原题目：19. Arestaurant has n items on its menu. During a particular
day, k customers will arrive and each one will choose
one item. The manager wants to count how many different
collections of customer choices are possible without
regard to the order in which the choices are made.
(For example, if k = 3 and a1, . . . , an are the menu items,
then a1a3a1 is not distinguished from a1a1a3.) Prove that
the number of different collections of customer choices is n+k−1
k
. Hint: Assume that the menu items are a1, . . . , an.
Show that each collection of customer choices, arranged
with the a1’s first, the a2’s second, etc., can be identified
with a sequence of k zeros and n − 1 ones, where each 0
stands for a customer choice and each 1 indicates a point
in the sequence where the menu item number increases
by 1. For example, if k = 3 and n = 5, then a1a1a3 becomes
0011011.

看不懂，感觉像排列组合

同问

每一种选择都可以描述成x1个a1,x2个a2,...,xn个an（x1+x2+...+xn=k），也可以写成以下序列的形式：
(x1个0) 1 (x2个0) 1 ... 1 (xn个0)
容易证明这种从选择到含n-1个1与k个0的序列的对应关系是一一对应的，因此选择数就是含n-1个1与k个0的序列数。

顶