I have a question as follows:
A small design company gives each of its products a code that consists of two letters
followed by four digits. How many different codes can be formed such that the letters
are taken from $\{A,B,C,D\}$ and may include repetition, and the four digits are taken
from $\{1,2,3,4,5,6,7,8,9\}$ and must be all different and arranged in decreasing order?
My idea: we know that the options for the first two letters are $4^2$. But how to arrange the four digits in decreasing order? I feel like that the options of "all different" are $\tbinom{9}{4}$.
Best Answer
You need to break everything down. $\tbinom{9}{4}$ means the number of all unique subsets with four elements of a set of 9 elements. Now a set of 9 elements of $\{1,2,3,4,5,6,7,8,9\}$ remains the same even if you shuffle the numbers, because you can still choose from the same values. This is also true for its subsets: a unique subset must have all of its values so that none of the other subsets have the same values, irrespective of ordering. Based on the comment, $\{2, 9, 3, 4\}$ is the same subset as $\{9, 4, 3, 2\}$, though the latter is sorted. Now you need to see if you can have multiple options from a given subset by sorting, or possibly less. If you have sorted elements like $\{9, 4, 3, 2\}$, as each element is unique, it means that an element and its smaller neighbour (if has) have a difference of at least 1, therefore no neighbours can be swithced, as that would break ordering. From this follows that no any 2 elements can be switched. So a unique subset has exatly one sorting order, therefore the sorting condition does not increase the number of options. It can also not decrease, as subsets are unique which means per above not all the numbers are the same for any 2 subsets, and after sorting this attribute will still be true as no value has changed, and therefore this meets the "must be all different" condition. So the question is as you correctly feel: how many unique subsets with four elements of a set of 9 elements has?