help permutations and combinations question (1 Viewer)

happypolarbear944 · Jan 29, 2024

There are 50 balls that are colored either, red, yellow, green, purple, or blue. There must be at least 4 balls of each color and no color can be on more than 1/3 of the balls. How many combinations are there?

liamkk112 · Jan 29, 2024

we know that there are at least 4 balls of each colour, and there are five colours, so there are 20 balls already fixed in colour. this reduces the problem to 30 balls that can be coloured 5 different colours, and no colour can be on more than 1/3 of the balls. i am not good at combinatorics lol but hopefully this helps, i will try to come up with a solution

ISAM77 · Jan 30, 2024

It's been a while since I did this topic. Dunno if I'm right, but hoping to help you at least.

As Liam said, since there must be at least 4 balls of each colour; 4x5=20, gives us 20 balls fixed in place. Hence, we have to find the remaining combinations.

Since 1 colour can be no more than 1/3 of the balls. 1/3 * 50 = 16.67. 16 is the maximum for one colour out of the 50. But 4 of each have already been chosen to meet the minimum requirement. Hence, 12 is the maximum for one colour in the remaining 30 slots. We could say we have 12 red balls to choose from, 12 yellow, 12 green, 12 purple, and 12 blue; which is 60 balls in total. Now Choose 30 out of these 60 for all possible combinations.

I'm not confident about my answer as I haven't touched this topic in months. But if I am right:
60C30 = 1.18 * 10^17 would be my final answer.

s97127 · Jan 30, 2024

happypolarbear944 said:
There are 50 balls that are colored either, red, yellow, green, purple, or blue. There must be at least 4 balls of each color and no color can be on more than 1/3 of the balls. How many combinations are there?

I'm going to give this a try tonight. Where did you get this problem from?

s97127 · Jan 30, 2024

My answer is 17,151. Is it correct?

liamkk112 · Jan 30, 2024

ISAM77 said:
It's been a while since I did this topic. Dunno if I'm right, but hoping to help you at least.

As Liam said, since there must be at least 4 balls of each colour; 4x5=20, gives us 20 balls fixed in place. Hence, we have to find the remaining combinations.

Since 1 colour can be no more than 1/3 of the balls. 1/3 * 50 = 16.67. 16 is the maximum for one colour out of the 50. But 4 of each have already been chosen to meet the minimum requirement. Hence, 12 is the maximum for one colour in the remaining 30 slots. We could say we have 12 red balls to choose from, 12 yellow, 12 green, 12 purple, and 12 blue; which is 60 balls in total. Now Choose 30 out of these 60 for all possible combinations.

I'm not confident about my answer as I haven't touched this topic in months. But if I am right:
60C30 = 1.18 * 10^17 would be my final answer.

i think this is wrong, there are 50 balls not 60. also u havent considered the case where one colour does not take up 1/3 of the balls, eg 10 10 10 10 10 instead. tbh this question is really hard bc theres so many different cases to consider, the 1/3 restriction is kinda crazy

happypolarbear944 · Jan 31, 2024

bump!

ISAM77 · Jan 31, 2024

happypolarbear944 said:
bump!

Do you have the final answer?

ISAM77 · Jan 31, 2024

happypolarbear944 said:
There are 50 balls that are colored either, red, yellow, green, purple, or blue. There must be at least 4 balls of each color and no color can be on more than 1/3 of the balls. How many combinations are there?

@Luukas.2 . Reckon you could give this a crack if you have time pls?

happypolarbear944 · Jan 31, 2024

ISAM77 said:
Do you have the final answer?

really sorry, but i don't have the final answer

Luukas.2 · Jan 31, 2024

The problem is finding the number of different solutions of the equation

$r + y + g + p + b = 50$

where $r$ is the number of red balls, etc, subject to the constraints that:

$r,\,y,\,g,\,p,\ \text{and}\ b \in \mathbb{Z}^+$
$r,\,y,\,g,\,p,\ \text{and}\ b \ge 4$
$r,\,y,\,g,\,p,\ \text{and}\ b < \frac{50}{3}$

Equations like this are called Diophantine equations and the number of solutions can be counted by the "stars and bars" method - neither of which is formally in any HSC course. Without the constraints, the number of combinations / solutions would simply be:

$\binom{50-1}{5-1} = \binom{49}{4} = 211\ 876$

Taking into account the constraint that there must be at least 4 of each colour, and noting that the stars-and-bars approach is designed for at least one of each, we can transform using $r' = r - 3$ (and similar), so that $r'$ is the number of red balls more than 3, so that the minimum value of $r'$ is 1, consistent with how stars-and-bars counting works. This yields:

$\begin{align*} r + y + g + p + b &= 50 \\ (r' + 3) + (y' + 3) + (g' + 3) + (p' + 3) + (b' + 3) &= 50 \\ r' + y' + g' + p' + b' &= 50 - 5 \times 3 = 35 \end{align*}$

The number of solutions here is then

$\binom{35-1}{5-1} = \binom{34}{4} = 46\ 376$

However, this does not account for the constraint that $r' \le 13$ , etc. We now need to count the cases where one or more colours would have too many balls, and subtract those.

Can anyone complete the solution from here?

s97127 · Jan 31, 2024

happypolarbear944 said:
really sorry, but i don't have the final answer

Where did you get this problem from?

happypolarbear944 · Jan 31, 2024

s97127 said:
Where did you get this problem from?

idk friend gave it to me

s97127 · Jan 31, 2024

Luukas.2 said:
The problem is finding the number of different solutions of the equation

$r + y + g + p + b = 50$

where $r$ is the number of red balls, etc, subject to the constraints that:

$r,\,y,\,g,\,p,\ \text{and}\ b \in \mathbb{Z}^+$

$r,\,y,\,g,\,p,\ \text{and}\ b \ge 4$

$r,\,y,\,g,\,p,\ \text{and}\ b < \frac{50}{3}$

Equations like this are called Diophantine equations and the number of solutions can be counted by the "stars and bars" method - neither of which is formally in any HSC course. Without the constraints, the number of combinations / solutions would simply be:

$\binom{50-1}{5-1} = \binom{49}{4} = 211\ 876$

Taking into account the constraint that there must be at least 4 of each colour, and noting that the stars-and-bars approach is designed for at least one of each, we can transform using $r' = r - 3$ (and similar), so that $r'$ is the number of red balls more than 3, so that the minimum value of $r'$ is 1, consistent with how stars-and-bars counting works. This yields:

$\begin{align*} r + y + g + p + b &= 50 \\ (r' + 3) + (y' + 3) + (g' + 3) + (p' + 3) + (b' + 3) &= 50 \\ r' + y' + g' + p' + b' &= 50 - 5 \times 3 = 35 \end{align*}$

The number of solutions here is then

$\binom{35-1}{5-1} = \binom{34}{4} = 46\ 376$

However, this does not account for the constraint that $r' \le 13$ , etc. We now need to count the cases where one or more colours would have too many balls, and subtract those.

Can anyone complete the solution from here?

46376 - (5*5985 -10*70) = 17151

Luukas.2 · Feb 3, 2024

Carrying on from my earlier post, we had:

Luukas.2 said:
$r + y + g + p + b = 50$

where $r$ is the number of red balls, etc, subject to the constraints that:

$r,\,y,\,g,\,p,\ \text{and}\ b \in \mathbb{Z}^+$

$r,\,y,\,g,\,p,\ \text{and}\ b \ge 4$

$r,\,y,\,g,\,p,\ \text{and}\ b < \frac{50}{3}$

Equations like this are called Diophantine equations and the number of solutions can be counted by the "stars and bars" method - neither of which is formally in any HSC course. Without the constraints, the number of combinations / solutions would simply be:

$\binom{50-1}{5-1} = \binom{49}{4} = 211\ 876$

Taking into account the constraint that there must be at least 4 of each colour, and noting that the stars-and-bars approach is designed for at least one of each, we can transform using $r' = r - 3$ (and similar), so that $r'$ is the number of red balls more than 3, so that the minimum value of $r'$ is 1, consistent with how stars-and-bars counting works. This yields:

$\begin{align*} r + y + g + p + b &= 50 \\ (r' + 3) + (y' + 3) + (g' + 3) + (p' + 3) + (b' + 3) &= 50 \\ r' + y' + g' + p' + b' &= 50 - 5 \times 3 = 35 \end{align*}$

The number of solutions here is then

$\binom{35-1}{5-1} = \binom{34}{4} = 46\ 376$

However, this does not account for the constraint that $r' \le 13$ , etc. We now need to count the cases where one or more colours would have too many balls, and subtract those.

Suppose we set the number or red balls, [text]r[/tex] to be at least 17, producing an invalid solution:

$\begin{align*} r + y + g + p + b &= 50 \\ (r'' + 16) + (y' + 3) + (g' + 3) + (p' + 3) + (b' + 3) &= 50 \qquad \text{where $r'' = r - 16$, so that}\ r_{\text{min}} = 17 \\ r'' + y' + g' + p' + b' &= 50 - 4 \times 3 - 16 = 22 \end{align*}$

The number of cases with 17 or more of the red balls is

$\binom{22-1}{5-1} = \binom{21}{4} = 5\ 985$

This calculation includes cases where two of the colours exceed 17 balls because a solution like

$r'' = 1,\ y' = 15,\ g' = p' = b' = 2 \ \ \implies \ \ r = 17,\ y = 18,\ g = p = b = 5$

is valid. However, whilst the red exceding 17 is mandated, the colour of the other is not ( $r = 17,\ y = 5,\ g = 18,\ p = b = 5$ is equally valid). Multiplying by the options for the fixed ball will double count the two-exceed-17 cases, so we need to look at the case where two colours (say, red and yellow) both have 17 or more balls:

$\begin{align*} r + y + g + p + b &= 50 \\ (r'' + 16) + (y' + 16) + (g' + 3) + (p' + 3) + (b' + 3) &= 50 \qquad \text{where $r'' = r - 16$ and $y'' = y - 16$} \\ r'' + y'' + g' + p' + b' &= 50 - 3 \times 3 - 2 \times 16 = 9 \end{align*}$

The number of cases with 17 or more red and yellow is then

$\binom{9-1}{5-1} = \binom{8}{4} = 70$

which is also the number of any two-balls-exceeds-17 case.

The number with exactly one colour having 17 or more balls is then

$\binom{22-1}{5-1} - \binom{4}{1} \times \binom{9-1}{5-1} = \binom{21}{4} - 4\binom{8}{4}$

as we need to remove the yellow, pink, green, and blue exceeding 17 balls from the red base case.

It follows that the total number of possibilities is

$\begin{align*} \text{Total possibilities} &= \text{All solutions with at least 4 of each less the 1 or 2 balls exceed 16 cases} \\ &= \binom{34}{4} - \binom{5}{1}\left[\binom{21}{4} - \binom{4}{1}\binom{8}{4}\right] - \binom{5}{2}\binom{8}{4} \\ &= \binom{34}{4} - 5\left[\binom{21}{4} - 4\binom{8}{4}\right] - 10\binom{8}{4} \\ &= \binom{34}{4} - 5\binom{21}{4} + 20\binom{8}{4} - 10\binom{8}{4} \\ &= \binom{34}{4} - 5\binom{21}{4} + 10\binom{8}{4} \\ &= \binom{34}{4} - \left[5\binom{21}{4} - 10\binom{8}{4}\right] \\ &= 46\ 376 - (5 \times 5\ 985 - 10 \times 70) \\ &= 17\ 151 \end{align*}$

which matches @s97127's answer exactly.

s97127 said:
46376 - (5*5985 -10*70) = 17151

ISAM77 · Feb 4, 2024

yeah, nah. I've done all combinatorics questions in the cambridge y11 ext 1 book and this isn't like anything I've seen before. Sometime in future, I'll have a look at what stars and bars is. Thx always, Luukas

Luukas.2 · Feb 4, 2024

Suppose we had 10 balls of the five colours with no restrictions other than there must be at least 1 of each colour.

Imagine the colours as different bins, into which we put some number of each colour - blue, green, pink, red yellow (BGPRY).

A solution like B = 3, G = 1, P = 2, R = 3, Y = 1 is a solution of B + G + P + R + Y = 10. It can be represented as:

* * * | * | * * | * * * | *

which is 10 stars for the ten balls and four bars to separate bin 1, bin 2, bin 3, bin 4, and bin 5.

We need to place the four bars in between the stars, but must have a star to start and to end, and no consecutive bars (so no empty bins). There are thus 10 - 1 = 9 places to out the bars and 5 - 1 = 4 bars to place, hence the number of combinations is:

$\binom{10-1}{5-1} = \binom{9}{4} = \frac{9!}{4!5!} = \frac{9 \times 8 \times 7 \times 6 \times 5!}{4 \times 3 \times 2 \times 1 \times 5!} = 9 \times \frac{8}{2} \times 7 = 252$

ISAM77 · Feb 5, 2024

Luukas.2 said:
Suppose we had 10 balls of the five colours with no restrictions other than there must be at least 1 of each colour.

Imagine the colours as different bins, into which we put some number of each colour - blue, green, pink, red yellow (BGPRY).

A solution like B = 3, G = 1, P = 2, R = 3, Y = 1 is a solution of B + G + P + R + Y = 10. It can be represented as:

* * * | * | * * | * * * | *

which is 10 stars for the ten balls and four bars to separate bin 1, bin 2, bin 3, bin 4, and bin 5.

We need to place the four bars in between the stars, but must have a star to start and to end, and no consecutive bars (so no empty bins). There are thus 10 - 1 = 9 places to out the bars and 5 - 1 = 4 bars to place, hence the number of combinations is:

$\binom{10-1}{5-1} = \binom{9}{4} = \frac{9!}{4!5!} = \frac{9 \times 8 \times 7 \times 6 \times 5!}{4 \times 3 \times 2 \times 1 \times 5!} = 9 \times \frac{8}{2} \times 7 = 252$

This was really intuitive and easy to follow. Can do the original question now thx to this. Good stuff!

help permutations and combinations question (1 Viewer)

happypolarbear944

New Member

liamkk112

Well-Known Member

ISAM77

Member

s97127

Active Member

s97127

Active Member

liamkk112

Well-Known Member

happypolarbear944

New Member

ISAM77

Member

ISAM77

Member

happypolarbear944

New Member

Luukas.2

Well-Known Member

s97127

Active Member

happypolarbear944

New Member

s97127

Active Member

Luukas.2

Well-Known Member

ISAM77

Member

Luukas.2

Well-Known Member

ISAM77

Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)