Combinatorics with just 2 letters

Question

Using the letters A & B only to make two strings of 7 letters each, how many combinations are possible based on the following criteria?

Criteria 1: There must be at least 2 B's in each string.

Criteria 2: A can be on top or below A and B but B cannot be above or below another B.

Examples:

---

AAABBAA

BBBAAAB

---

ABABAAB

AABABAA

---

BAAABBB

ABBBAAA

---

BAAAAAB

ABAAABA

---

I think I understand how to calculate the number of combinations of the top string but I can't figure out how to link that to the bottom string.

Any help is greatly appreciated!

---

My solution for the top string combinations:

$\sum_{i=1}^{4} \binom{7}{2}\binom{5}{5-i}$

Where $\binom{7}{2}$ is the required 2 B's, and the $\binom{5}{5-i}$ is the other choices for the remaining letters.

Answer 1

Since no $B$ can be in the same column as another $B$ and there must be at least two $B$s in each row, there are at least four columns that contain a $B$. If there are exactly $k$ columns in which a $B$ occurs, there are $\binom{7}{k}$ ways of choosing which columns contain a $B$ and $2$ ways of choosing in which row that $B$ appears. From these, we must subtract those arrangements in which there are fewer than two $B$s in one the rows. Hence, the number of admissible arrangements is $$\sum_{k = 4}^{7} \binom{7}{k}\left[2^k - \binom{2}{1}\binom{k}{k} - \binom{2}{1}\binom{k}{k - 1}\right]$$ where the term $\binom{2}{1}\binom{k}{k}$ represents the number of ways we could place all $k$ $B$s in the same row and the term $\binom{2}{1}\binom{k}{k - 1}$ represents the number of ways we could place all but one of the $B$s in the same row.

Answer 2

I think the simplest way to approach this is to consider the cases "there are exactly $k$ Bs in the top string" for each $k$ separately, and add everything up in the end.

For example, if there are exactly $2$ Bs in the top string, then there are $\binom{7}{2}$ ways to choose the top string and $2^5 - 1 - 5$ ways to choose the bottom string (the two positions below the top string's Bs must be As, which leaves $5$ positions, at least two of which must be Bs).

You can continue for "exactly $3$ Bs in the top string," and so on.

This approach yields $$\sum_{k=2}^5 \binom{7}{k} (2^{7-k} - 1 - (7-k)).$$

I may be missing a more elegant approach though.

Answer 3

Suppose we initially drop the second condition and ask how many ways there are to arrange 7 A/B's in two rows with at least 2 B's in each row. In one row there are $2^7$ ways to arrange 7 A/B's. In $7$ of these there is only one B and in $1$ there are no B's. So one row can be arranged in $2^7-7-1$ ways, and two rows can be arranged in $N= (2^7-7-1)^2$ ways.

To find the number of these arrangements which satisfy the second condition (no two B's in the same column), we apply the Principle of Inclusion / Exclusion (PIE). Let's say an arrangement has "Property $i$" if column $i$ has two B's, for $i=1,2,3,\dots,7$. Let $S_j$ be the number of arrangements with $j$ of the properties, for $j=1,2,3,\dots,7$.

The case $j=1$ is a bit special. The single column can be chosen in $\binom{7}{1}$ ways. In the first row the remaining columns can be filled in $2^6$ ways, but one of these ways consists of only A's, violating the rule that the row must contain at least two B's. So the letters in the first row can be arranged in $2^6-1$ ways, and similarly for the second row. So $$S_1 = \binom{7}{1}(2^6-1)^2$$

The cases $S_2, S_3, \dots , S_7$ are a bit simpler than $S_1$, because when two or more of the columns contain B's, we have automatically satisfied the requirement that each row contain at least two B's. So $$S_j = \binom{7}{j} (2^{7-j})^2$$ for $j = 2,3,4, \dots,7$.

Finally, by PIE, the number of arrangements with none of the properties, i.e. the arrangements in which no column contains two B's, is $$\begin{align} N_0 &= N + \sum_{j=1}^7 (-1)^j S_j \\ &= (2^7-7-1)^2 - \binom{7}{1}(2^6-1)^2 + \sum_{j=2}^7 (-1)^j \binom{7}{j} (2^{7-j})^2 \\ &= (2^7-7-1)^2 - \binom{7}{1}(2^6-1)^2 + \sum_{j=0}^7 (-1)^j \binom{7}{j} (2^{7-j})^2 - \sum_{j=0}^1 (-1)^j \binom{7}{j} (2^{7-j})^2 \\ &= (2^7-7-1)^2 - \binom{7}{1}(2^6-1)^2 - (1-4)^7 - 4^7 + 7 \cdot 4^6\\ \end{align}$$ where we have applied the Binomial Theorem in the last line.

Answer 4

Another approach is to solve a more general problem, in which the lengths of the two strings are $r$. The original problem is then the case $r=7$.

Any single column consists of two letters, one of $$\alpha = \begin{vmatrix} A\\B \end{vmatrix} \qquad \beta = \begin{vmatrix}B\\A \end{vmatrix} \qquad \gamma = \begin{vmatrix} A\\A \end{vmatrix}$$ An acceptable arrangement of length $r$ is a string of $r$ "characters" taken from $\alpha, \beta$ and $\gamma$ with at least two $\alpha$'s and at least two $\beta$'s. The exponential generating function for the number of acceptable strings is $$\begin{align} f(x) &= \left( \frac{1}{2!} x^2 + \frac{1}{3!} x^3 + \frac{1}{4!} x^4+ \dots \right)^2 \left( 1 + x + \frac{1}{2!} x^2 + \dots \right) \\ &= (e^x-1-x)^2 \; e^x \\ &= e^{3x}+e^x+x^2 e^x-2e^{2x}-2xe^{2x}+2xe^x \end{align}$$ From this last expression we can find the coefficient of $(1/7!)x^7$, which is the solution to the original problem: $$7! \;[x^7] f(x) = 3^7 + 1 + 6 \cdot 7 - 2^8 - 7 \cdot 2^7 + 2 \cdot 7 =1092$$