Prove that there are exactly $\binom{k}{[k/2]}$ arrays $a_1, a_2, \ldots , a_{k+1}$ of nonnegative integers such that $a_1 = 0$ and $|a_i-a_{i+1}| = 1$ for $i = 1, 2, \ldots , k.$
Problem
Source:
Tags: combinatorics, counting, Sequences, binomial coefficients, IMO Shortlist
kamil9876
22.09.2010 15:46
This can be related to Catalan Numbers for the $k$ even case. I guess you can sort of adjust it for the odd case. This relationship can be most easily seen from the monotonic path characterization as given here. http://en.wikipedia.org/wiki/Catalan_number#Second_proof
mahanmath
22.09.2010 15:52
kamil9876 wrote: This can be related to Catalan Numbers for the $k$ even case. I guess you can sort of adjust it for the odd case. This relationship can be most easily seen from the monotonic path characterization as given here. http://en.wikipedia.org/wiki/Catalan_number#Second_proof .... [Edited !]
kamil9876
22.09.2010 16:01
Maybe it is related to Sperner, I don't know. But you can't say "No" to my reply, catalan numbers do give the result. edit: Oh no, sorry, I see that I made a mistake. edit2: on second thought, Catalan numbers do come in handy here. Let the answer to the problem be A(k) and let B(k) be the number of such sequences with the condition that $a_{k+1}=0$. Now a recursion can be made from the following observation: To compute $A(k+1)$, notice that if $a_{k+1}$ is non-zero then we can either add 1 or -1 to it to get $a_{k+2}$. However if $a_{k+1}$ is 0 then we can only add 1. Hence we get: $A(k+1)=B(k)+2( A(k)-B(k))=2A(k)-B(k)$ However notice that $B(k)=0$ if $k+1$ is odd. While (by the link I provided), if $k+1$ is even then $B(k)$ is the $k/2$ Catalan Number. This should be enough to do an induction proof.