Quintinomial Coefficients

The coefficients in the expansion of $(x+1)^k$ are called binomial coefficients.
Analoguously the coefficients in the expansion of $(x^4+x^3+x^2+x+1)^k$ are called quintinomial coefficients. (quintus= Latin for fifth).

Consider the expansion of $(x^4+x^3+x^2+x+1)^3$:
$x^{12}+3x^{11}+6x^{10}+10x^9+15x^8+18x^7+19x^6+18x^5+15x^4+10x^3+6x^2+3x+1$
As we can see $7$ out of the $13$ quintinomial coefficients for $k=3$ are odd.

Let $Q(k)$ be the number of odd coefficients in the expansion of $(x^4+x^3+x^2+x+1)^k$.
So $Q(3)=7$.

You are given $Q(10)=17$ and $Q(100)=35$.

Find $\sum_{k=1}^{18}Q(10^k)$.

The coefficients in these polynomial expansions are counted by the number of ways to distribute the exponents among the five terms of each polynomial. The binomial theorem generalizes to:

(x^4 + x^3 + x^2 + x + 1)^k = sum(C(k, n_4, n_3, n_2, n_1, n_0)*(x^4)^n_4*(x^3)^n_3*(x^2)^n_2*x^n_1*1^n_0) for all tuples (n_4, n_3, n_2, n_1, n_0) such that n_4 + n_3 + n_2 + n_1 + n_0 = k

The number Q(k) would then be the sum of all coefficients C(k, n_4, n_3, n_2, n_1, n_0) that are odd for a given k.

Here’s the trick: Notice that, when doing these counts, each of x^4, x^3, x^2, x and 1^k must have their corresponding n_i either even (when they are raised to an even power) or odd (when they are raised to an odd power). But in order for the total polynomial to have its exponent as k, the sum of these n_i (which must either be even or odd) must also be odd.

We can translate this problem into a counting problem in base 2 under these restrictions.

It is known that the total number of coefficients in the expansion of (x^4 + x^3 + x^2 + x + 1)^k, is the number of solutions to n_4 + n_3 + n_2 + n_1 + n_0 = k, which is C(k + 4, 4). In our base 2 interpretation, the number of coefficients C(k, n_4, n_3, n_2, n_1, n_0) that add to k is the number of k-digit binary strings.

What about odd coefficients? In our base 2 interpretation, the number of odd coefficients is simply the number of k-digit binary strings with an odd number of 1’s. And here the Hamming weight of a k-digit binary string is simply the number of 1’s in the string. So Q(k) is just the number of k-digit binary strings with an odd Hamming weight.

Since the Hamming weight of a k-digit binary string is either even or odd, we know that Q(k) + P(k) = 2^k, where P(k) is the number of k-digit binary strings with even Hamming weight. Now the intuition becomes clear: Half of k-digit binary strings contain an even number of 1’s and half contain an odd number of 1’s. Therefore, P(k) = Q(k) = 2^(k-1).

We can easily check this formula for k equals to 3, 10 and 100. For Q(3), it yields 2^(3-1) = 2^2 = 4, which is not correct. For Q(10), it yields 2^(10-1) = 2^9 = 512, also not correct. For Q(100), it yields 2^(100-1), too huge to be correct. Therefore, this formula is not valid for arbitrary k.

This is a tricky counting problem with not-very-obvious symmetries, and it’s unlikely to have a neat closed-form solution. We need a more general solution that accounts for the specific structure of our polynomial and its coefficients. Unfortunately, it appears that this problem might not have a general closed-form solution and may require significant computation.

More Answers: