3
$\begingroup$

Definition

A permutation $\pi = a_1 a_2 \cdots a_n \in S_n \; \; i \in \{1,\cdots,(n-1)\}$ is called a decrease if $a_i > a_{i+1}$. For $k \geq 1$, let $A(n,k)$ be the number of permutations of $[n]$ having $k-1$ decreases. We set $A(0,0) = 1$ and $A(0,k) = 0$ for $k \geq 1$.

Excercise

Prove that for $n \geq 0, k \geq 1$: $A(n,k) = k \cdot A(n-1,k) + (n-k+1) \cdot A(n-1,k-1)$


I first tried to write down the permutations and their decreases for n = 2,3,4:

$ \begin{array}{l|r} \text{Permutation} & \text{#} \\ 12 & 0 \\ 21 & 1 \\ \end{array} $

$ \begin{array}{l|r|l|r} \text{Permutation} & \text{#} & \text{Permutation} & \text{#} \\ 123 & 0 & 132 & 1 \\ 213 & 1 & 231 & 1 \\ 312 & 1 & 321 & 2 \end{array} $

$ \begin{array}{l|r|l|r|l|r} \text{Permutation} & \text{#} & \text{Permutation} & \text{#} & \text{Permutation} & \text{#} \\ 1234 & 0 & 1243 & 1 & 1324 & 1 \\ 1342 & 1 & 1432 & 2 & 1423 & 1 \\ \hline 2134 & 1 & 2143 & 2 & 2314 & 1 \\ 2341 & 1 & 2413 & 1 & 2431 & 2 \\ \hline 3124 & 1 & 3142 & 2 & 3214 & 2 \\ 3241 & 2 & 3412 & 1 & 3421 & 2 \\ \hline 4123 & 1 & 4132 & 2 & 4231 & 2 \\ 4213 & 2 & 4312 & 2 & 4321 & 3 \end{array} $

I played around with this for quite a while, but looking for example at

$\begin{array}{lllll} A(4,1) & = 1 \cdot A(3,1) & + 4 \cdot A(3,0) & = 1 \cdot 1 + 4 \cdot 0 & = 1 \\ A(4,2) & = 2 \cdot A(3,2) & + 3 \cdot A(3,1) & = 2 \cdot 4 + 3 \cdot 1 & = 11 \\ A(4,3) & = 3 \cdot A(3,3) & + 2 \cdot A(3,2) & = 3 \cdot 1 + 2 \cdot 4 & = 11 \\ A(4,4) & = 4 \cdot A(3,4) & + 1 \cdot A(3,3) & = 4 \cdot 0 + 1 \cdot 1 & = 1 \end{array}$

didn't make me see anything that helped me understanding and proving that recursive definition.

Could you please help me a bit?

Thanks in advance!

1 Answers 1

3

The first summand comes from the following construction: take a $n-1$-permutation with $k-1$ decreases; now you can add a new element, $n$ (which is the largest) without inducing new decreases by either entering it directly before any given decrease ($k-1$ places) or the end (1 additional place).

The second summand is similar, only now we consider the places where adding $n$ will create a new decrease (namely, exactly those where a decrease didn't happen before, and not the end).

  • 0
    Oops, I mixed k and the amount of decreases up - of course you were right.. Sorry and thank you very much for your great answer!2011-05-22