# Proving a recursive definition about decreases in permutations

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.

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).
• Thank you for your answer! I just didn't got the whole part about the second summand. Consider the second part for A(5,4) - so the second part is about adding one decrease by adding the number 5 to all permutations of [4] having 2 decreases. Let's look at $\sigma = 4 2 3 1$. Then we might add the 5 at the beginning - as for every permutation here. But what about the other 2 positions? The only position which is not a decrease is $a_2 = 2$. So one possibility is to add the 5 just after 2 -> (4,2,5,3,1). But what about the other one? – muffel May 22 '11 at 17:13