Problem

Source: Iran 3rd round 2011-combinatorics exam-p4

Tags: combinatorics proposed, combinatorics



We say the point $i$ in the permutation $\sigma$ ongoing if for every $j<i$ we have $\sigma (j)<\sigma (i)$. a) prove that the number of permutations of the set $\{1,....,n\}$ with exactly $r$ ongoing points is $s(n,r)$. b) prove that the number of $n$-letter words with letters $\{a_1,....,a_k\},a_1<.....<a_k$. with exactly $r$ ongoing points is $\sum_{m}\dbinom{k}{m} S(n,m) s(m,r)$.