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!
Best Answer
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).$$