F(n, m) = (n+m)! / (n!m!)
(Benjamin Balaam, 03/08/2025)
The number of coefficients can clearly be seen as the number of possible combinations of the variables which is a valid term for the polynomial.
Now if we consider a single term in a polynomial in n variables of order m, we can think of it as m sub-terms multiplied together, each one can be one of the n variables, or 1.
This gives all possible terms, but it is not unique as any two sub-terms which are the same can be swapped without affecting the result, so we instead consider it is a list of these m sub-terms with markers between them telling us when the variable changes, so anything before the first marker is a 1, anything between the first and second markers is an x, then y between the second and third and so on.
And clearly we must then have n markers we can place anywhere. If we now consider this as a list of m+n "things" where m are sub-terms and n are markers, then we can uniquely define each term as which of these m+n "things" are markers, the order of the markers clearly does not matter, so we are choosing n of the m+n "things" to be markers, this clearly leads to m+n choose n, which is (m+n)!/(m!n!).
This is a standard method from combinatorics known as the "Stars and Bars" method, further research can be done here: Stars and bars (Wikipedia).
Back to NumberOfCoefficients.