3
$\begingroup$

enter image description here

From the picture above I have five slots and a bag of balls (three) of color -red, blue and green...

Question

Now whenever I choose a ball, I note the colour and replace it in the bag, then I randomly keep choosing balls (independent event) until all five slots are filled and put them back in the bag..

How can I derive a formula to find all possible repetitive arrangements (exhaustive approach) with the condition that a MAXIMUM of THREE balls of the same color are in the five slots.

Note:

I have ask a similar question at Finding the Total number of permutation using a selective formula

In the accepted answer, there were five slots and five letters and all arrangements with a maximum of three letters were found using a pattern

$3-1-1: \binom5{1,2,2}\binom5{3,1,1}$
$2-2-1: \binom5{2,1,2}\binom5{2,2,1}$
$2-1-1-1: \binom5{1,3,1}\binom5{2,1,1,1}$
$1-1-1-1-1:\binom55\binom5{1,1,1,1,1}$

Now in this question the number of balls and slots varies

I would like to build from the pattern above answer using multinomials (since I don't want to write a new algorithm again)

$\endgroup$
  • 1
    $\begingroup$ I don't think this is clear. What do the slots have to do with anything? Are you saying that when you note a color you write it in one of the slots, UNLESS doing so would violate the cap rule? But then...why not just ask "how many words on $\{R,B,G\}$ are there of length $5$ with no letter appearing more than $3$ times?" $\endgroup$ – lulu Aug 21 '16 at 19:18
  • $\begingroup$ yes I would like "how many words on {R,B,G} are there of length 5 with no letter appearing more than 3 times?" $\endgroup$ – repzero Aug 21 '16 at 19:28
  • $\begingroup$ @lulu note too order/arrangements counts $\endgroup$ – repzero Aug 21 '16 at 19:29
2
$\begingroup$

We will solve the problem: "how many words of length $5$ on $\{R,B,G\}$ are there in which no letter appears more than $3$ times".

Easier to work backwards. Without the cap rule there are $3^5$ possible words.

How many of these have exactly $4\;R's$? Well there are $5$ place to put the non-$R$, and $2$ options for what letter it is. Hence $10$. As there are three letter, there are exactly $30$ words of length $5$ in which some letter appears exactly $4$ times.

Now, of course there are eactly $3$ words in which a letter appears $5$ times.

Hence there are $30+3=33$ words of length $5$ in which some letter appears more than $3$ times.

It follows that there are $3^5-33=\fbox {210}$ words of length $5$ in which no letter appears more than $3$ times.

$\endgroup$

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.