Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Hint: The number of repetitions for the digits 1227 is not 4!. –  Byron Schmuland Nov 18 '10 at 13:19
add comment

2 Answers 2

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

share|improve this answer
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.