2

I have written a Mastermind clone where there are 9 peg-slots where each of the peg-slots can be 1 of 9 colours. I cannot seem to get my head round working out the number of permutations for particular repeated counts of any colours :( I am wanting to create a table of the frequencies of possible solution compositions ( or at least the most common ones / easiest to calculate ) , e.g. solutions with 9 separate colours, solutions with 1 and only 1 duplicated colour ( e.g. 9 pegs with 2 blue pegs and the rest all different OR 2 red pegs and the rest all different colours, etc ) , solutions with 2 and only 2 duplicated colours ( e.g. 9 pegs with 2 blue pegs AND 2 red pegs the rest all different OR 2 red pegs AND 2 orange pegs AND the rest all different colours, etc ), solutions with 1 peg appearing 3 times and the rest all different, solutions with 1 peg appearing 3 times, 1 appearing 2 times AND the rest all different-coloured pegs.

The total number of possible combinations is 99 which approximates to just over 184 million as any peg-slot can contain any colour. ( i assume i am right here? :) i.e. any peg colour can go in any slot so 9x9x9x9x9... )

The number of possible permutations with each peg being a different colour is 9! which is 362,880 which translates as the chance of getting a randomly generated solution with 9 separate colours as 362,880/184 million = 0.00094. That is that one would expect approx 1 in a 1000 to have distinct colours.

Now, to calculate the number of permutations with 1 and only 1 repeated colour. So this is the same as taking the permutations for 9 separate colours and changing one of the colours, say the yellow, to any other, say the blue. In doing this, we will have 2 repeated permutations: one where the yellow in Position x was changed to a blue, and the original blue in Position y, and another permutation where Yellow in Position y was changed to a blue, and the peg in Position x was a blue. So we can process the solution the same by substituting the yellow with another of the other 7 colours other than yellow ( all colours EXCEPT blue or yellow )to find all the possibilities with blue repeated. And we can do this for every colour.

The number of solutions where a particular colour is replaced by another particular colour = 362,880 /2.

The number of solutions where a particular colour being replaced by any other colour = (362,880 /2) * 8.

The number of solutions where any colour being replaced by any other colour = (362,880 /2) * 8 * 9.

Which means that the chances of a repeated colour is 36 times more likely than having a randomly-generated solution with ALL the colours represented.

Is my reasoning correct?

The problem is I have difficulty in visualising it to have solutions with 2 different colours being replaced by 2 other separate colours :( or extending it to substitute 2 colours with another so a colour, and only one colour, is tripled.

Thanks in advance.

And I am sure there is an easy formula to do this.

Alex Ainsworth
  • 45
  • To be clear... you are asking for the number of functions from ${1,2,3,\dots,9}$ (pegslots) to ${1,2,3,\dots,9}$ (colors) where exactly one number in the codomain appears any amount more than once or are you asking where exactly one number in the codomain appears exactly twice? – JMoravitz Jul 09 '21 at 12:26
  • Choose the color to be repeated. Break into cases based on the number of times that color is used. Choose that many positions to be used for this color. For the remaining positions, from left to right choose an unused color. $\sum\limits_{i=2}^n\binom{n}{i}k\frac{n-i}{~}$ where $n$ is the number of pegs, $k$ is the number of colors, $i$ represents the number of times the repeated color is repeated, and $a\frac{b}{~}$ represents the falling factorial, $a\frac{b}{~}=\frac{a!}{(a-b)!}=\underbrace{a(a-1)(a-2)\cdots(a-b+1)}_{b~\text{terms}}$ – JMoravitz Jul 09 '21 at 12:34
  • Hi JM Thans for responding. What i am wanting is bascially a formulavor explanation to find the number of possible solutions in a Mastermind game where ANY colour is duplicated e.g. 2 yellows OR 2 blues OR 2 reds , etc. and no other colour is repeated. – Alex Ainsworth Jul 09 '21 at 12:37
  • But also 2 work out number of possible permutiations where TWO colours are duplicated e.g. 2 reds and 2 blues, 2 oranges and 2 purples, and all the other colours are singular. Then maybe to find the number of permuaitons where any colour is tripled. So it contains 3 reds OR 3 blues OR 3 yllows and no other colour is repeated. I just want to understand the strategy to work out how to work out the duplicates no matter how many duplicates there are i.e. 1, 2, 3 or 4. or number of times colours are repeated – Alex Ainsworth Jul 09 '21 at 12:38
  • "Duplicated" is the word I'm struggling with here. Some may take that to mean "appears exactly twice." Others might take that to mean "appears any number of times more than once" – JMoravitz Jul 09 '21 at 12:38
  • Sorry JM i am sorry you are right i was not clear. I am wanting to create a table of as many ways solutions can be permuted. So i want for example the number of ways 1 and only 1 colour appears TWICE, all other colours appearing once. But also the number of ways TWO colours appear TWICE each, all other colours appearing once. I also want to find out the number of ways, for example, any colour appears THREE times an only THREE times and the remaining colours just once. – Alex Ainsworth Jul 09 '21 at 13:13
  • The idea for example is wanting to work out ANY possible combinaton of frequencies of colours e.g. 2-1-1-1-1-1-1-1, 2-2-1-1-1-1-1, 2-2-2-1-1-1, 3-1-1-1-1-1-1, 3-2-1-1-1-1, 3-2-2-1-1,and to underestand what i am doing to calculate them. Thanks again JM – Alex Ainsworth Jul 09 '21 at 13:13

1 Answers1

1

Coming up with a completely generic formula that covers all cases is frustratingly difficult or tedious to write... but if you have a specific what I'll call a "frequency-sequence" you are interested in, the approach is to choose which colors are used for which frequency where order of colors within the same frequency doesn't matter... then use multinomial coefficients to choose how to distribute those colors with those frequencies among the peg positions.

For example with $n=k=9$ and the frequency-sequence "3-2-2-1-1", begin by picking a color to appear three times. This can be done in $9$ ways. Next, simultaneously pick two colors from those remaining to appear two times each. This can be done in $\binom{8}{2}$ ways. Finally, simultaneously pick two colors to be used once each. This can be done in $\binom{6}{2}$ ways. Finally, pick the order in which those selected colors appear that many times in $\binom{9}{3,2,2,1,1}=\frac{9!}{3!2!2!1!1!}$ ways.

The overall count of this case then? $9\cdot \binom{8}{2}\cdot \binom{6}{2}\cdot \frac{9!}{3!2!2!1!1!}$

As for a completely general formula... given a degree sequence in the form $((a_1,a_2,\dots,a_m),(b_1,b_2,\dots,b_m))$ with $b_i\neq b_j$ for all $i\neq j$ and $a_1b_1+a_2b_2+\dots+a_mb_m=n$ representing $a_1$ copies of $b_1$, $a_2$ copies of $b_2$ and so on... the earlier example being $((1,2,2),(3,2,1))$ corresponding to one $3$, two $2$'s, and two $1$'s...

we can express this as:

$\left(\prod\limits_{i=1}^m\binom{k-\sum\limits_{j=1}^{i-1}a_i}{a_i}\right)\cdot\frac{n!}{\prod\limits_{i=1}^m(b_i!)^{a_i}}$

JMoravitz
  • 79,518
  • Thanks J you are a star :) – Alex Ainsworth Jul 09 '21 at 14:20
  • I will leave the generic formula for another day :) lol The example was what i was wanting that you wrote above so that I understoood the Math that i had to execute. And yes. I did realise that a generic formula to cover all bases was rather impractical and unwieldy - so as you did taking each case individually was the proper approach. – Alex Ainsworth Jul 09 '21 at 14:24