Counting argument to compute the difference $\binom{n}{k} - \binom{\frac{n}{m}}{\frac{k}{m}}^m$

Question

I was wondering if there is counting argument to compute the following difference?

$$\binom{n}{k} - \binom{\frac{n}{m}}{\frac{k}{m}}^m,$$

where m divides k and n. Obviously $\binom{n}{k}$ is the number of ways to choose $k$ elements from a set of $n$ elements. The second term $\binom{\frac{n}{m}}{\frac{k}{m}}^m$ can be related to this. If we first split the $n$ elements into $m$ equal sized groups, then is the number of ways to choose $k$ elements such that exactly $\frac{k}{m}$ are chosen from each of the $m$ groups

Answer 1

So, if the set of $n$ elements can be split into $m$ groups of size $\frac{n}{m}$ each and also $m \mid k$, the difference $\displaystyle \binom{n}{k}-\binom{\frac{n}{m}}{\frac{k}{m}}^m $ is the number of ways to choose $k$ elements from the set of $n$ elements such that the numbers of elements chosen from each of the $m$ groups are not all the same.

Answer 2

Let's adjust things so all the values are integers.

$f(m, n, k) =\binom{mn}{mk} - \binom{n}{k}^m, $.

I have shown using Stirling (see below) that

$\binom{an}{bn} \approx \sqrt{\dfrac{ a}{2\pi bn(a-b)}}\left(\dfrac{a^a}{b^b(a-b)^{a-b}}\right)^n =\dfrac1{\sqrt{n}}s(a, b)r^n(a, b) $ with $r(a, b) =\dfrac{a^a}{b^b(a-b)^{a-b}} $ and $s(a, b) =\sqrt{\dfrac{ a}{2\pi b(a-b)}} =\sqrt{\dfrac{ 1}{2\pi b(1-b/a)}} $.

If $n = 1$ this is $\binom{a}{b} \approx s(a, b)r(a, b) $ so $(\binom{a}{b})^n \approx s^n(a, b)r^n(a, b) $.

Therefore

$\begin{array}\\ \dfrac{\binom{an}{bn}}{(\binom{a}{b})^n} &\approx \dfrac{s(a, b)r^n(a, b)}{\sqrt{n}s^n(a, b)r^n(a, b)}\\ &=\dfrac1{\sqrt{n}s^{n-1}(a, b)}\\ \end{array} $

Since $s(a, b ) < 1$, $\sqrt{n}s^{n-1}(a, b) \to 0$ as $n \to \infty$ so $\dfrac{\binom{an}{bn}}{(\binom{a}{b})^n} \to \infty$ as $n \to \infty$.

Note: Here is a proof of that assertion.

Since $n! \approx \sqrt{2\pi n}(n/e)^n$,

$\begin{array}\\ \binom{an}{bn} &=\dfrac{(an)!}{(bn)!((a-b)n!}\\ &\sim \dfrac{\sqrt{2\pi an}(an/e)^{an}} {(\sqrt{2\pi bn}(bn/e)^{bn})(\sqrt{2\pi n(a-b)}(((a-b)n)/e)^{(a-b)n})}\\ &= \sqrt{\dfrac{2\pi an}{2\pi bn2\pi n(a-b)}}\left(\dfrac{(an)^ae^be^{a-b}}{e^a(bn)^b((a-b)n)^{a-b}}\right)^n\\ &= \sqrt{\dfrac{ a}{2\pi bn(a-b)}}\left(\dfrac{a^an^a}{b^b(a-b)^{a-b}n^a}\right)^n\\ &= \sqrt{\dfrac{ a}{2\pi bn(a-b)}}\left(\dfrac{a^a}{b^b(a-b)^{a-b}}\right)^n\\ \end{array} $