3
$\begingroup$

Two numbers are equivalent if they have the same digits, for example $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 $\dfrac{9\times 10\times 10\times 10}{4!}$? First calculating the total numbers formed and divindg by $4!$ to get rid of the repetitions.

  • 4
    Hint: The number of repetitions for the digits 1227 is not 4!.2010-11-18

2 Answers 2

3

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

1

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 $\dfrac{9\times 8\times 7\times 6}{24}$ equivalence classes. If no digits match and one is zero, the zero cannot be the first digit, so there are only $3\times 3\times 2\times 1=18$ permutations and $\dfrac{1\times 9\times 8\times 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?