Permutations when element pairs alternate

Question

First I'll explain my question and then how I arrived at this as the crux of a real-world problem.

Q: how many permutations are there of a $n$-move long sequence of A,B,C,D where A,B and C,D exist each in pairs such that A and B must alternate and C and D must alternate, in the sense that anytime A occurs it cannot recur until B has next occurred and vice versa (seen another way, if you strip the list down to just this pair and get rid of the Cs and Ds, it has to be ABABAB... or BABABA...)? The sequence can start with any letter and each possible sequence is distinct. For example a possible sequence of length $n=15$ is ADCDCDBCDCABABD.

Real-world use case: Bughouse chess is a popular variant of chess which differs in that you play in teams and can use pieces taken by your partner on your own board. Say that A and C are playing against B and D. On board 1, A and B must alternate their moves (like in standard chess), and on board 2, C and D must alternate; but there is no cross-board sequential order, in other words, many turns (move-pairs) can be played on one board while players sit still on the other. (There is a clock to make sure no-one is stalling too long, but we can ignore this aspect for our purposes here.)

It's obvious that Bughouse has a vastly larger gametree than standard chess, not just because the piece drops you can make enlarge the branching factor (number of possible moves on each turn), but because of this freedom to play your moves whenever you want with regards to the other board (not with regards to your opponent counterpart on your own board). However, game-theoretically, my understanding would be that it shouldn't matter (except in some edge-cases maybe) exactly when you move; if we suppose the state-space depends purely on the position of the two boards, then the gametree could be modelled by enumerating the sequences I have suggested. Of course this works for only a rough approximation where you assume a static number of available actions per turn.

If you want to take a stab at estimating the gametree size itself, which is my idea, you could estimate that there are $M=100$ possible actions per move and the game will last $n=160$ total moves (the usual estimate is 40 turns for standard chess, so I'm saying 80 turns across the two boards combined).

Bonus points for an answer that readily extends to $B$ boards, i.e., $B$ pairs of the form (A,B),(C,D),(E,F),... and a game lasting $n = 80B$ total moves, i.e. sequence length $80B$.

Answer 1

As suggested by lulu's comment: To choose such a sequence, we can first pick which subsequence will appear at each index ($2^n$ possibilities) and then choose the starting value of both subsequences ($2\times2$ possibilities). This yields each desired sequence in exactly one way except for the four sequences in which only one of the subsequences is present, each of which is counted twice (once for each version of the missing subsequence). Subtracting the double-counting, we get a total count of $2^{n+2}-4$.

If the number of boards is $b$ instead of 2, more inclusion-exclusion work is needed to get an exact count, but a reasonable estimate when $n$ is much larger than $b$ (so that most of the sequences include all the boards) is $2^bb^n$, by the same reasoning.