## IMC 2014 Day 2 Problem 5

For every positive integer , denote by the number of permutations of such that for every . For , denote by the number of permutations of such that for every and for every . Prove that

**IMC 2014 Day 2 Problem 5**

Advertisements

Categories: Algebra, Combinatorics
Algebra, Combinatorics, IMC

Here is a try: https://www.dropbox.com/s/mrjivjytpyv23vb/IMC_2014d2p5_comb_identity.pdf

Very straightforward solution:

delta(n+1,k+1)=delta(n,k)+delta(n-1,k). The proof of this is easy combinatorical transformation – start with delta(n+1,k+1), erase 2k+2 from the list, exchange 2k+1 with k+1 and if needed, erase 2k+1 as well. In order to complete an induction, just check the trivial cases delta(2k,k) and delta(n,1).