About André's original solution to the Ballot problem My question is about the Ballot_problem; By applying André's trick, it is directly obvious that permuting a sequence of p As and (q-1) Bs gives back a sequence of p As and q Bs that: (1) starts with an A, (2) is unfavorable. But it is not obvious to me how does this prove that it gives back ALL the unfavorable sequences starting with an A?
Also, by applying André's trick, it is directly obvious that every unfavorable sequence of p As and q Bs could be converted into a sequence of p As and (q-1) Bs. Yet it is not obvious to me how could we be sure that every resulting sequence is unique?
In general, is there a systematic/direct way of proving the one-to-one mapping between both sequences, without going through examining the results (individually/by hand) to make sure that this is the case?
 A: It would have been practical if you had explained what is being proved, and what André's trick for proving it was. The ballot problem involves counting, for given positive integers $p>q$, among all $\binom{p+q}p$ permutations of a word of $p$ letters A and $q$ letters $B$, the "favorable" ones, in which every nonempty prefix of the word contains strictly more letters A than B (viewed as a sequence of votes being cast succesively, candidate A is strictly ahead all of the time). The proof is based on showing that among the unfavorable sequences, there are as many starting with A as with B. Since the sequences starting with B are all unfavorable and there are $\binom{p+q-1}p$ of them, the number of favorable sequences is then easily computed to be $\binom{p+q}p-2\binom{p+q-1}p=\frac{p-q}{p+q}\binom{p+q}p$.
André's trick for proving this is to map the unfavorable sequences starting with A bijectively to those starting with B by splitting the the former sequence just before the first B that makes the number of B's in the prefix equal to the number of its number of A's, and putting the two obtained subsequences together in the opposite order, so that the mentioned B becomes the first letter of the sequence.
This obviously is a well defined map (since sequences starting with A must contain such a letter B to be considered unfavorable, and the resulting sequence starts with B and is therefore unfavorable). To see that it is a bijection, we can define an inverse map. Given an unfavorable sequence starting with B, search the first A from the right that makes the number of A's in the corresponding suffix strictly larger than the number of B's (since the A's are overall in the majority, such an A exists), split to separate this suffix, and put the two obtained subsequences together in the opposite order. This suffix starts with A and has overall one more A than B, so that after going to the front and being followed by a B the result is ensured to start with A and be unfavorable.
To see why the maps are inverses, call "Dyck word" any sequence that has balanced parentheses if we read A as '(' and B as ')': it has equally many A's as B's overall (possibly none), and no prefix has more B's than A's (equivalently no remaining suffix has more A's than B's). The prefix split for in the first operation, and the suffix split off in the second operation, both consist of A followed by a Dyck word. One now easily sees that after applying one operation, the other operation applied to the resulting sequence will find the original split into two subsequences, and therefore put them together to form the original word.
A: At last, it clicked. It turned out that what I needed is a visual representation. Diagrams are perfect in conveying symmetry, which is capable, especially in combinatorics, of revealing the unspoken.
For clarity let's refer to all the unfavorable permutations of p letters A and q letters B that start with A as $ \alpha $ sequences, and to those of p letters A and (q-1) letters B as $ \beta $ sequences.
You have thoroughly described the problem and it is clear to me that all the $ \alpha $ sequences are convertible into $ \beta $ sequences. What I was, mainly, missing is why this is a unique correspondence; I wasn't (literally) seeing it. Not until I visited the Dyck word wiki page and had a look into some diagrams, and despite escaping most of the text, it inspired me to go looking further for other diagrams describing our exact version of the ballot problem.
The way I see it now is just how you explained it: I check that all $ \alpha $ sequences are convertible into $ \beta $ sequences, which proves that there are at least as many $ \beta $ sequences as $ \alpha $s (there are AT LEAST as many, but not yet EXACTLY as many). So far there may have been more of $ \beta $ sequences still overlooked. Then it take a short while to see (see literally, again) from the diagrams that every $ \beta $ sequence produces a unique $ \alpha $ sequence, as well. Hence the one-to-one mapping.
If we think of $ \beta $ sequences as group of boxes, and $ \alpha $ sequences as group of balls, it translates to this: we check that all balls are contained in boxes, so there are AT LEAST as many boxes as balls. So to prove that there are EXACTLY as many boxes as balls, we have to show that there are no empty boxes left. And this is done by showing that every box available does indeed contain a ball, and only one ball.
It is hard to further extend the explanation or give a full demonstration in words, but if there is a need for one, I could post a separate answer backed up with diagrams.
Thanks @Marc van Leeuwen.
