Theorem 3

F(n, m) = (n+m)! / (n!m!)

Proof

There were some preliminary thoughts on this, but here is the proof.

Lemma 3.1

F(n,m) is the number of terms in the polynomial over x0, ... xn with terms of all orders up to m, after collecting repeats.

Imagine we introduce a new variable d, and look at all the terms of order m ONLY in the polynomial over d, x0, ... xn. Call the number of terms in this polynomial G(n, m).

Then this new polynomial has the same number of terms as our original:

F(n, m) = G(n, m)

Proof of Lemma 3.1

If we set d = 1, we end up with all the same terms as our original polynomial: the d^m term becomes constant, the x0d^(m-1) term becomes x0, and so on. The terms containing d become the terms of lower orders, and those not containing d remain of order m.

Lemma 3.2

G(n, m) = n+m choose m

Proof of Lemma 3.2

The number of terms in a polynomial over N variables where all terms are of order exactly m is:

N+m-1 choose m

since this is the formula for choosing m things from N things with replacement (more info).

But this is what we are doing to find G, with N = n+1 in this case, since we added the variable d, so the result follows:

G(n, m) = n+m choose m

The final result follows from these two lemmas, since:

F(n, m) = G(n, m) = n+m choose m = (n+m)! / (n!m!)

Back to NumberOfCoefficients.