Probability that at the end of the four exchanges, all balls are where they started? [DBertsekas P56, 1.20] 
We have two jars each containing initially $n$ balls. We perform four
  successive ball exchanges. In each exchange, we pick simultaneously and at random a
  ball from each jar and move it to the other jar. What is the probability that at the
  end of the four exchanges all the balls will be in the jar where they started?
Solution:  (Soln uses subscripts) Let $P(i, n - i)[k]$ be the probability that after $k$ exchanges, a jar will contain $i$ balls that started in that jar and $n - i$ balls that started in
  the other jar.
  We want  $P(i, n - i)[4]$. Argue recursively, using the total probability theorem :
  

I'm flummoxed by this question; I seem to only apprehend $P(1, n - 1)[1] = 1$
. This is because the first ball exchange must transfer one ball from each jar and to the other. Afterwards, each ball must contain $n - 1$ original balls but the $1$ from the other. 
Could someone please explicate what's happening? The solution looks terse.  
Source: P56, 1.19, An Intro to Pr, 2nd Ed, D Bertsekas 
 A: From the bottom up:
The second swap can hit zero, one or two of the balls swapped by the first swap. There are $(n-1)^2$, $2\cdot1\cdot(n-1)$ and $1^2$ choices for the balls, respectively, and these need to be divided by the total number $n^2$ of choices to get the corresponding probabilities.
For the third swap, we're only interested in the probability that it results in a state with one pair of balls swapped, because that's the only case in which the fourth swap can restore the original state. Again we need to count the number of choices that lead to the desired result: If two pairs are swapped, there are $2^2$ choices that unswap one pair; if one pair is swapped, there are $2\cdot1\cdot(n-1)$ choices that hit one swapped and one unswapped ball, leaving the number of swapped pairs at $1$, and if no pair is swapped, all $n^2$ choices result in one swapped pair.
A: I will try to explain each step below:

step (4): pn,0(4) = $\frac{1}{n}$$\frac{1}{n}$ pn-1,1(3)

This is because if you want to be in the perfect state after 4 step, there is only 1 way, which is by having 1 pair of balls swaped at step 3, and then swap those 2 exactly (picking each with probability $\frac{1}{n}$) from each jar.

step (3): pn-1,1(3) = pn,0(2) + 2 $\frac{n-1}{n}$$\frac{1}{n}$ pn-1,1(2) + $\frac{2}{n}$ $\frac{2}{n}$ pn-2,2(2)

To get to right state ready forstep (3), there are 3 ways


*

*you can start from a perfect state in step 2, in that case, you can swap whatever you want and you will only have one pair of balls swapped (getting ready for step 4)

*you can start from one pair of misplaced balls in step 2, in that case, you need to maintain in the same state by swapping one misplaced ball with one correctly placed ball. There are two ways to doing it


*

*pick a misplaced ball from first jar (prob $\frac{1}{n}$) and a correctly placed ball from second jar (prob $\frac{n-1}{n}$) and swap them

*pick a correctly placed ball from first jar (prob $\frac{n-1}{n}$) and a misplaced ball from second jar (prob $\frac{1}{n}$) and swap them


*you can start from two pairs of misplaced balls in step2, in that case, you have to pick one of the misplaced balls (prob $\frac{2}{n}$) from the first jar and one of the misplaced balls (prob $\frac{2}{n}$) from the second jar and swap them



step (2): pn,0(2) = $\frac{1}{n}$ $\frac{1}{n}$ pn-1,1(1)

To get to this state of step 2, we need to revert step 1 by picking exactly the right balls ($\frac{1}{n}$ $\frac{1}{n}$)

step (2): pn-1,1(2) = 2 $\frac{n-1}{n}$ $\frac{1}{n}$ pn-1,1(1)

To get to this state of step 2, we have 2 ways again
- pick a misplaced ball from jar 1 and a correctly placed ball from jar 2, then swap
- pick a correctly placed ball from jar 1 and a misplaced ball from jar 2, then swap

step (2): pn-2,2(2) = $\frac{n-1}{n}$ $\frac{n-1}{n}$ pn-1,1(1)

To get to this state of step 2, we need to generate another pair of misplaced balls by choose the correctly placed balls from jar 1 and jar 2 and swap them

step (1): pn-1,1(1) = 1

To get into the state of one pair of misplaced balls, you can swap any balls from each jar
Note: You can also try to read the steps from bottom to top if that makes more sense to you!
