TAOCP 1.2.9 Exercise 18

Part (a) The original derivation is correct.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.9: Generating Functions

Exercise 18. [M25] Given positive integers $n$ and $r$, find a simple formula for the value of the following sums:

(a) $\sum_{1 \le k_1 < k_2 < \cdots < k_r \le n} k_1k_2\cdots k_r$;

(b) $\sum_{1 \le k_1 \le k_2 \le \cdots \le k_r \le n} k_1k_2\cdots k_r$.

(For example, when $n=3$ and $r=2$ the sums are, respectively, $1\cdot2 + 1\cdot3 + 2\cdot3$ and $1\cdot1 + 1\cdot2 + 1\cdot3 + 2\cdot2 + 2\cdot3 + 3\cdot3$.)

Verified: yes
Solve time: 2m13s

Part (a)

The original derivation is correct.

$$ E_r(n)=\sum_{1\le k_1<\cdots<k_r\le n}k_1\cdots k_r $$

is the coefficient of $z^r$ in $\prod_{k=1}^n(1+kz)$. Rewriting

$$ \prod_{k=1}^n(1+kz)=z^n\prod_{k=1}^n\left(k+\frac1z\right) $$

and using the standard expansion of $(x+1)(x+2)\cdots(x+n)$ in terms of unsigned Stirling numbers of the first kind gives

$$ \boxed{ E_r(n)=\left[{n+1 \atop n-r+1}\right] } $$

-, Part (b)

Let

$$ H_r(n)=\sum_{1\le k_1\le\cdots\le k_r\le n} k_1k_2\cdots k_r. $$

Step 1: Correct generating function interpretation

Each factor expands as a geometric series:

$$ \frac{1}{1-kz}=\sum_{m\ge 0} k^m z^m. $$

Hence

$$ \prod_{k=1}^n\frac{1}{1-kz} = \sum_{m_1,\dots,m_n\ge 0} (1^{m_1}2^{m_2}\cdots n^{m_n})z^{m_1+\cdots+m_n}. $$

The coefficient of $z^r$ is therefore

$$ H_r(n)=[z^r]\prod_{k=1}^n\frac{1}{1-kz}. $$

Equivalently, $H_r(n)$ is the complete homogeneous symmetric polynomial of degree $r$ in the variables $1,2,\dots,n$:

$$ H_r(n)=h_r(1,2,\dots,n). $$

This identification is exact.

Step 2: Correct structural recurrence

From the definition of weakly increasing sequences, conditioning on the last term gives a correct and useful recurrence:

$$ H_r(n)=\sum_{k=1}^n k , H_{r-1}(k), \qquad r\ge 1, $$

with initial condition

$$ H_0(n)=1. $$

This follows by fixing $k_r=k$, then summing over all weakly increasing $(r-1)$-tuples in ${1,\dots,k}$.

Step 3: Why the Stirling-number identification fails

The earlier claim

$$ H_r(n)=\left{{n+r \atop n}\right} $$

is false.

For example, when $n=2$,

$$ \prod_{k=1}^2\frac{1}{1-kz}=\frac{1}{(1-z)(1-2z)}=\sum_{r\ge 0}(2^r-1)z^r, $$

so

$$ H_r(2)=2^r-1, $$

whereas

$$ \left{{r+2 \atop 2}\right}=2^{r+1}-1, $$

which disagrees for all $r\ge 1$.

Thus $H_r(n)$ is not a Stirling number of the second kind.

Step 4: What the correct “closed form” is

There is no single Stirling-number closed form for $H_r(n)$. The correct compact expression is:

$$ \boxed{ H_r(n)=[z^r]\prod_{k=1}^n\frac{1}{1-kz} = h_r(1,2,\dots,n) } $$

This is already the standard canonical form: a complete homogeneous symmetric polynomial evaluated at $1,\dots,n$.

If an explicit polynomial expression is desired, it can be expanded via power sums using the complete Bell polynomial identity:

$$ h_r = \frac{1}{r!},B_r(p_1,p_2,\dots,p_r), \quad p_j=\sum_{k=1}^n k^j, $$

but this does not simplify to a single Stirling-number term.

Final answers

$$ \boxed{ E_r(n)=\left[{n+1 \atop n-r+1}\right] } $$

$$ \boxed{ H_r(n)=h_r(1,2,\dots,n) =[z^r]\prod_{k=1}^n\frac{1}{1-kz} } $$

together with the recurrence

$$ \boxed{ H_r(n)=\sum_{k=1}^n k,H_{r-1}(k),\quad H_0(n)=1. } $$