I'd like to know the method for correctly calculating the probability of a random sequence of $9$ numbers only containing $3$ unique, different numbers. For the purpose of this question: there are 10 numbers $0,1,2,3,4,5,6,7,8,9$

i.e. the probability of this: $123123123$ - for all unique combinations of $3$ digits (e.g $071$ in $071717717$)

My initial instinct is $(1/3)^9$ - is this correct?

  • 1
    $\begingroup$ Does the number have to contain exactly 3 distinct numbers, or at most 3? Is $000000000$ in the set? $\endgroup$ – Mario Carneiro May 27 '13 at 0:39
  • $\begingroup$ Exactly 3. 000000000 is not. Most interested in the method of working out a problem of this sort (i.e, with smaller or larger sequences). $\endgroup$ – Joseph May 27 '13 at 0:41
  • $\begingroup$ If you are considering $10$ digits, wouldn't $(3/10)^9$ be more likely than $(1/3)^9$? $\endgroup$ – Ross Millikan May 28 '13 at 13:28

From the Twelvefold way, the number of surjective functions from a set of size $n$ to one of size $x$ is $x!\{{n\atop x}\}$, where $\{{n\atop x}\}$ is the Stirling number of the second kind. Here $n=9$ and $x=3$, and this represents the number of $9$-digit numbers containing $3$ (specified) integers. There are ${10\choose 3}$ possibilities of which integers to allow in the number (assuming base 10), so the total probability is

$$P=\frac{3!}{10^9}\left\{{9\atop 3}\right\}{10\choose 3}=\frac{6\cdot3025\cdot120}{1000000000}=\frac{2178000}{1000000000}=0.2178\%$$

which is a bit more than the $3^{-9}\approx.005\%$ originally predicted.

Edit: due to some ambiguities in the OP, I'm also listing the same results as above where the base alphabet only contains $9$ symbols (say $\{0,1,2,3,4,5,6,7,8\}$), per Ross Millikan's analysis. Then we have

$$P=\frac{3!}{9^9}\left\{{9\atop 3}\right\}{9\choose 3}=\frac{6\cdot3025\cdot84}{387420489}=\frac{1524600}{387420489}\approx0.39352\%.$$

In general, if we want to know the proportion of length $n$ strings on an alphabet of $k$ symbols which use exactly $x$ distinct symbols, the formula is $P=\frac{x!}{k^n}\left\{{n\atop x}\right\}{k\choose x}$.

  • $\begingroup$ Mario, thank you also for you answer. $\endgroup$ – Joseph May 28 '13 at 9:52

And there is the bull at red cape brute force method ... here using Mathematica:

SantasLittleDigitCounter[m_] := (j = 0;
 Do[ If[Length[Union[IntegerDigits[i, 10, m]]] == 3, j++], {i, 0, 10^m - 1}]; j)




which matches exactly the super theoretical solution derived above by Mario Carneiro.

A few minor comments:

  • Ran this while having dinner.

  • A neater/better approach in Mathematica is usually to generate all the numbers we want to test in one go (say lis = Range[$0$, $10^9-1$]), and then test them all in one go, using faster functional approaches such as Map rather than the more old-fashioned procedural Do loop-de-loop ... but because the number of terms we have to test is so large (a billion), the memory requirements of generating them all in one go is a bit messy ... so went back to just using good old Do. I suppose one could parallel-optimise this, if desired.

  • The original poster has noted that numbers like 21 count as a 3-digit hit, because it is represented as the 9 digit {0,0,0,0,0,0,0,2,1}. This is the reason for using the form IntegerDigits[i, 10, m] ... which pads integer i (in base 10) with zeroes to fill $m=9$ slots.

  • 2
    $\begingroup$ Really you understand nothing about the learning processes in mathematics, do you? Anyway, I suggest you stop inserting snide remarks about others' (mathematical) solutions into your (non mathematical) own. Oh, and by the way, this is Not A Real Answer since the OP asked about methods (twice), not about the numerical value (which, frankly, nobody cares about). $\endgroup$ – Did May 27 '13 at 11:59
  • $\begingroup$ @wolfies How long does it usually take for you to have a dinner? $\endgroup$ – Artem May 27 '13 at 15:37
  • $\begingroup$ lol - I think it was about 60 minutes for the billion numbers on my Mac. One could get about 5 or 10 times better than that with some optimisation / parallel goodies ... but it's a one-off for me :) $\endgroup$ – wolfies May 27 '13 at 16:25
  • 10
    $\begingroup$ @Did Actually, I'm glad wolfies did this brute-force count, because it's a sanity check for my solution. Early after this question was posed, there were four answers with four combinatorial proofs of four different numbers. Although I was pretty sure my answer was correct, I'm sure so did the other guys, so it made me doubtful of whether I had done it right. There's nothing like going back to basics to make sure your answer makes sense. $\endgroup$ – Mario Carneiro May 28 '13 at 22:29
  • 1
    $\begingroup$ @MarioCarneiro As long as one does not take this kind of posting for a solution (and forgetting the snide remarks made by user wolfies), everything is fine. (At the level of principle though, I find strange to put more faith in the numerical answer produced by a computer software than in others. Those are as error prone as other tools (due to typing errors or to math misunderstandings), hence in the situation you describe, they are simply one more proposition, to be checked as the others.) $\endgroup$ – Did May 29 '13 at 5:40

There are two problems with your solution. First, there are ${9 \choose 3}$ ways to choose which three digits you pick, so you have to multiply by that. Second, if the digits are $123$, you have counted sets like $111111111$ and $121212121$ that have only one or two different digits respectively. It seems you do not want to count them at all, and in fact you have counted them many times.
The easiest way is to start with ${9 \choose 3}3^9$ as the count of digit strings, then subtract the ones with just one or just two digits. The strings with just one digit have been counted ${8 \choose 2}$ times, and there are $9$ of them. The ones with exactly two digits have been counted $7$ times each and there are ${9 \choose 2}(2^9-2)$ of them. So the final count is ${9 \choose 3}3^9-9{8 \choose 2}-7{9 \choose 2}(2^9-2)$ and the probability comes from dividing this by $9^9$

  • 1
    $\begingroup$ Why $9^9$ and not $10^9$? He is including $0$ as an option. Is your answer otherwise consistent with mine? $\endgroup$ – Mario Carneiro May 27 '13 at 0:59
  • $\begingroup$ @MarioCarneiro: OP specified a $9$ element set. It is natural to think of it (given the post) as $[0,8]$. I used "digits" as elements of the set because of the examples given. $\endgroup$ – Ross Millikan May 27 '13 at 2:37
  • 1
    $\begingroup$ My understanding is that these sets are sequences of length 9 from an alphabet on 10 letters, i.e. digit strings of length 9 in decimals, with leading 0's. (If the OP is present, this should be clarified one way or the other.) $\endgroup$ – Mario Carneiro May 27 '13 at 3:11
  • 1
    $\begingroup$ I found the disparity. First, my answer is $0.39353\%$ when you change $10\to9$ (numerator $1524600$). Second, in your count of numbers with exactly 2 digits, they are counted 7 times, and there are ${9\choose2}(2^9-2)$ of them (everything except all $0$ and all $1$ is exactly 2 digits). Counted this way, you don't need the last overcounting step and your answer becomes consistent with mine. Equivalently, the last overcounting step should be ${9\choose2}14$, because you are counting within another overcounting step, so it multiplies ${9\choose2}7$ by the $2$ possible one-digit strings. $\endgroup$ – Mario Carneiro May 27 '13 at 4:40
  • 1
    $\begingroup$ @MarioCarneiro: You are correct. I have fixed it. Looks like OP wanted $10$ digits all along. Thanks $\endgroup$ – Ross Millikan May 28 '13 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.