Question

Explain and prove your answer for each question. (a) How many lists of length 3 can be formed whose components are drawn from {1, 2, 3, . . . , n}? (b) How many lists of length 3 can be formed whose components are drawn from {1, 2, 3, . . . , n} and if we require that the first and second components must be the same? (c) How many lists of length 3 can be formed whose components are drawn from {1, 2, 3, . . . , n} and the components are all distinct? (d) How many lists of length 3 can be formed whose components are drawn from {1, 2, 3, . . . , n} and if we only require that the first and last components must be different?

Answer 1

a) We have n³ possible lists

b) We have n² possible lists

c) We have n³-3n²+2n possible lists

Explanation:

a) We have n options for each element of the list. Since we have no restrictions between the elements, then we will have to power n by 3, gibing us a total of n³ possible lists that we can form.

b) Since the fisrt two components must be the same, then we have n possibilities for the first element and after choosing it, we will have only 1 possibility for the second element and then n possibilities for the third one. This gives us n*1*n = n² possible lists.

c) We have n possibilities for the first element, but we have to discard it when we pick the second one, thus we have n-1 possibilities for the second element and with a similar argument we will have n-2 possibilities for the third element. Giving us a total of n*(n-1)*(n-2) = n³-3n²+2n possibilities.