问题一

\(x_1, x_2, \dots, x_K\) 是正整数，满足 \(x_1 + x_2 + \dots + x_K = N\)。

求 \(\sum x_1 x_2\dots x_K\)。

解

答案是 \(N + K - 1 \choose 2K - 1\)。

考虑 \(\sum x_1 x_2 \dots x_K\) 的组合意义。

设想有 \(N\) 个球排成一行。“先把这 \(N\) 个球分成 \(K\) 段，然后从每一段中选一个球”的方法数就是 \(\sum x_1 x_2 \dots x_K\)。

“先把这 \(N\) 个球分成 \(K\) 段，然后从每一段中选一个球”有多少种方法？设想有 \(K - 1\) 个隔板。先用这 \(K - 1\) 个隔板把 \(N\) 个球分成 \(K\) 段，再从每一段里选一个球。此时我们有 \(N\) 个球和 \(K-1\) 个隔板共 \(N + K - 1\) 个东西排成一行。把这 \(N + K - 1\) 个东西从左往右编号，把所放置的 \(K - 1\) 个隔板和所选的 \(K\) 个球的编号依次写下来就得到一个长为 \(2K - 1\) 的的编号序列。下图是 \(N = 6, K= 3\) 的一个例子。绿色竖线代表隔板，红球代表所选的球。

不难看出 \(1, 2, \dots, N + K - 1\) 的长为 \(2K - 1\) 的子序列和“先把这 \(N\) 个球分成 \(K\) 段，再从每一段中选一个球”的方法一一对应。于是“先把这 \(N\) 个球分成 \(K\) 段，再从每一段中选一个球”有 \(N + K - 1 \choose 2K - 1\) 种方法。

问题二

\(x_1, x_2, \dots, x_K\) 是正整数，满足 \(x_1 + x_2 + \dots + x_K \le N\)。求 \(\sum x_1 \dots x_k\)。

解

答案是 \(N + K \choose 2K\)。

仿照上题，考虑 \(\sum x_1 x_2 \dots x_K\) 的组合意义。

设想有 \(N\) 个球排成一行。“先把这 \(N\) 个球分成 \(K + 1\) 段，第 \(K+1\) 段可以是空的但前 \(K\) 段都是非空的，然后从前 \(K\) 段中每一段选一个球”的方法数就是 \(\sum x_1 x_2 \dots x_K\)。

设想先用 \(K\) 个隔板把 \(N\) 个球分成 \(K + 1\) 段，前 \(K\) 段非空，第 \(K+1\) 段可以是空的；然后从前 \(K\) 段中每一段选一个球。此时我们有 \(N\) 个球和 \(K\) 个隔板排成一行，把这 \(N + K\) 个东西从左到右编号，然后把所放置的 \(K\) 个隔板和所选的 \(K\) 个球的编号依次写下来，得到一个长为 \(2K\) 的编号序列。下图是 \(N = 6, K = 3\) 时的两种方法和对应的编号序列。

“先把 \(N\) 个球分成 \(K + 1\) 段，第 \(K+1\) 段可以是空的但前 \(K\) 段都是非空的，再从前 \(K\) 段每一段选一个球”的方法和 \(1, 2, \dots, N + K\) 的长为 \(2K\) 的子序列一一对应。

问题三

\(x_1, x_2, \dots, x_K\) 是正整数，满足 \(x_1 + x_2 + \dots + x_K = N\) 且 \(x_1 \ge t\)，\(t\) 是正整数。求 \(\sum x_1 x_2\dots x_K\)。

解

令 \(x_1' = x_1 - (t - 1)\)。 \[ \begin{aligned} \sum {x_1 x_2 \dots x_K} &= \sum (x_1' + (t - 1)) x_2 \dots x_K \\ & = \sum_{x_1' + x_2 + \dots + x_K = N - (t - 1)} x_1' x_2 \dots x_K + (t - 1) \sum_{x_2 + \dots + x_K \le N - t} x_2 \dots x_K \\ & = {N + K - t \choose 2K - 1} + (t - 1) {N - t + K - 1 \choose 2K - 2} \end{aligned} \]

试给等式 \(\sum x_1 x_2 \dots x_K = {N + K - t \choose 2K - 1} + (t - 1) {N - t + K - 1 \choose 2K - 2}\) 一个组合解释。

问题四

\(x_1, x_2, \dots, x_K\) 是正整数，满足 \(x_1 + x_2 + \dots + x_K = N\) 且 \(x_1\le t\)，\(t\) 是正整数。求 \(\sum x_1 x_2\dots x_K\)。

解

答案是 \({N + K - 1 \choose 2K- 1} - {N + K - t - 1 \choose 2K - 1} - t{N - t + K - 2 \choose 2K - 2}\)。