In how many ways can the basketball be passed between four people so that the ball comes back to $A$ after seven passes? (Use recursion)

Question

There are four basketball players $A, B, C, D$. Initially, the ball is with $A$. The ball is always passed from one person to a different person. In how many ways can the ball come back to $A$ after seven passes? (For example $A \mapsto C \mapsto B \mapsto D \mapsto A \mapsto B \mapsto C \mapsto A$ and $A \mapsto D \mapsto A \mapsto C \mapsto A \mapsto B \mapsto C \mapsto A$)

I know that it can be done considering cases (location and the number of passes received by $A$ in between). But I'm interested in learning some recursion. So, it would be good if some explicitly explains how to get the recursion. Not just the recursion, but how to "derive" it.

Answer 1

Note that there are only two states: either A has the ball or somebody else has it. Define $f(n)$ as the number of ways to pass the ball $n$ times so that $A$ has it at the end and $g(n)$ as the number of ways to pass the ball $n$ times so that somebody else has it at the end. We start with $f(0)=1, g(0)=0$ because after $0$ passes $A$ has the ball. If somebody else has the ball there is $1$ way to pass it to $A$, so $f(n+1)=g(n)$. If $A$ has the ball there are three ways to pass it to somebody else, while if somebody else has it there are two, so $g(n+1)=3f(n)+2g(n)$

Answer 2

Let $b_{i,n}$ be the number of ways to get the ball to player $i$ in $n$ passes, where $i = 1,2,3,4$ corresponds to $A,B,C,D$. First you answer the question, "What is $b_{i,0}$ for each $i$?" The answer should reflect the initial condition, which says that $A$ has the ball. Hence $b_{1,0} = 1$ and $b_{j,0} = 0$ for $j \neq 1$.

The next question sets up the recursion: "What is $b_{i,n+1}$ in terms of $b_{j,n}$ (for all $j$)?" For example, there are 3 ways to get the ball to $A$ ($j=1$) in two passes, and 2 ways to get the ball to everybody else ($j=2,3,4$) in two passes. If the ball is in $A$'s hands after two passes, someone else will have it after the third pass. However, if someone else has the ball after two passes, then that someone can pass it to $A$ (in exactly one way). Hence there are $b_{1,3} = 6 = b_{2,2} + b_{3,2} + b_{4,2}$ ways to get the ball to $A$ in three passes. On the other hand, $b_{2,3} = 7 = b_{1,2} + b_{3,2} + b_{4,2}$.

It should be not too difficult to write a general formula for $b_{i,n+1}$ at this point. This formula will give you the recurrence, which is conveniently written in matrix form.

For the solution, there's more than one method. Which one(s) have you seen?

Answer 3

Ross Millikan set up the recursion, so here we find the solution using a recursively defined function in Python:

def PassBall(m):
    if m == 0:
        return {'f':1, 'g':0}
    else:
        r = PassBall(m-1)
        return {'f':r['g'] ,'g':3*r['f'] + 2 * r['g']}

for n in range(0,8):
    print (n, PassBall(n))

Output:

0 {'f': 1, 'g': 0}
1 {'f': 0, 'g': 3}
2 {'f': 3, 'g': 6}
3 {'f': 6, 'g': 21}
4 {'f': 21, 'g': 60}
5 {'f': 60, 'g': 183}
6 {'f': 183, 'g': 546}
7 {'f': 546, 'g': 1641}