Let $k$ be a positive integer, and set $n=2^k$, $N=\{1, 2, \cdots, n\}$. For any bijective function $f:N\rightarrow N$, if a set $A\subset N$ contains an element $a\in A$ such that $\{a, f(a), f(f(a)), \cdots\} = A$, then we call $A$ as a cycle of $f$. Prove that: among all bijective functions $f:N\rightarrow N$, at least $\frac{n!}{2}$ of them have number of cycles less than or equal to $2k-1$. Note: A function is bijective if and only if it is injective and surjective; in other words, it is 1-1 and onto. Proposed by CSJL
Problem
Source: 2023 Taiwan Round 1 Mock Exam P4
Tags: combinatorics, Permutation cycles, Taiwan, function
asbodke
18.03.2023 21:46
The cases $k=1$ and $k=2$ can be checked readily, we focus only on $k\ge 3$. Consider a random function. Let $X$ be the number of cycles it contains, and let $X_i$ be the number of cycles it contains of length $i$. Note that we have \[ \mathbb E[X_i] = \binom{n}{i} \frac {(i-1)! (n-i)!}{n!}=\frac 1i,\]since there are $\tbinom ni$ possible cycles of length $i$, of which the probability it is present in the function is as described above. And so \begin{align*} \mathbb E[X]&=\mathbb E[X_1]+\mathbb E[X_2] +\cdots + \mathbb E[X_n]\\ &= \frac 11 + \frac 12+\frac 13 + \frac 14 + \frac 15 +\cdots + \frac 1{2^k}\\ &< \frac 11 + \frac 12 + \frac 12 + \frac 14 + \frac 14 + \cdots + \frac 1{2^k} +\left (\frac 13-\frac 12\right)\\ &= k + \frac 1{2^k}-\frac 16\\ &< k. \end{align*}And now by Markov's inequality \[ \mathrm P (X\ge 2k) \le \frac{\mathbb E[X]}{2k}<\frac 12,\]as desired.
CSJL
20.03.2023 01:09
asbodke wrote: The cases $k=1$ and $k=2$ can be checked readily, we focus only on $k\ge 3$. Consider a random function. Let $X$ be the number of cycles it contains, and let $X_i$ be the number of cycles it contains of length $i$. Note that we have \[ \mathbb E[X_i] = \binom{n}{i} \frac {(i-1)! (n-i)!}{n!}=\frac 1i,\]since there are $\tbinom ni$ possible cycles of length $i$, of which the probability it is present in the function is as described above. And so \begin{align*} \mathbb E[X]&=\mathbb E[X_1]+\mathbb E[X_2] +\cdots + \mathbb E[X_n]\\ &= \frac 11 + \frac 12+\frac 13 + \frac 14 + \frac 15 +\cdots + \frac 1{2^k}\\ &< \frac 11 + \frac 12 + \frac 12 + \frac 14 + \frac 14 + \cdots + \frac 1{2^k} +\left (\frac 13-\frac 12\right)\\ &= k + \frac 1{2^k}-\frac 16\\ &< k. \end{align*}And now by Markov's inequality \[ \mathrm P (X\ge 2k) \le \frac{\mathbb E[X]}{2k}<\frac 12,\]as desired. Nice one! This is exactly how a came up with this problem.