Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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).

share|improve this answer
    
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
    
Why should there be 2 other positions? There should be (n-k+1) positions, and in your example n=5, k=4, so (n-k+1)=2 - two positions which add a decrease overall. –  Gadi A May 22 '11 at 17:21
    
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! –  muffel May 22 '11 at 17:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.