# Generating function of words in a binary alphabet counting blocks and appearances

Given the binary alphabet {a,b}, I'm trying to find the generating function that distinguishes, for all words of fixed length $n$, the count of blocks of a's and the number of a's. Let $x^p$ count the number of blocks of size $p$ and $y^q$ count the number of a's in a word. As a first example, take the word:

abbaaabaabaabba


This has nine a's broken up into a two blocks of length one, two blocks on length two and a block of length three. This would contribute to the generating function a term of $y^9(2x + 2x^2 + x^3)$.

As a second example, with $n=3$ there are eight words and the term associated with each of them is:

bbb = 1
bba = xy
bab = xy
baa = (xy)^2
abb = xy
aba = 2xy^2
aab = (xy)^2
aaa = (xy)^3


Note that the term aba = 2xy^2 is not a typo, there are two blocks of length one. With $A$ as the generating function, this would give: $A_3(x,y) = 1 + 3xy + (2x + 2x^2)y^2 + y^3x^3$. I've been able to come up with a special case of this, when we don't care about the counts of the a's (equivalent to setting all $y=1$). This restricted form $B_n(x) = A_n(x,y=1)$ is:

$$B_n = B_{n-1} + x^n + \sum_{j=0}^{n-2} ( 2^j x^{n-j-1} -1 + B_j )$$

with $B_0 = 1$. Is there such a formula for $A_n$, or even better, a non-recursive closed form of $A_{npq}$?

-
I don't understand what you're asking for. What is the power of x counting? What is the power of y counting? And why do you need the 2 in the term associated to aba? – Qiaochu Yuan Oct 10 '10 at 21:05
@Qiaochu I've added another example that hopefully makes the question a bit clearer. – Hooked Oct 10 '10 at 21:29

I know this is a very old question, BUT here's an answer:

First, let me define four functions...

Let $\text{part}_{k}(n)$ returns the $k$th lexicographic partition of $n$. For instance, $\text{part}_{0}(5) = \langle 5 \rangle$, $\text{part}_{1}(5) = \langle 4,1 \rangle$, and $\text{part}_{4}(5) = \langle 2,2,1 \rangle$.

Furthermore, I define $\text{part}_{k,p}(n)$ to be the $p$th element of $\text{part}_{k}(n)$. For example, $\text{part}_{4,2}(5) = 1$.

Next, let $\text{len}(\text{part}_{k}(n))$ return the number of elements in $\text{part}_{k}(n)$. Hence, $\text{len}(\text{part}_{4}(5)) = 3$.

Finally, let us define $\text{count}(\text{part}_{k}(n), x)$ to be the number of elements in $\text{part}_{k}(n)$ with the value of $x$. Thus, $\text{count}(\text{part}_{4}(5), 2) = 2$.

Also, here are a couple variable definitions.

$w =$ number of characters in word.
$n =$ number of partitions of $w$.

Now we can get started on the formula! :P

I chose to count by partitions, as I'm sure my function definitions have implied. I noticed that the way you put your problem meant that as long as there was at least one b between each block of a's, then there could be any number of b's elsewhere and the function for that particular situation would be unchanged. In other words, the function in x and y of "aaabbabbba" would be the exact same as for "baaabbbaba".

First, I counted the number of ways to arrange the blocks of a's. This is equivalent to having a row of b's and blanks and counting how many ways to choose which blanks to put the blocks of a into. For example, two blocks of a's ("aaa" and "aa", say) can be put into 6 blanks with 5 b's between them ("_b_b_b_b_b_") in $\binom{6}{2} = 15$ ways (6 blanks, 2 blocks). In general, the number of blanks is the number of b's plus one, which is
$\displaystyle \binom{w+1-\text{len}(\text{part}_{i}(k))}{\text{part}_{i}(k)}$
where $i$ is the index of the particular partition and $k$ is the number of a's.

Next, we need to multiply by the number of ways to arrange the blocks amongst themselves. Disregarding duplicates, this is the factorial of the number of blocks, which is $\text{len}(\text{part}_{i}(k))!$. To account for the duplicates, we need to divide by the product of the factorials of the number of times each element repeats (wow, that was wordy). In all, it looks like this:
$\displaystyle \frac{\text{len}(\text{part}_{i}(k))!}{\displaystyle \prod_{j=0}^{k} \Bigl( \text{count}(\text{part}_{i}(k),j)! \Bigr)}$

Multiplying the two gives us the coefficient for each piece. The x's are given by $\displaystyle \sum_{q=0}^{\text{len}(\text{part}_{i}(k))} x^q$ and the y's are given by $y^k$. Thus, the whole equation is:

$A_{w}(x,y) = \displaystyle \sum_{k=0}^{w} \left( y^k \; \sum_{i=0}^{n} \left( \binom{w+1-\text{len}(\text{part}_{i}(k))}{\text{part}_{i}(k)} \frac{\text{len}(\text{part}_{i}(k))!}{\displaystyle \prod_{j=0}^{k} \Bigl( \text{count}(\text{part}_{i}(k),j)! \Bigr)} \right) \left( \sum_{q=0}^{\text{len}(\text{part}_{i}(k))} x^q \right) \right)$

Yep. Quite a monster. But it's not that hard to program, although it definitely would be quite tedious to do by hand.

-