(a) Count the number of quadruples (a, b, c, d) of nonnegative integers such that 0 <= a < b < c < d <= 12.
(b) For this part, we want to count the number of quadruples (a, b, c, d) of nonnegative integers such that 0 <= a <= b <= c <= d <= 12.
Here, some of a, b, c, and d can be equal to each other, so the answer will be different from part (a). Each value a, b, c, d must be between 0 and 12 inclusive. One idea is to count how many times each number appears.
(c) In general, find the number of k-tuples (a1, a2, a3, . . ., ak) of nonnegative integers such that 0 <= a1 <= a2 <= a3 <= . . . <= ak <= n.
(a) We can choose four numbers from 1, 2, 3, ..., 12. Then a is the lowest, b is the second-lowest, c is the third-lowest, and is the fourth-lowest, so the number of ways of choosing a,b,c,d is C(12,4) = 495.
(b) There are 12 ways of choosing a. If a = 12, then there are 12 ways of choosing b. If a = 11, then there are 11 ways of choosing b. This pattern continues, so the number of ways of choosing b is 12 + 11 + 10 + ... + 1.
If b = 11, then there are 11 ways of choosing c. If b = 10, then there are 10 ways of choosing c. This pattern continues, so the number of ways of choosing c is 11 + 10 + 9 + ... + 1.
If c = 10, then there are 10 ways of choosing d. If c = 9, then there are 9 ways of choosing d. This pattern continues, so the number of ways of choosing d is 10 + 9 + 8 + ... + 1.
So the number of ways of choosing a,b,c,d is 12(12 + 11 + ... + 1)(11 + 10 + 9 + .. + 1)(10 + 9 + 8 + ... + 1) = 12*78*66*55 = 3397680.
(c) There are n ways of choosing a_1. If a_1 = n, then there are n ways of choosing a_2. If a_1 = n - 1, then there are n - 1 ways of choosing a_2. This pattern continues, so the number of ways of choosing a_2 is n + (n - 1) + ... + 1 = n(n + 1)/2.
We can take the formula for part (b) and make it for n and k. The number of ways of choosing a_1,a_2,...,a_k is n * n(n + 1)/2 * (n - 1)n/2 * ... * (n - k)(n - k + 1)/2.
