|
Two numbers are equivalent if they have the same digits ex 2271 and 1227 are equivalent. How many equivalent classes are there between 1000 & 9999? I'm not sure I fully understand how this works, is the answer to this question (9*10*10*10)/4!? First calculating the total numbers formed and divindg by 4! to get rid of the repetitions. |
|||||
|
|
Represent each equivalence class by the number which has it's digits sorted. Now this is uniquely determined by the number of 0s, number of 1s, ..., number of 9s. Thus you need to find the total number of tuples $(n_0, n_1, \dots, n_9)$ such that $\displaystyle \sum_{i=0}^{9} n_i = 4$ such that $n_i \ge 0$. This is given by $\displaystyle {13 \choose 4}$ Since this also counts $0000$, the answer for your problem is $\displaystyle {13 \choose 4}-1$. In general, the number of disitnct $n$-tuples of non-negative integers which sum to $k$ is given by $\displaystyle {n+k-1 \choose k}$. See here: http://en.wikipedia.org/wiki/Stars_and_bars_%28probability%29 |
||||
|
|
|
One approach is to work by cases of the number of matching digits. If no digits match and none is zero, there are in fact 4!=24 permutations. So this accounts for 9*8*7*6/24 equivalence classes. If no digits match and one is zero, the zero cannot be the first digit, so there are only 3*3*2*1=18 permutations and 1*9*8*7/18 equivalence classes. If you have one pair of matching digits and no zero, there are how many permutations and how many equivalence classes? |
|||
|
|
