Home > Algebra, Combinatorics > IMC 2014 Day 2 Problem 5

IMC 2014 Day 2 Problem 5


For every positive integer {n}, denote by {D_n} the number of permutations {(x_1,...,x_n)} of {(1,2,...,n)} such that {x_j \neq j} for every {1 \leq j \leq n}. For {1 \leq k \leq \frac{n}{2}}, denote by {\Delta(n,k)} the number of permutations {(x_1,...,x_n)} of {(1,2,...,n)} such that {x_i = k+i} for every {1 \leq i \leq k} and {x_j \neq j} for every {1 \leq j \leq n}. Prove that

\displaystyle \Delta(n,k) = \sum_{i = 0}^{k-1} {k-1 \choose i} \frac{D_{(n+1)-(k+i)}}{n-(k+i)}.

IMC 2014 Day 2 Problem 5

Advertisements
  1. Artur Kirkoryan
    August 3, 2014 at 6:11 pm

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

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: