kn choose n

Posted on by John

Define

f(n, k) = \binom{kn}{n}
These binomial coefficients come up frequently in application. In particular, they came up in the previous post. I wanted to give an asymptotic approximation for f(n, k), and I thought it might be generally useful, so I pulled it out into its own post.

I used Mathematica to calculate an approximation. First, I used Stirling’s approximation.

    s[n_] := Sqrt[2 Pi n] (n/E)^n

and then I used it to approximate f(n, k).

    Simplify[ s[k n] / (s[(k-1) n] s[n]), 
         Assumptions -> Element[k, Integers] && k > 0]

Applying TeXForm to this gives

f(n,k) \approx \frac{(k-1)^{-k n+n-\frac{1}{2}} k^{k n+\frac{1}{2}}}{\sqrt{2 \pi n}}

which is still a little hard to use.

By rearranging the terms we can make this approximation easier to understand.

f(n,k) \approx \sqrt{\frac{k}{k-1}} \,\,\frac{1}{\sqrt{2\pi n}} \,\,\frac{k^{kn}}{(k-1)^{(k-1)n}}

These three terms are arranged in order of increasing importance. If k is fixed and n grows, the first term is constant, the second term decreases slowly, and the third term grows exponentially.

When k = 2, the approximation is particularly simple.

f(n,2) \approx \frac{4^n}{\sqrt{\pi n}}

For larger the expressions are a little more complicated, but a couple examples will illustrate the pattern.

f(n,3) \approx \sqrt{\frac{3}{2}} \,\, \frac{1}{\sqrt{2\pi n}} \,\,\frac{3^{3n}}{2^{2n}}

and

f(n,4) \approx \sqrt{\frac{4}{3}} \,\, \frac{1}{\sqrt{2\pi n}} \,\,\frac{4^{4n}}{3^{3n}}

For an application of f(n,2), see How many ways you can parenthesize an expression?

For an application of f(n, 3) and f(n, 4), see the previous post.

2 thoughts on “kn choose n”

  2. John

    Thanks! I was afraid the computations were wrong, but looks like I just left off the ^n when I pasted the code.

Comments are closed.