Finding the number of arrangements of $n$ binary elements ($a$, $b$) with a maximum of $k$ repeating consecutive elements of one type [duplicate]

Question

Here's an example

For $n = 4$ and $k = 1$, there are 8 possible arrangements:

$a\ a\ a\ a$

$a\ a\ a\ b$

$a\ a\ b\ a$

$a\ b\ a\ a$

$b\ a\ a\ a$

$b\ a\ b\ a$

$b\ a\ a\ b$

$b\ a\ b\ a$

with $b$ being the element that can't have more than $k$ consecutive appearances.

I'm not really well-versed in combinatorics, so $2^n$ being the total number of arrangements is the only piece of info I came up with.

Anyway, this is actually a programming challenge from one of those competitive programming sites, but I wanna get a grasp of the math behind the idea before thinking about implementation methods, so I figured I'd ask things here. Also, the input range for both $n$ and $k$ is $[1, 10^6]$ so a dynamic programming approach is the way to go.

Answer 1

The dynamic programming states are :

$(i,j)$= number of valid strings of length $i$ ending with character $j$. Assume $j$ to be $0$ for $a$ and $1$ for $b$.

Now, consider a compressed version of the string , it will be like $\{ (a,x),(b,x'),(a,z),(b,z') \}$ and so on, or $\{ (b,x),(a,x'),(b,z),(a,z') \}$ and so on.

For example, the set of pairs : $ \{ (a,1),(b,2),(a,1) \} $ would indicate the string :

$ abba $

Now let's call $q_{i}$ the second member of the $i^{th}$ pair in the set. You want the sum of all $q_{i}$ to be $N$, where $N$ is the length of the string , each $q_{i}$ is positive, and each $q_{i}$ belonging to a $'b'$ is $ \le K $.

So, the dyanmic programming transisions would be :

$ d[i][0]= \sum_{j=0}^{i-1} d[j][1] $,

$ d[i][1]= \sum_{j=i-k}^{i-1} d[j][0] $

with the base case being $d[0][0]=d[0][1]=1$

The answer will be sum of $ d[N][0]$ and $d[N][1]$. Try and think of how you can use prefix sums to optimize these transitions to work in $O(N)$

I personally feel this is a standard problem, and having many queries for different $K$ with fixed $N$ would make the problem much more interesting and harder.

Answer 2

I take it you're asking how to come up with a mathematical formula for the number of words of a particular length that don't violate the restriction about one letter appearing too many times in a row. It turns out there is not a closed-form formula for this (for general $n$ and $k$), but there are general methods that give pretty good approximations.

So, let $a_n$ be the number of words of length $n$ from the two-letter alphabet $\{a,b\}$ so that the $b$ never appears more than $k$ times in a row (and call these type of words valid). Each valid word can be uniquely decomposed by stripping off the at most $k$ $b$'s at the beginning of the word, which must be followed by a single $a$, which is then followed by a shorter valid word. Therefore, $$a_n=\sum_{j=0}^ka_{n-(j+1)}\text{ for }n\ge k+1 $$ and $$a_0=1,\; a_1=2,\;\ldots\;,a_k=2^k.$$ This recurrence relation is easy to code up, if that's all you want to do. However, your question comes down to solving this recurrence relation. It is of $k$th order, linear, and has constant coefficients. (If $k=1$, it gives the Fibonacci numbers.) There are many ways to solve recurrence relations of this type---my personal favorite is with generating functions. Whatever the $a_n$'s turn out to be, you define the generating function $f(x)=\sum_{n\ge0}a_nx^n$ and then transform the recurrence relation to a statement about the generating function itself. In this case it turns out to be $$f(x)-1=\sum_{j=0}^k x^{j+1}f(x). $$ Solving this gives $$f(x)=\frac{1-x}{1-2x+x^{k+2}}.$$ The last step in order to get a formula for $a_n$ is to extract the coefficient of $x^n$ in $f(x)$. Unfortunately, you can't do this exactly since the denominator of $f$ doesn't factor nicely. However, if you want to follow up the problem, you can get a reasonable approximation by getting a good estimate for the smallest root $\alpha$ of $1-2x+x^{k+2}$, say with Newton's method, which is just shy of $1/2$. Then, $a_n\sim 1/\alpha^n$.