Let's say you have six ladder rungs. There are two particles on each rung of the ladder. Every second, one of the particles on each rung moves up and the other moves down. (At the top rung, the particle that will move up stays there, and at the bottom rung, the particle that will move down stays there.) How many ways are there for the particles to be paired on the rungs after 3 seconds (3 moves)?
What I've got so far: Let's start simple and extrapolate. Assume you have two rungs and 1 second. Because there are only two rungs, we only have to worry about the first rung- the second rung will be determined by what is on the first rung. Label the particles on the top rung A and B, and those on the bottom rung C and D. There are 4 possible particle combos after 1 second: AC, AD, BC, BD. Defining a function numberCombos(x,y) for shorthand which gives the number of combinations with x as rungs and y as seconds, numberCombos(2,1) = 4.
Next: 2 rungs, 2 seconds. After 2 seconds, any particle can be anywhere. Therefore, we get 12 possible combinations: 4*3 combos for the top rung (the bottom rung is determined by the top rung and thus does not affect the total) divided by 2 (as pairings are identical- A and B on a rung is the same as B and A on the same rung). numberCombos(2,2) = 6. Using similar logic, numberCombos(2, y >= 2) = 6.
Next: numberCombos(3, x). With 1 second, I'm pretty much entirely stuck - I have absolutely no idea how to approach this, and it takes way too long to do by hand. However, we do know that for over 3 seconds, any particle can be anywhere, so numberCombos (3, y >= 3) = 6*5*4*3/(2*2) = 90 combinations.
That's all I have. To complicate things even further, if a particle cannot reach either the top or bottom rung, there will be alternating rungs which it cannot reach for any given number of seconds. For example, given a particle on the 4th rung for a ladder of 7 steps (for example), after 3 seconds, it cannot be on the 4th rung, 2nd rung, or 6th rung; it can only be on rungs 1, 3, 5, or 7.
Is there a formula for numberCombos(x,y)? Even further, if we extend this problem so that there are z particles per rung, and z/2 move up and z/2 move down each second (just assume notation is numberCombos(x,y,z), is there still a formula?
Thanks for your help in advance!
**Edit: As user @David K noted, I overcounted numberCombos(2,2). It is 6, not 12. The mistake has been fixed, and its reason noted.