Can A has N 1 $ bills. Can B is empty. At each step you can either take a bill from can A or put a bill you already have into can B. You can choose to keep some bills in your hand and take some more bills from can A. At the end all the bills should be in can B.
For e.g. Let N = 10, I can do a sequence:
take 1, take 1, take 1, put 1, put 1, take 1 take 1, put 1, take 1, put 1, put 1, take 1, take 1, put 1, take 1, take 1, put 1, put 1, put 1, put 1
In how many possible ways can I do this?
I am trying to reduce this to a problem of solving number of non-negative solutions of equations x1 - y1 >=0; x1 + x2 - (y1 + y2) >= 0; x1 + x2 + x3 - (y1 + y2 + y3) >= 0
where xis correspond to taking a xi bills from can A and yi to putting yi bills in can B. But, I am stuck here and not able to go any further.
Consider the case when all the bills are distinct. Now, how many permutations are there in which I can do the above process?
We can associate each dollar bill with a letter, and then consider a word of length $2n$ (where $n$ is the number of dollar bills) with the requirement that each associated letter appears exactly twice in the word. Each such word will give us a unique (up to permutation) way to draw the dollar bills and put them into can B by moving along the word from left to right, and when we encounter a letter the first time we move the associated dollar bill from can A to our hand, and when we encounter it the second time we move it from our hand to can B.
For example, for three dollar bills we could associate the letters a,b,c, and the word 'abbcca' would tell us how to move the dollar bills; first moving a to our hand, then b, then moving b to can B, and so forth.
It then suffices to count the number of such words which are distinct, which is $\dfrac{(2n)!}{2^n}$.