# 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$, allow $A(n,k)$ be the variety of permutations of $[n]$ having $k-1$ declines. We set $A(0,0) = 1$ and also $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 attempted to list the permutations and also their declines 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 experimented with this for a long time, yet seeking instance 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}$

really did not make me see anything that aided me recognizing and also confirming that recursive definition.

Could you please aid me a little bit?

Many thanks beforehand!

3
2022-06-07 14:32:54
Source Share
The first summand originates from the adhering to building and construction: take a $n-1$ - permutation with $k-1$ lowers ; currently you can add a new component, $n$ (which is the biggest) without generating new declines by either entering it straight prior to any kind of offered decrease ($k-1$ areas) or completion (1 added area).
The 2nd summand is comparable, just currently we take into consideration the areas where including $n$ will certainly create a new decrease (particularly, specifically those where a decrease really did not take place in the past, and also not completion).