Partitioning a Queue

Question

Imaging a situation that we have n people in a queue and each people represent with number 1 and I want to partition the queue in smaller part, there are several ways to partition the queue.
For instance, a queue of size 3 can be partitioned into $1+2, 2+1, 1+1+1, 3 $. It is easy to prove that there are $2^{n-1}$ ways to partition a queue of size n.
The problem becomes a little complicated, when we are not allowed to use parts whose sizes are in some given set S.
For instance, if S is the set of even numbers, a queue of size 4 can be partitioned in 3 ways, namely $1+1+1+1, 1+3,3+1$.
Now I want to count the number of ways to partition a queue of size n, with an additional condition that the size of no part should be in a given arithmetic sequence ${m+ik|i=0, 1,…}$ for the given m,k.

Answer 1

Let $S\subset\mathbb{N}$ be the subset of valid block sizes (in the example you gave, $S$ is the set of odd numbers.) Let $g(z)$ be the generating function for $S$; that is, $g(z)=\sum_{k\in S}z^k$. Let $a_n$ be the number of partitions of a queue of length $n$; note that $a_0=1$ since the empty queue can be partitioned in exactly one way (the empty partition). We set $a_n=0$ if $n<0$.

We get a recurrence for $a_n$ by considering the possible sizes of the last block: $$a_n = [n=0] + \sum_{k\in S} a_{n-k};$$ multiplying by $z^n$ and summing over $n$ leads to the functional equation $$f(z) = 1 + \sum_{k\in S} z^k f(z),$$ from which we find $$f(z) = \frac1{1-g(z)}.$$

Note that $g(z)$ is a rational function whenever $S$ is a union of a finite set and finitely many arithmetic sequences, in which case $f(z)$ is rational as well. This leads to a closed form for $a_n$ in such cases; how "closed-form" it is depends on how well you can solve for the roots of the denominator of $f(z)$.

The solution is instructive for the partitions into odd pieces: we get $$\begin{align} f(z)&=\frac1{1-(z+z^3+z^5+\cdots)}\\ &=\frac1{1-z/(1-z^2)}\\ &=\frac{1-z^2}{1-z-z^2}. \end{align}$$ We recognize the denominator as the Fibonacci recurrence, and indeed $$\frac{1-z^2}{1-z-z^2} = 1 + z + z^2 + 2z^3 + 3z^4 + 5 z^5 + \cdots$$ so that $a_n=F_n$ if $n>0$ (but $a_0=0$).

In the specific case you're asking for, $S$ is the complement in $\mathbb{N}$ of the arithmetic sequence $\{m+ik\mid i\ge0\}$, so we have $$f(z) = \frac1{1-\left(\frac1{1-z} - \frac{z^m}{1-z^k}\right)}.$$