Alice and bob are playing cards. for each round of the game, player can win 1 card if he or she won the round, otherwise, he or she loses $1$. It's a $30$ rounds game, and player can hold negative amount of cards which he or she owes to the other player. the game result will be presented by series of $30$ characters, built from $A,B$.
A- if Alice won the round.
B- if Bob won the round.
What is the number of possible sequences (game results) under the following restriction: Bob started with 2 cards, finished with no cards and during the competition Bob never owed Alice cards.
if I wasn't clear enough, please tell me and I'll fix it.
HINT: It’s easiest to derive a general formula.
Assume that Alice starts with no cards in hand. Let $b_n$ be the number of valid sequences for a game of $2n$ rounds when Bob starts with $2$ cards in hand. Let $a_n$ be the number of valid sequences for a game of $2n+1$ rounds when Bob starts with one card in hand. We know that there are $C_n$ valid sequences of $2n$ rounds when Bob starts with no cards in hand.
If Bob starts with one card in hand in a game of $2n+1$ rounds, there are two possibilities. If Alice wins the first round, the next $2n$ rounds must play out as if Bob and Alice were starting with no cards in hand, so there are $C_n$ valid continuations. If Bob wins the first round, he starts the next $2n$ rounds with $2$ cards in hand to Alice’s none, so there are $b_n$ valid continuations. Thus, $a_n=b_n+C_n$, and hence $b_n=a_n-C_n$. Thus, to get an expression for $b_n$ in terms of $n$, we need only do so for $a_n$.
In case you get completely stuck, I’ve left a hint in the spoiler-protected block below.