A restaurant 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). 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.