MathDB
IMC 2014, Problem 10

Source: IMC 2014

July 27, 2016
IMCcollege contestspermutationscombinatorics

Problem Statement

For every positive integer nn, denote by DnD_n the number of permutations (x1,…,xn)(x_1, \dots, x_n) of (1,2,…,n)(1,2,\dots, n) such that xj≠jx_j\neq j for every 1≤j≤n1\le j\le n. For 1≤k≤n21\le k\le \frac{n}{2}, denote by Δ(n,k)\Delta (n,k) the number of permutations (x1,…,xn)(x_1,\dots, x_n) of (1,2,…,n)(1,2,\dots, n) such that xi=k+ix_i=k+i for every 1≤i≤k1\le i\le k and xj≠jx_j\neq j for every 1≤j≤n1\le j\le n. Prove that Δ(n,k)=∑i=0k=1(k−1i)D(n+1)−(k+i)n−(k+i)\Delta (n,k)=\sum_{i=0}^{k=1} \binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n-(k+i)}
(Proposed by Combinatorics; Ferdowsi University of Mashhad, Iran; Mirzavaziri)
Back to ProblemsView on AoPS