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]
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.
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”
You forgot the exponent at the end of s[n_], should be (n/E)^n.
That’s all. Love your blogs! <(not factorial)
Thanks! I was afraid the computations were wrong, but looks like I just left off the
^nwhen I pasted the code.