For a positive integer $n$, consider all nonincreasing functions $f : \{1,\hdots,n\}\to\{1,\hdots,n\}$. Some of them have a fixed point (i.e. a $c$ such that $f(c) = c$), some do not. Determine the difference between the sizes of the two sets of functions. Remark. A function $f$ is nonincreasing if $f(x) \geq f(y)$ holds for all $x \leq y$
Problem
Source: 2019 Baltic Way P9
Tags: function, combinatorics, Enumerative Combinatorics
biomathematics
18.11.2019 15:42
Note that a non-increasing function can have at most $1$ fixed point. The number of non-increasing functions is clearly $${2n-1 \choose n-1}$$ Now we count the number of non-increasing functions with a fixed point. For each $1\le m \le n$ the number of non-increasing functions for which $f(m)=m$ are $${n-1 \choose m-1} \cdot {n-1 \choose n-m}$$As $m$ varies, we sum up these quantities and obtain $${2n-2 \choose n-1}$$
hanulyeongsam
16.10.2024 17:54
hmmmmmmmmmmm
hanulyeongsam
16.10.2024 18:03
My solution: Lets put A the functions that has f(m)=m in it, and B as the opposite. Lemma:
the number of this function
f: {1,2,...,a}->{1,2,...,b}
f(1)>=f(2)>=...>=f(a) is
(a+b-1)C(a).
So, |A|+|B|=(2n-1)C(n) Another crucial truth...... the number of f(m)=m is smaller than 2.
pf)
c<d.
f(c)=f(d)
according to the question, f(c)>f(d) but f(c)=c<d=f(d) false!
So, let's but m the one that makes f(m)=m (m-1 numbers) m (n-m numbers) Let's put the first part (the one with m-1 numbers) X and the second part (the one with n-m numbers) Y. Because of the Lemma I wrote, |X|=(n-1)C(m-1) and |Y|=(n-1)C(n-m) |A|=|X|+|Y|=(n-1)C(m-1)+(n-1)C(n-m)=(2n-2)C(n-1) |B|=(2n-1)C(n)-(2n-2)C(n-1)=(2n-2)Cn
(2n-2)C(n-1)