10
$\begingroup$

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

m = 5, n = 4.

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.

m = 5, n = 3

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

m = 5, n = 1

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!

$\endgroup$
4
  • $\begingroup$ great diagrams, how did you created them? $\endgroup$ – RE60K Dec 30 '14 at 17:12
  • $\begingroup$ Nothing fancy. I have solved some of the smaller problems by hand using excel. The pictures above are just screenshots from my worksheet. $\endgroup$ – Frustrated Jan 7 '15 at 19:00
  • $\begingroup$ You seem to allow "leftover" items when $k$ does not divide $n$. However, it's not clear from your examples what your general rule is. One possibility is that all groups must have size $k$ except that when $k$ doesn't divide $n$, you're allowed one additional group of size $n$ mod $k$. Is this what you intend? $\endgroup$ – Tad Jan 20 '15 at 5:18
  • $\begingroup$ I should have ended the title with "in the largest group". Any combination of groups smaller than $k$ is valid as a solution as long as there is one or more groups of size $k$. $\endgroup$ – Frustrated Jan 20 '15 at 7:36
1
$\begingroup$

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).$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.