Cycle of Permutations

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Cycle of Permutations

G H J

Reveal topic tags

Permutation cycles

L

G H BBookmark kLocked kLocked NReply

Source: 2023 Taiwan Round 1 Mock Exam P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

55 posts

CSJL

#1 h Mar 18, 2023, 9:06 AM • 2 Y

Y by anantmudgal09, kiyoras_2001

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1914 posts

#4 h Mar 18, 2023, 6:46 PM • 4 Y

Y by gvole, R8kt, IAmTheHazard, CSJL

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.

This post has been edited 2 times. Last edited by asbodke, Mar 18, 2023, 6:53 PM
Reason: defined 2 things called k

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

55 posts

CSJL

#5 h Mar 19, 2023, 10:09 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatinoBarbaraCombinatoric

103 posts

CatinoBarbaraCombinatoric

#6 h Thursday at 1:00 PM • 1 Y

Y by math90

We can prove a much better bound then $2k-1$ .
Costruct the function in the following way:
Choose $a$ at random.
Choose $f(a)$ .
Set $b=f(a)$ and choose $f(b)$ .
And so on.
When we have $f(x)=a$ we have formed a new cicle.
Now choose randomly a different element and repeat this.
At every step we create a new cicle with probability $1/k$ where $k$ is the number of remaing terms.
So let $x_i$ be $1$ if at step $i$ we create a cicle and $0$ otherwise.
Let $X$ the total number of values.
Then $X=\sum_{i=1}^{n} x_1$
So $\mathbb{E} [X]=\sum_{i=1}^{n} 1/i$ $Var(X)=\mathbb{E}[X^2]-\mathbb{E}[X]^2$ $=\mathbb{E}[\sum_{i=1}^{n}x_i^2]+2\mathbb{E}[\sum_{i<j}x_ix_j]-\mathbb{E}[X]^2$ $=\mathbb{E}[\sum_{i=1}^{n}x_i^2]+2\mathbb{E}[\sum_{i<j}x_ix_j]-(\sum_{i=1}^{n} 1/i)^2$ Notice that $x_i$ and $x_j$ are indipendent. So $\mathbb{E}[x_ix_j]=1/ij$ and $x_i^2=x_i$ .
So $Var(X)$ became
$\sum_{i=1}^{n}(1/i)+2\sum_{i<j}(1/ij)-(\sum_{i=1}^{n} 1/i)^2$ $=\sum_{i=1}^{n}(1/i)-\sum_{i=1}^{n}(1/i^2)$ Now we have that
$Var(X)\geq 2Var(X)P(X\geq \mathbb{E}[X]+\sqrt{2Var(X)})$ So
$P(X\geq \mathbb{E}[X]+\sqrt{2Var(X)})\leq 1/2$ So for at least $n!/2$ permutation the number of cicles is less than $\mathbb{E}[X]+\sqrt{2Var(X)}<H_n+\sqrt{2H_n}$
$H_n$ is less $k$ and in particular is $\approx \dfrac{k}{\log_2(e)}$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a