QUESTION: Consider the set $S$ of all integers between and including $1000$ and $99999$. Consider two integers $x$ and $y$ in $S$ to be in same equivalence class if the digits appearing in $x$ and $y$ are same. For example if $x=1010 , y=1000 $ and $z=1201$ then $x$ and $y$ are in the same equivalence class but $y$ and $z$ are not. Find the number of distinct equivalence classes that can be formed out of $S$.
I tried to find the number of ways in which 4 digit numbers can be formed with 2 given digits (so that if I take 2 at a time from the resulting number of numbers formed, then I get the number of equivalence classes). Same goes for 5 digits.. Also in doing these I had considered 0 as an explicit case since zero cannot occupy the first position. Now, this was really a tiresome calculation, and the fun is, my answer becomes improbably large.
Can anyone please help me out. I feel, there must be some smarter way to think about it.
Thank you.
Best Answer
The set of equivalence classes is in bijective correspondence with the set of subsets of $\{0,1,2, \cdots ,9\}$ (with a small exception, see below).
Therefore, counting the equivalence classes is like counting the number of way to select $k$ elements among $n$).
$$(\binom{10}{1}-1)+\binom{10}{2}+\binom{10}{3}+\binom{10}{4}+\binom{10}{5}$$
More precisely :
the number of classes with a single digit is : $\binom{10}{1}=10$ $\color{red}{\ minus \ 1}$ (the unique digit cannot be $0$ as you have seen it).
the number of classes with $k$ kinds of digits is : $\binom{10}{k}, \ k=2,3,4,5$.