What is $\max_{n} \frac{1}{d^n} \sum_{r=1}^d \sum_{m=r}^d (-1)^{m+r}rm {d \choose m}{m \choose r} (r-1)^{n-1}$

Question

Question

For $d, n \in \mathbb{N}$ define $$ f(d, n) = \frac{1}{d^n} \sum_{r=1}^d \sum_{m=r}^d (-1)^{m+r}rm {d \choose m}{m \choose r} (r-1)^{n-1}. $$

For a given $d$, what $n$ maximizes $f(d,n)$?

Context

This is the expectation for the following game. Throw $n$ dice (each having $d$ faces). You get as many points as there are different values appearing. Except if two adjacent dice (the dice are in a row) have the same value, in which case you get $0$ points for that throw.

Examples:

• 1, 5, 2, 4, 1 $\space \space \mapsto$ $4$ points (4 different values: 1,2,4,5)
• 6, 2, 2, 4, 3 $\space \space \mapsto$ $0$ points (because 2's next to each other)
• 2, 6, 1, 2, 6 $\space \space \mapsto$ $3$ points (3 different values: 1,2,6)

The formula $f$ for this expectation can be derived by inclusion-exclusion in a similar fashion that the number of surjections is calculated, we just have some more factors in there.

Remarks

The maximizing $n$ seems to grow linearly and be about $n_{max} = 0.69d -0.42$. And the quantity $f(d, n_{max})$ also looks linear with a coefficient $0.12$.

Can this be proved and how about the exact value of these coefficients?

Answer 1

We derive a closed formula for $f(d,n)$ which will considerably ease maximum calculations. We show the following is valid for natural numbers $n,d\geq 1$: \begin{align*} \color{blue}{f(d,n)} &\color{blue}{=\frac{1}{d^n}\sum_{r=1}^d\sum_{m=r}^d(-1)^{m+r}rm\binom{d}{m}\binom{m}{r}(r-1)^{n-1}}\\ &\,\,\color{blue}{=(1-d)\left(1-\frac{2}{d}\right)^{n-1}+d\left(1-\frac{1}{d}\right)^{n-1}}\tag{1} \end{align*}

In the following we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance \begin{align*} r^{n}=n![z^n]e^{rz}\tag{2} \end{align*}

We obtain \begin{align*} \color{blue}{f(d,n)} &=\frac{1}{d^n}\sum_{r=1}^d\sum_{m=r}^d(-1)^{m+r}rm\binom{d}{m}\binom{m}{r}(r-1)^{n-1}\\ &=\frac{1}{d^{n-1}}\sum_{m=1}^d(-1)^m\binom{d-1}{m-1}\sum_{r=1}^m(-1)^rr\binom{m}{r}(r-1)^{n-1}\tag{3} \end{align*}

Comment: In (3) we change the order of summation according to \begin{align*} \sum_{r=1}^d\sum_{m=r}^d a_{rm}=\sum_{1\leq r\leq m\leq d} a_{rm}=\sum_{m=1}^d\sum_{r=1}^m a_{rm} \end{align*} and we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

The inner sum in (3) can be written as \begin{align*} \color{blue}{\sum_{r=1}^m(-1)^r}&\color{blue}{r\binom{m}{r}(r-1)^{n-1}}\\ &=m\sum_{r=1}^m(-1)^r\binom{m-1}{r-1}(r-1)^{n-1}\tag{4.1}\\ &=-m\sum_{r=0}^{m-1}(-1)^r\binom{m-1}{r}r^{n-1}\tag{4.2}\\ &=-m\sum_{r=0}^{m-1}(-1)^r\binom{m-1}{r}(n-1)![z^{n-1}]e^{rz}\tag{4.3}\\ &=-m(n-1)![z^{n-1}]\sum_{r=0}^{m-1}(-1)^r\binom{m-1}{r}\left(e^z\right)^r\\ &\,\,\color{blue}{=-m(n-1)![z^{n-1}]\left(1-e^z\right)^{m-1}}\tag{4.4}\\ \end{align*}

Comment:

• In (4.1) we use again the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (4.2) we shift the index by one to start with $r=0$.

• In (4.3) we use (2) and apply in the lines below after some rearrangements the binomial theorem.

We use the expression (4.4) in (3) and obtain \begin{align*} \color{blue}{f(d,n)} &=-\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\sum_{m=1}^d(-1)^m\binom{d-1}{m-1}m\left(1-e^z\right)^{m-1}\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\sum_{m=0}^{d-1}(-1)^m\binom{d-1}{m}(m+1)\left(1-e^z\right)^{m}\tag{5.1}\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\sum_{m=0}^{d-1}(-1)^m\binom{d-1}{m}\left(-e^{-z}\right)\frac{d}{dz}\left(1-e^z\right)^{m+1}\tag{5.2}\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\left(-e^{-z}\right)\frac{d}{dz}\left(1-e^{z}\right)\sum_{m=0}^{d-1}(-1)^m\binom{d-1}{m}\left(1-e^z\right)^m\tag{5.3}\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\left(-e^{-z}\right)\frac{d}{dz}\left(\left(1-e^{z}\right)\left(1-\left(1-e^{z}\right)\right)^{d-1}\right)\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\left(-e^{-z}\right)\frac{d}{dz}\left(\left(1-e^{z}\right)e^{(d-1)z}\right)\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\left(-e^{-z}\right)\frac{d}{dz}\left(e^{(d-1)z}-e^{dz}\right)\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\left(-e^{-z}\right)\left((d-1)e^{(d-1)z}-de^{dz}\right)\\ &=\frac{(n-1)!}{d^{n-1}}[z^{n-1}]\left(-(d-1)e^{d-2)z}+de^{(d-1)z}\right)\\ &=\frac{1}{d^{n-1}}\left(-(d-1)(d-2)^{n-1}+d(d-1)^{n-1}\right)\tag{5.4}\\ &\,\,\color{blue}{=(1-d)\left(1-\frac{2}{d}\right)^{n-1}+d\left(1-\frac{1}{d}\right)^{n-1}} \end{align*} and the claim (1) follows. The result is verified with a few lines of R code for small numbers $d$ and $n$.

Comment:

• In (5.1) we shift the index $m$ to start with $m=0$.

• In (5.2) we get rid of the factor $m+1$ by using the differential operator $\frac{d}{dz}$.

• In (5.3) we do some rearrangements to be able to apply the binomial theorem again.

• In (5.4) we use the coefficient of operator as indicated in (2).

Answer 2

Starting for @epi163sqrt's nice answer $$f(d,n)=(1-d)\left(1-\frac{2}{d}\right)^{n-1}+d\left(1-\frac{1}{d}\right)^{n-1}\tag 1$$ Computing the partial derivative $$\frac {\partial f(d,n)}{\partial n}=(1-d) \left(1-\frac{2}{d}\right)^{n-1} \log \left(1-\frac{2}{d}\right)+$$ $$d \left(1-\frac{1}{d}\right)^{n-1} \log \left(1-\frac{1}{d}\right)$$ which gives $$n_{\text{max}}=\frac{-\log \left(1-\frac{1}{d}\right)-\log \left(\frac{(d-1) \log \left(\frac{d-2}{d}\right)}{(d-2) \log \left(\frac{d-1}{d}\right)}\right)}{\log \left(1-\frac{2}{d}\right)-\log \left(1-\frac{1}{d}\right)}\tag 2$$

Expanded for large values of $d$, this gives $$n_{\text{max}}=d \log (2)-\frac{3\log (2)-1}{2} +\frac{21-2 \log (2)}{24 d}+\frac{19-6 \log (2)}{48 d^2}+O\left(\frac{1}{d^3}\right)$$ which extremely accurate even for small values of $d$ (absolute error of $1.71\times 10^{-4}$ for $d=10$).

By the way, notice how close are the first and second coefficients to yours.

Plugging $(2)$ in $(1)$ and expanding again $$f(d,n_{\text{max}})=\frac{1}{4}d+\frac{1+\log (2)}{4} +\frac{1+2 \log ^2(2)+6 \log (2)}{16 d}+\frac{4 \log ^3(2)+24 \log ^2(2)+28 \log (2)-9}{96 d^2}+O\left(\frac{1}{d^3}\right)$$