Number of ways to arrange $n$ items in $m$ positions having exactly $k$ items adjacent to each other

Question

It was over 20 years since I studied maths and I am stuck. I'd really appreciate some help understanding this (probably quite simple) problem.

I have $n$ items that I can place on $m$ positions. $m$ ≥ $n$. The total number of combinations is the old and trusty ${m \choose n}$, but I also need to partition the combinations on k - the number of items directly adjacent to each other

What I am looking for is best shown with a couple of examples.

Five positions and four items can be combined in two ways when $k$ is four, two ways when $k$ is three and one way when $k$ is two

.

Five positions and three items can be combined in three ways when $k$ is three, six ways when $k$ is two and one way when $k$ is one.

Five positions and one item can be combined in five ways when $k$ is one.

What I am trying to find is a function $f(m, n, k)$ that give me the number of combinations for some value $k$. For example:

$f(5, 3, 3)$ => $3$
$f(5, 3, 2)$ => $6$
$f(5, 3, 1)$ => $1$

Of course, adding up the number of combinations for all valid $k$ is ${m \choose n}$.

Just by toying with pen and paper I have observed some edge cases

$f(x, x, x)$ => $1$
$f(x, 1, 1)$ => $x$
$f(x, y, y)$ => $x-y+1$

Help me, please!

Answer 1

There is no simple formula, but you can use a simple recursive property to efficiently compute $f$.

Border conditions :

1. if $k>n$ or $n>m$ then $f(m,n,k)=0$

2. if $k=m=n$ then $f(m,n,k)=1$

Then, any valid (m,n,k) configurations either :

1. begins with $i$ occupied cells followed by an empty cell and a $(m-i-1,n-i,k)$ configuration (for any $i\le k$)
2. begins with $k$ occupied cells followed by an empty cell and a $(m-k-1,n-k,i)$ configuration (for any $i<k$)

$$f(m,n,k)=\sum_{i=0}^kf(m-i-1,n-i,k)+\sum_{i=0}^{k-1}f(m-k-1,n-k,i)$$

Using that, you can very efficiently compute $f$ with some dynamic programming. An example in python :

_db={}
def f(m,n,k) :
    if k>n or n>m: return 0
    if k==n and k==m : return 1
    if (m,n,k) in _db : return _db[(m,n,k)]
    _db[(m,n,k)]=sum(f(m-i-1,n-i,k) for i in range(k+1))
    _db[(m,n,k)]+=sum(f(m-k-1,n-k,i) for i in range(k))
    return _db[(m,n,k)]

And then compute $f(300,60,8) = 3093843836691461760481283005507531400353771346949728892427692$ in a few seconds.

Answer 2

It suffices to consider the function $g(m,n,k)$, which counts the number of ways to select $n$ positions from $m$ such that at most $k$ consecutive positions are chosen; note that $f(m,n,k)=g(m,n,k)-g(m,n,k-1)$. The function $g$ satisfies a simpler recurrence than $f$, namely $$g(m,n,k)=\begin{cases} {m\choose n},&n\le k\\ \sum_{r=1}^{k+1} g(m-r,n-r+1,k),&n>k \end{cases}$$ where the sum arises from breaking into cases according to the location of the last vacant cell.

By induction, we can show that, for fixed $n$ and $k$, $g(m,n,k)$ is a polynomial in $m$ of degree $n$, for $m>k$. This is clear for $n\le k$ by the initial conditions. For $n>k$ we see that $g(m,n,k)-g(m-1,n,k)$ is a sum of polynomials of degree $n-1, n-2, \ldots, n-k$, i.e. $g(m,n,k)-g(m-1,n,k)$ has degree $n-1$. So finite difference calculus tells us $g(m,n,k)$ is a degree $n$ polynomial; indeed, it tells us how to write down this polynomial explicitly, having used the recurrence to generate $n+1$ terms. That may suffice for your needs.

Alternatively, you can get sort of a closed form using generating functions. Denote empty cells by $0$ and filled cells by $1$. For each $r$ with $0\le r\le k$, define an $r$-block to be $r$ $1$'s followed by a $0$. If we temporarily append an extra vacant cell to the end, each valid configuration can be uniquely described by laying down a sequence of $r$-blocks, for various $r$, so that the total number of $1$'s is $n$ and the total number of cells is $m+1$. Note that in order to get density $n$, we need to use $m+1-n$ blocks. Standard exponential generatingfunctionology implies that $g(m,n,k)$ is the coefficient of $x^{m+1}\,z^{m+1-n}/(m+1-n)!$ in $$ G_k(x,z) := {\rm exp}\left( z(x + x^2 + \cdots + x^{k+1})\right).$$

(Basically, $z$ tags the total number of blocks, so the g.f. is exponential in $z$, and $x$ tags the lengths of the blocks. The $m$ turns into $m+1$ because of the extra empty cell we added.) Bringing things full circle, this says

$$ f(m,n,k) = \left[\frac{x^{m+1}\,z^{m+1-n}}{(m+1-n)!} \right]\left( G_k(x,z) - G_{k-1}(x,z)\right).$$