I have this assignment where I'm really lost and not sure how to solve. The assignment follows:
We have two sets, $A = \{1,2,3,4,5,6,7\}$ and $X=\{a,b,c,d,e,f\}$. We say that a function $F$ is growing if $x \le y$ or $F(x)\le F(y)$. How many growing functions are there from $A$ to $X$?
I would appreciate advice on how to start and what to do next.
I have figured out that there are 6^7 functions from $A$ to $X$, and I know that the $(n+1)^{th}$ element need to be equal or bigger than the $n^{th}$ element, meaning $n+1\ge n$, for all increasing function, so it should look a little something like this, these below are some of the growing functions.
[a,a,a,a,a,a,a] [a,a,a,a,a,a,b] [a,a,a,a,a,a,c] [a,a,a,a,a,a,d] [a,a,a,a,a,a,e] [a,a,a,a,a,a,f] [a,a,a,a,a,b,b] [a,a,a,a,a,b,c] [a,a,a,a,a,b,d] [a,a,a,a,a,b,e] [a,a,a,a,a,b,f] [a,a,a,a,a,c,c] [a,a,a,a,a,c,d] [a,a,a,a,a,c,e] [a,a,a,a,a,c,f] [a,a,a,a,a,d,d] [a,a,a,a,a,d,e] [a,a,a,a,a,d,f] [a,a,a,a,a,e,e] [a,a,a,a,a,e,f] [a,a,a,a,a,f,f] [a,a,a,a,b,b,b] [a,a,a,a,b,b,c] [a,a,a,a,b,b,e]
Now I don't know how to create a formula or how to prove and calculate how many increasing functions there are.
Thanks in advance!
Hint: These functions are in direct bijection with sequences of 5 stars and 7 bars. Equivalently these can be seen as lattice paths which use only ups and rights starting from (0,a) going to (7,f).
The function $[a,a,b,c,e,f,f]$ for example corresponds to the sequence $--\star-\star -\star\star-\star--$ and the lattice path
The function $[a,a,a,a,b,b,b]$ for example corresponds to the sequence $----\star ---\star\star\star\star$ and the lattice path
The function $[c,c,c,c,c,c,c]$ corresponds to the sequence $\star\star-------\star\star\star$
See if you can come up with the specific rules for the bijection yourself. How many sequences of stars and bars described above exist?