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.

This is a math question.

I have been stumped to come up with a general formula for the following seemingly simple question. Given a number of distinct elements to choose from and choosing N, how many permutations exist that have a set number of different elements? An example of this problem is how many different 16 digit numbers exist in base 10 that have exactly 8 different digits? (0 as the most significant is counted). It seems to me there is no generic formula except all the different combinations of the 8 elements must be permutated and added up? Any suggestion to look for the shortest solutions is appreciated.

share|improve this question

migrated from physics.stackexchange.com Jun 20 '13 at 2:55

This question came from our site for active researchers, academics and students of physics.

1 Answer 1

Here's a go at an answer. Test this against your own counting to check if we are understanding the question in the same way.

Let $n_{k}\left(j\right)$ be the number of $k$ digit numbers drawn from an alphabet of $j$ different digits and let $N_{k}\left(j\right)$ be the number with exactly $j$ different digits. For example: $$\begin{array}{lcl} n_{k}\left(1\right) &=& 1,\\ n_{16}\left(2\right) &=& 2^{16},\\ n_{16}\left(3\right) &=& 3^{16},\\ n_{3}\left(2\right) &=& 2^{2},\\ N_{2}\left(2\right) &=& 2,\\ N_{3}\left(2\right) &=& 6,\\ N_{k}\left(k\right) &=& k!, \end{array}$$ etc. Clearly $n_{k}\left(j\right)=j^{k}$.

To make a $k$ digit number with exactly $j$ different digits then you must exclude all possibilities with fewer digits, i.e. $n_{k}\left(j-1\right),n_{k}\left(j-2\right),$ etc. Each of these is weighted by the number of possible subsets of $j-i$ digits from the full alphabet of $j$ digits. For example, in the case $j\in\left\{ 0,1\right\} , n_{2}\left(2\right)=4$ corresponds to the set $\left\{ 00,01,10,11\right\} $. But to get $N_{2}\left(2\right)$ you must exclude the two cases $\left\{ 00,11\right\} $. Thus

$$\begin{array}{lcl} N_{k}\left(j\right) &=& n_{k}\left(j\right)+\sum_{i=1}^{j-1} (-1)^i \binom{j}{j-i}n_{k}\left(j-i\right) \\ &=& j^{k}+\sum_{i=1}^{j-1} (-1)^i \binom{j}{j-i}\left(j-i\right)^{k} \\ &=& \sum_{i=0}^{j} (-1)^i \binom{j}{j-i}\left(j-i\right)^{k} \end{array}.$$

The factors of -1 account for the multiple counting of numbers in the sum. I'm not aware of a closed form expression for this sum. Mathematica won't give me one, but someone here would probably know if there is a simple expression for it. Note that when $j=k$ the series reduces to $k!$ as it should.

The answer to your question would be $\binom{10}{8} N_{16}(8) = 3886016697763200$.

EDIT: Note that this is related to Stirling numbers of the second kind:

$$ N_k(j) = j! S(k, j).$$

share|improve this answer
    
I think your answer does not satisfy this problem, and the problem is not related to Stirling numbers of the second kind. –  alian Jun 30 '13 at 17:42
    
Then it would help if you listed a number of simple cases where you can do the counting by hand, just to make sure we know what the problem actually is. I based this on the question as read. Apologies if I misunderstood. –  Michael Brown Jul 1 '13 at 0:13

Your Answer

 
discard

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