Monotonicity of the sum of coefficients of a family of generating functions

Question

Let \begin{equation*} A_{n,w}(z)=\left(\sum_{i=0}^{\lfloor\frac{w}{2}\rfloor-1}\binom{w}{i}z^i+\frac{1}{2^{(w+1)\bmod 2}}\binom{w}{\lfloor\frac{w}{2}\rfloor}z^{\lfloor\frac{w}{2}\rfloor}\right)^{n/w} \end{equation*} for example:

• $A_{n,2}(z)=(1+z)^{n/2}$
• $A_{n,3}(z)=(1+3z)^{n/3}$
• $A_{n,4}(z)=(1+4z+3z^2)^{n/4}$
• $A_{n,5}(z)=(1+5z+10z^2)^{n/5}$

Note that $[z^k]A_{n,w}(z)$ is the number of ways to put $k$ balls into $n/w$ boxes with $w$ positions such that:

• each box contains at most $\lfloor\frac{w}{2}\rfloor$ balls,
• any box containing exactly $\lfloor\frac{w}{2}\rfloor$ balls must use its first position if $w$ is even (note that $\binom{w-1}{w/2-1}=\frac{1}{2}\binom{w}{w/2}$ when $w$ is even).

I conjecture that:

Given $n, w$ such that $w(w+1) \mid n$. For all $0\leq r\leq n$, we have $$\sum_{k=0}^{r}[z^k]A_{n,w}(z)\leq\sum_{k=0}^{r}[z^k]A_{n,w+1}(z)$$

But I don't have enough tools to show that for arbitrary $w$, maybe do some asymptotic analysis?

for example: $$\sum_{k=0}^{\alpha n}[z^k]A_{n,2}(z)=\sum_{k=0}^{\alpha n}\binom{n/2}{k}\sim2^{\frac{1}{2}H_2(2\alpha)n}\leq2^{\frac{2}{3}H_4(3\alpha)n}\sim\sum_{k=0}^{\alpha n}\binom{n/3}{k}3^k=\sum_{k=0}^{\alpha n}[z^k]A_{n,3}(z)$$ where $H_q(x)=x\log_q(q-1)-x\log_q(x)-(1-x)\log_q(1-x)$.

The following basic facts might be helpful:

• Let $K_{w}(z)=(A_{n,w}(z))^{w/n}$, then we have $K_{w}(z)+z^wK_{w}(\tfrac{1}{z})=(1+z)^w$.
• For all $0\leq k\leq\lfloor\frac{w-1}{2}\rfloor$ we have $[z^k]A_{n,w}(z)=[z^k]((1+z)^w)^{n/w}=[z^k](1+z)^n=\binom{n}{k}$.

Answer 1

Your conjecture is true. First, observe that

\begin{align*} K_{w+1}(z)&=(1+z)\,K_w(z) & \mbox{ if } w \mbox{ is odd, }\\ K_{w+1}(z)&=(1+z)\,K_w(z) +\frac{1}{2}{w\choose \frac{w}{2}}z^{w/2}(1-z) & \mbox{ if } w \mbox{ is even } \end{align*} (Informally, for $w$ even $K_{w+1}(z)$ is constructed from $(1+z)K_w(z)$ by adding the coefficient of $z^{w/2+1}$ to the coefficient of $z^{w/2}$ and deleting it at $z^{w/2+1}$.) Therefore the partial coefficient sums of $K_{w+1}(z)$ are not less than the partial coefficient sums of $(1+z)K_w(z)$, and this will stay true if both sides are raised to some positive integer power.

(In probabilistic language : the distribution with probability generating function $K_{w+1}(z)/K_{w+1}(1)$ is stochastically not larger than that with probability generating function $(1+z)K_w(z)/K_{w+1}(1)$, and that continues to hold for sums of independent summmands.)

Now let $n=m w (w+1)$ with positive integer $m$. Then \begin{align*} \sum_{k=0}^r [z^k] A_{n,w+1}(z)&=[z^r] \frac{1}{1-z} \Big(K_{w+1}(z)\Big)^{mw}\\ &\geq [z^r] \frac{1}{1-z} \Big((1+z) K_{w}(z)\Big)^{mw}\\ &= [z^r] \frac{1}{1-z} \Big((1+z)^w (K_{w}(z))^w\Big)^{m}\\ &\geq [z^r] \frac{1}{1-z} \Big(K_w(z) (K_{w}(z))^w\Big)^{m}\\ &= [z^r] \frac{1}{1-z} \Big(K_w(z)\Big)^{m(w+1)}\\ &=\sum_{k=0}^r [z^r] A_{n,w}(z) \end{align*} Here the first inequality follows from the remark above, and the second inequality follows, since $(1+z)^w$ is coefficient-wise not less than $K_w(z)$.

Answer 2

I discover an injection proof.

Intuitively:

• If $w$ is odd ($w=2\ell-1$): \begin{equation*} \begin{split} \hspace{-8.4ex}\underbrace{(\blacksquare\Box\Box)}_{\mbox{splitted into each other boxes}}\hspace{-8.4ex}(\Box\blacksquare\Box)(\Box\Box\Box)(\Box\Box\blacksquare)\mapsto(\blacksquare\Box\blacksquare\Box)(\Box\Box\Box\Box)(\Box\Box\Box\blacksquare) \end{split} \end{equation*}
• If $w$ is even ($w=2\ell$): \begin{equation*} \begin{matrix} \hspace{-7.5ex}\underbrace{(\blacksquare\Box\blacksquare\Box)}_{\mbox{splitted into each other boxes}}\hspace{-7.5ex}(\Box\blacksquare\Box\Box)(\blacksquare\Box\Box\blacksquare)(\blacksquare\Box\blacksquare\Box)(\blacksquare\blacksquare\Box\Box)\\ \downarrow\\ (\blacksquare\Box\blacksquare\Box\Box)(\Box\blacksquare\Box\Box\blacksquare)\hspace{-1.9ex}\underbrace{(\blacksquare\blacksquare\Box\blacksquare\Box)}_{\mbox{flip each position}}\hspace{-1.5ex}(\Box\blacksquare\blacksquare\Box\Box)\\ \downarrow\\ (\blacksquare\Box\blacksquare\Box\Box)(\Box\blacksquare\Box\Box\blacksquare)(\Box\Box\blacksquare\Box\blacksquare)(\Box\blacksquare\blacksquare\Box\Box)\\ \end{matrix} \end{equation*}