Number of strings containing an adjacent pair of a specific character

Question

Problem Space

Given a set of strings $S$ of length $N$ where each character of $S$ is to be filled by choosing exhaustively from it's own alphabet subset $S_n$ where $n < N$.

For example, if $N=2$ and the alphabets are defined as follows: $$ S_0 = \{a, b, c\} \\ S_1 = \{a, b\} $$

Then: $$ S = \{aa, ab, ba, bb, ca, cb\} $$

I think another way of saying this is $S$ is the combinatorial product of all the alphabet subsets $S_n$ without computing $S$?

Problem

What is the algorithm for the number $P$ of strings in $S$ that contain adjacent pairs of a given character $C$?

Examples

Example 1

Given: $$ N=4 \\ C=a \\ S_0 = \{a, b, c\} \\ S_1 = \{a, b\} \\ S_2 = \{c\} \\ S_3 = \{a\} \\ $$

Then: $$ S = \{aaca, abca, baca, bbca, caca, cbca\} $$

Thus, the only string with adjacent pair of $a$ is $aaca$ thus $P=1$

Example 2

Given: $$ N=3 \\ C=a \\ S_0 = \{a, b\} \\ S_1 = \{a\} \\ S_2 = \{a, b\} $$

Then: $$ S = \{aaa, baa, aab, bab\} $$

Thus, the strings with adjacent pair of $a$ are $\{aaa, baa, aab\}$ thus $P=3$

Example 3

Given: $$ N=4 \\ C=a \\ S_0 = \{a, b\} \\ S_1 = \{a\} \\ S_2 = \{a, b\} \\ S_2 = \{a\} $$

Then: $$ S = \{aaaa, baaa, aaba, baba\} $$

Thus, the strings with adjacent pair of $a$ are $\{aaaa, baaa, aaba, baaa\}$ thus $P=3$

Answer 1

For any set $E$, with a finite number of elements, let $|E|$ denote the number of elements in $E$.

Assume that $N$ is a fixed positive integer, and that for $~k \in \{0,1,2, \cdots, (N-1)\},~$ that $|S_k| = i_k.$

So, the first conclusion is that the total number of different strings possible is

$$|S| = \prod_{k=0}^{N-1} i_k.$$

The particular problem posed has the specific flavor that you are not asking for the total number of $N$ character words where any consecutive duplications occur. Instead, you are asking for the total number of $N$ character words where (for example) the letter $A$ occurs in consecutive letters, at least once.

This means that if (for example) the letter $A$ occurs in five consecutive letters for a specific $N$ character string, that $N$ character string is still only counted once.

---

Assuming that the focus letter is "A", to attack this problem, two things are needed:

• Which of the sets $S_0, S_1, \cdots, S_{(n-1)}$ contain an "A".

• Some enumeration method. In my opinion, since $|S|$ is known, the easiest method is to enumerate the subset $T$ of $S$, where $T$ contains all strings that do not contain consecutive "A"'s, anywhere in the string. Then, the desired computation is $|S| - |T|$.

---

I think that there is so much variety possible with respect to the first bullet point above, that I (personally) am unable to create a generic formula. Therefore, the best that I can do is to illustrate my approach with a specific sample.

Suppose that $N = 20$, and (for simplicity) that for $k \in \{0,1,\cdots,19\}$, that $|S_k| = (k+1)$. This implies that $|S| = 20!.$

Consider the specific subsets $S_0, \cdots, S_{n-1}$ that happen to contain an "A" as forming islands, where islands of size $(1)$ can be ignored.

For example, if an "A" is present in $S_0, S_2, S_3$, then you can ignore the "A" in $S_0$, but can not ignore the "A"'s in $S_2, S_3$.

I am going to assume that the are exactly $(4)$ islands, whose size is greater than $(1)$. For illustration, assume that the islands are

• $S_2,S_3$ : size = $(2)$.

• $S_5,S_6,S_7$ : size = $(3)$.

• $S_9,S_{10},S_{11},S_{12}$ : size = $(4)$.

• $S_{14},S_{15},S_{16},S_{17},S_{18}$ : size = $(5)$.

So, I am assuming that none of the following sets have an "A":
$S_1, S_4, S_8, S_{13}, S_{19}.$
It is irrelevant whether $S_0$ contains an "A", because $S_1$ is assumed to not contain an "A".

Keeping in mind that the final computation will be

$$(20)! - |T|,$$

the first factor involved in the computation of $|T|$ is

$$T_1 = 1 \times 2 \times 5 \times 9 \times 14 \times 20.$$

That is, $T_1$ represents the cross multiplication of all of the subsets that are not part of any island of size greater than $(1)$.

For $k \in \{1,2,3,4\}$, let $R_k$ denote the number of ways that Island K can produce a string, using one letter from each of the pertinent groups, without consecutive "A"'s.

Then, $$T = T_1 \times R_1 \times \cdots R_4,$$

so, the question is reduced to enumerating $R_k ~: k \in \{1,2,3,4\}$.

Note that there are (in effect) two variables that have to be considered, when enumerating $R_k$

• The size of the island (i.e. how many subsets it contains).

• The specific size of each subset.

---

$\underline{\text{Is elegance possible?}}$
The remainder of this answer is very inelegant. In particular, the computations of $R_3$ and $R_4$ are very cumbersome.

Let "b" refer to any character other than an "A".

In striving for elegance, it is insufficient (for example) to enumerate the number of patterns (e.g. A_b_A_A_A) that occur in a $5$ character string that contains two consecutive "A"'s, at least once.

The reason is that (for example), the enumeration of A_b_A_A_A will be different from the enumeration of A_A_b_A_A, because the 3rd member of the 5 island group will (potentially) have a different number of elements than the 2nd member of the group.

---

$\underline{\text{Computation of} ~R_1}$
$S_2,S_3$ have $3$ and $4$ elements respectively. From these $(3 \times 4) = 12$ possible two character strings, only the string "AA" must be omitted.

Therefore

$$R_1 = (12 - 1) = 11. \tag1 $$

---

$\underline{\text{Computation of} ~R_2}$
$S_5,S_6,S_7$ have $6,7$ and $8$ elements respectively. From these $(6 \times 7 \times 8) = 336$ possible three character strings, how many of these strings contain at least one occurrence of "AA"?

The following patterns have to be enumerated and deducted:

• AAb : $~(8-1) = 7~$ strings.
• bAA : $~(6-1) - 5~$ strings.
• AAA : $~1~$ string.

Therefore,

$$R_2 = 336 - (7 + 5 + 1) = 323. \tag2 $$

---

$\underline{\text{Computation of} ~R_3}$
$S_9,S_{10},S_{11},S_{12}$ have $10,11,12,$ and $13$ elements respectively. From these $(10 \times 11 \times 12 \times 13) = 17160$ possible four character strings, how many of these strings contain at least one occurrence of "AA"?

To enumerate the number of four character strings that must be deducted, note that there will be either $0$ "b"'s, $1$ "b", or $2$ "b"'s.

$0 ~$ "b"'s:
AAAA can only occur in $1$ way.

$1 ~$ "b":
Any of the $4$ members of the group can be the off member.
Enumeration is $(10-1) + \cdots + (13-1) = 42.$

$2 -$ "b"'s:
The computation here is:

bbAA $~: ~(10 - 1) \times (11 - 1) = 90.$
bAAb $~: ~(10 - 1) \times (13 - 1) = 108.$
AAbb $~: ~(12 - 1) \times (13 - 1) = 132.$
$90 + 108 + 132 = 330.$

Therefore,

$$R_3 = 17160 - (1 + 42 + 330) = 16787. \tag3 $$

---

$\underline{\text{Computation of} ~R_4}$
$S_{14},S_{15},S_{16},S_{17},S_{18}$ have $15,16,17,18$ and $19$ elements respectively. From these $(15 \times 16 \times 17 \times 18 \times 19) = 1395360$ possible five character strings, how many of these strings contain at least one occurrence of "AA"?

To enumerate the number of five character strings that must be deducted, note that there will be either $0$ "b"'s, $1$ "b", $2$ "b"'s or $3$ "b"'s.

$0 ~$ "b"'s:
AAAAA can only occur in $1$ way.

$1 ~$ "b":
Any of the $5$ members of the group can be the off member.
Enumeration is $(15-1) + \cdots + (19-1) = 80.$

$2 -$ "b"'s:
Of the $~\displaystyle \binom{5}{2} = 10$ ways that the off elements can occur, only AbAbA will prevent two consecutive A's.

So, from the set $\{14,15,16,17,18\}$, you want the sum of $(9)$ terms where each term represents the product of two of the factors. Only the $(15 \times 17)$ factor is excluded.

The shortcut is:
$(14) \times (15 + 16 + 17 + 18) = 924.$
$(15) \times (16 + 18) = 510.$
$(16) \times (17 + 18) = 560.$
$(17 \times 18) = 306.$

$924 + 510 + 560 + 306 = 2300.$

$3 -$ "b"'s:
bbbAA $~:~ 14 \times 15 \times 16 = 3360.$
bbAAb $~:~ 14 \times 15 \times 18 = 3780.$
bAAbb $~:~ 14 \times 17 \times 18 = 4284.$
AAbbb $~:~ 16 \times 17 \times 18 = 4896.$
$3360 + 3780 + 4284 + 4896 = 16320.$

Therefore,

$$R_4 = 1395360 - (1 + 80 + 2300 + 16320) = 1376659. \tag4 $$

---

Final computation:

$$T_1 = 1 \times 2 \times 5 \times 9 \times 14 \times 20.$$

$$R_1 = 11.$$

$$R_2 = 323.$$

$$R_3 = 16787.$$

$$R_4 = 1376659.$$

$$|T| = T_1 \times R_1 \times \cdots \times R_4.$$

The total number of $(20)$ character strings that do contain at least one occurrence of "AA", somewhere in the string is

$$(20)! - |T|.$$

Answer 2

I think this works:

$$ \sum_i [C \in Si ][ C \in S_{i+1}] * \left\{ \prod_j |S_j|^{[j \neq i][j \neq i+1]} - \sum_k [k > i][C \in Sk ][ C \in S_{k+1}] * \left(\prod_l |S_l|^{[l > k+1]}\right) \right\} $$

(The square brackets are Iverson brackets).

A quick test in Python of the given examples:

from math import prod

def countAdjacent(subsets, c):
    n = len(subsets)
    return sum([prod([len(subsets[j]) for j in range(0, n) if (j != i and j != i+1)])
                - sum([prod([len(subsets[l]) for l in range(k+2,n-1)])
                       for k in range(i+1,n-1) if (c in subsets[k] and c in subsets[k+1])])
                for i in range(0, n-1) if (c in subsets[i] and c in subsets[i+1])])

print ('ex1: P = %d' % countAdjacent([[ 'a', 'b', 'c' ],
                                      [ 'a', 'c' ],
                                      [ 'c' ],
                                      [ 'a' ]],
                                     'a'))

print ('ex2: P = %d' % countAdjacent([[ 'a', 'b' ],
                                      [ 'a' ],
                                      [ 'a', 'b' ]],
                                     'a'))

print ('ex3: P = %d' % countAdjacent([[ 'a', 'b' ],
                                      [ 'a' ],
                                      [ 'a', 'b' ],
                                      [ 'a' ]],
                                     'a'))