Find the number of functions $ A\stackrel{f}{\longrightarrow } A $ for which there exist two functions $ A\stackrel{g}{\longrightarrow } B\stackrel{h}{\longrightarrow } A $ having the properties that $ g\circ h =\text{id.} $ and $ h\circ g=f, $ where $ B $ and $ A $ are two finite sets.
Problem
Source: Romanian National Olympiad 2017, grade x, p. 4
Tags: function, algebra, combinatorics, identity
26.08.2019 18:40
Is the set $B$ given or can we vary it for different functions $f$?
26.08.2019 23:17
$ A,B $ and $ f $ are fixed from the beginning, and we play with $ g,h. $
27.08.2019 17:44
CatalinBordea wrote: $ A,B $ and $ f $ are fixed from the beginning, and we play with $ g,h. $ Wait? If $f$ is fixed, then what does it mean to look for the number of functions $f:A \to A$ such that...?
27.08.2019 22:25
It's the standard way of solving. You fix an $ f $ to determine what could be, and then you verify.
27.08.2019 22:54
I think, $A$ and $B$ are fixed. Of course $f$ is not. Given what's given, it follows $|B|\leq |A|$. Let $|A|=n, |B|=k,k\leq n$. Then $B$ is mapped 1 to 1 to some subset $A'\subset A, |A'|=|B|$. So, $f$ is $\text{id}$ over $A'$ and $f$ can be whatever we want over $A\setminus A'$, complying $f(a)\in A', \forall a\in A\setminus A'$. It means the number of those functions is $$k^{n-k}\binom{n}{k}$$ Remark: The statement is more complicated than the meaning and the solution.
11.09.2019 20:28
i got a different result... $k^{n-k}\frac{n!}{(n-k)!}$ there are $\frac{n!}{(n-k)!}$ ways to choose an isomorphic copy of B in A, and then create a one-to-one map between them.
12.09.2019 17:44
No, we look for the number of functions $f$, not the number of variants of $f$ combining with $h$. Indeed, there are $\frac{n!}{(n-k)!}$ way to choose an isomorphic copy $A'$ of $B$ in $A$, but what really matter is the set $A'$ itself, all permutations of $A'$ produce the same $f$. In fact, $f$ is determined by a set $A'\subset A, |A'|=k$, over which $f$ is identity and may be whatever we want over $A\setminus A'$ (of course its values are in $A$). The set $A'$ can be chosen in $\binom{n}{k}$ ways, the rest variants are $k^{n-k}$. So, the result is $k^{n-k}\binom{n}{k}$. Ok?
13.09.2019 17:20
Why is it that $|B| \le |A|?$
13.09.2019 21:46
Remember, $g\circ h=\text{ id}$. So could we send the set $B$ through $h$ to a smaller set $A$ and then, through $g$, back to $B$ and that mapping be the identity on $B$ ? I may also put it in a more formal way, but perhaps it's not needed?