Number of strings containing an adjacent pair of a specific character 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$
 A: 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'))

