Skip to content

Instantly share code, notes, and snippets.



Last active Sep 3, 2019
What would you like to do?
Strings with prefix imbalance

Let's define $a_{n,m}$ to be the number of words of length $n$ with a surplus of $m$ A's. E.g. with $k=2$, AAAB would contribute $1$ to $a_{4,1}$; with $k=3$ it would contribute $1$ to $a_{4,0}$.

Given a word of length $n-1$ we can always append an A to get a valid word; we can append a B to get a valid word iff the surplus is at least $k$. So if we set up the generating function $$f(x,z) = \sum_{n \ge 0} \sum_{m=0}^n a_{n,m} x^n z^m$$ we find that $$f(x, z) = 1 + xz f(x, z) + xz^{-p} \sum_{n \ge 0} \sum_{m=p}^n a_{n,m} x^n z^m \tag{1}$$ which doesn't look very promising.

However, I believe Deutsch proved that this kind of regression always gives a Riordan array, so let's assume that we can write $f(x, z)$ in the form $$f(x, z) = \sum_{m \ge 0} z^m d(x) (xh(x))^m \tag{2}$$

Useful observation: the length minus the surplus is always a multiple of $k+1$ (easily shown by induction), so $d(x)$ only has non-zero coefficients at powers of $x^{k+1}$, or $d(x) = d_k(x^{k+1})$.

Useful observation: if we extract just the terms with $z^0$ from $(1)$, we get $$d(x) = 1 + x \sum_{n \ge 0} a_{n,p} x^n$$ And if we extract just the terms with $z^p$ from $(2)$ we get $$\sum_{n \ge 0} a_{n,p} x^n = d(x) (xh(x))^p$$ So, combining them,

$$d(x) = \frac{1}{1 - x^{p+1} h(x)^p} \tag{3}$$

Applying a similar idea with $z^1$ and $z^{p+1}$, we get $$d(x)(xh(x)) = x d(x) + x d(x) (xh(x))^{p+1}$$ or $$h(x) = \frac{1}{1 - x^{p+1} h(x)^{p+1}} \tag{4}$$

Combining $(3)$ and $(4)$ and rearranging we get $$d(x) = \frac{h(x)^2}{1 - h(x) + h(x)^2}$$

Experimentation: calculating the first few dozen terms and doing a polynomial division to find $h(x)$, followed by an OEIS search, it seems that, denoting $h(x) = h_k(x^{k+1})$,

$$ h_1(x) = \textrm{A000108} = \sum_n \frac{1}{n+1} \binom{2n}{n} x^n \ h_2(x) = \textrm{A001764} = \sum_n \frac{1}{2n+1} \binom{3n}{n} x^n \ h_3(x) = \textrm{A002293} = \sum_n \frac{1}{3n+1} \binom{4n}{n} x^n $$

There's a pattern emerging here... For now, let's conjecture that $$h(x) = \sum_n \frac{1}{kn+1} \binom{(k+1)n}{n} x^{(k+1)n}$$

To get the number of words of length $n$, we sum over the surpluses, which is easily done by taking $f(x, 1)$. So if $g(x)$ is the generating function which we were really after all along, $$g(x) = \sum_{m \ge 0} d(x) (xh(x))^m = \frac{d(x)}{1 - xh(x)} = \frac{h(x)^2}{(1 - h(x) + h(x)^2)(1 - xh(x))} \ = \frac{h(x)^2}{1 - (x+1)h(x) + (x+1)h(x)^2 - xh(x)^3} $$

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment