kn choose n

Define

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

which is still a little hard to use.

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

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.

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

and

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.

The post kn choose n first appeared on John D. Cook.