Discrete

[hot kraken]

Let’s say there’s 10 red balls , 6 blue, 5 greens. How many ways to pick 4 balls if order doesn’t matter. How to do this type of sums. Also what will I do if order matters

[left compass]

Since all you are supposed to do is pick and not arrange or permute these picked balls, we can simply use the Combination Function by:

1. Tallying balls of all colours, since there is no specific condition placed on any particular balls you are supposed to pick on the basis of colour
   We get: 10+6+5=21 balls in total.

2. Now we can directly use the Combination Function as:
   C(21,4) = 21!/[(17!)(4!)].
   Which evaluates to the answer 5985.

[worn tartan]

that assumes the balls of the same colour are distinct

[left compass]

thats a horrible fucking error my bad

[hot kraken]

So how do we eleminate this

[worn tartan]

really? would something like 3red+1 blue constitute more arrangements than one then? im used to similar colours not being distinct implicitly in such questions

or did you mean something else that i missed

sure, but to answer this question would 3red+1 blue not be just one arranagement?

yes

like if when they give us a question like find the number of arrangements of the letters in the word "MISSISSIPPI", we implicitly assume the repeated letters are identical

is that not a common question in a combinatorics course

you can look up permutations with identical objects to see what im talking about

or i missed smth ur trying to say

idk

[worn tartan]

can we not do something like split 4 into the sum of 3 numbers,

consider the ordered triplet (r,b,g), we need to have r+b+g to equal 4 and r<=10, b<=6, g<=5

cases of the various splittings of 4 into 3 integers:

4--> 3 cases (4,0,0) (0,4,0) (0,0,4)
3+1---> permutation of 3,0,1 in 3 slots so 3x2x1
2+2--> permutation of 2,2,0 in 3 slots so 3x2x1/2=3 (since 2 idential 2's)
2+1+1--> permutations of 2,1,1 in 3 slots so 3x2,1/2=3 (since 1 identical 1's)

so 3+6+3+3=15?

im not sure if its correct tho

oh

nvm

Using this formula, 11 letters, 4P 41 2P 1M

so 11!/2!4!4!

wait, is this confirmed to be the answer?

i never encountered a combinatorics problem that doesnt consider similar colours to be identical

i doubt this one is different

this isnt the real world, this is pratice problem for a maths topic

😭 😭

okay if we tried to find the number of arrangements of the word BOOK, technically ii can label the 2 o's but you wouldnt be able to tell the difference so labelling them as distinct and as the same is just asking 2 differet questions

technically 11! and my asnwer are both correct in different contexts, but its a perfect valid question to wonder how many arrangements there would be since to if i just wrote 00BK you wouldnt be able to tell which O went first

[worn tartan]

and thats why its used as a example problem for the idea of permutations with identical objects

similar story for the balls

In a ideal where every red ball looked the same, you wouldnt be able to tell the difference

so its usually implicitly assumed to be identical in such questions unless specifically stated otherwise

sure, but if they wanted you to count the number of possible 4 digit passwords using the numbers 1 to 5 you wouldnt count 1223 and 1223 with the 2's arranged differently as different passwords, now would you?

mabye they are just curious and dont want to count ppiiiiissssm, ppiiiissssm and ppiiiissssm to be different arrangements counted in their answer

also this is just looking for real world applications for a concept

am i being baited

😭

i mean, you can see why they MIGHT want to

2x4x4?

so 32 i think

no, should be

2!4!4!

forgot to add ! earlier, braind fart

just multiplication principle

since adding assume they are

distinct

ah wait i used distinct in a different sens ehere lol

uh, you would add them if it was like how many ppiiiissssm's would there be if only one of p, i or s would be considered non-identicial at a time

like think of the the 2 cases where the 2 p's are arranges as p1p2 and p2p1

in each of those cases, the i's and s's can still be arranges differently

does that make more sense on why we use multiplication?

yeap

@crystal cargo also if your intrested you can look at help 21, someone asked help with a question with balls and got told to consider the balls as distinct

oh

its the same guy

maybe they got annoyed by us

😭

NUH UH!!

how would would it be 5, thats not possible

0,0,4 0,4,0 4,0,0 3,1,0 3,0,1 1,3,0 is already 6 if we consider (r,b,g) as the numbers of balls

typo of 15 surely

[olive gull]

Holy yap

In such questions when you are told you have 10 red balls it means the 10 red balls are identical, likewise for the other colors

Now, the exact amount of balls of each color here is a catch

Since you need to count only the amount of ways to pick 4 total balls and you have at least 4 balls of each color, you need only consider the following:

How many different ways do I have to gather 4 balls, some of which red, some blue, some green

And this is a classical problem

Denote by R, G and B the amount of respectively red, green and blue balls you will pick

One configuration of balls corresponds to each solution of the equation R+G+B=4

Where you seek solutions in non-negative integers

So the amount is 6 choose 2

Which is 15

6 comes from 4 (the total amount) + 2 (the number of variables - 1)

The 2 comes from the same consideration as the 2 which we used to get the 6

[worn tartan]

imsorry

https://tenor.com/view/bocchi-the-rock-bocchi-hehe-hehehe-anime-gif-27028096

[olive gull]

Have you never gone through a combinatorics course

[dusty cobalt]

If the balls aren't identifical then its just 20P4

Each color gotta be identical bro

[olive gull]

What you're telling me is "I know how to solve another problem so I'll be nitpicking"

The person who asked for help literally was wondering why the answer is 15

I believe that is reason enough to assume my interpretation is right

If you don't, you do you

I am plenty sure it's 15 because I know what I'm doing

#help-21 message

[hot kraken]

Okay i didn’t get this one answer. Like why 6? When our total colors 3
. What is consideration? Like is this like a formula or a way that we gonna add true repetition of a ball (as u adding 2) to the number of picks? Then dividing by 2! As two repeats?

Also smth else I noticed, if we do this way, then. No matter how many more balls I add

It’s going to be 15, if I just add colors of same ball

[olive gull]

It is a formula, but it's easy to derive

Imagine you have the equation x1+x2+..+xn = T and you wish to find the number of its solutions (as n-tuples) in non-negative integers (which number is always finite since each element in the tuple is a number between 0 and T)

Rewrite T as a sum of T-many ones, i.e. 1+1+1+...+1 where the number of occurrences of 1 is T

Now each solution corresponds to a "proper subdivision" of this sum of ones

By separating the sum into n-many sections we can extract a solution in the following way: sum up the 1s in the first section and this is the value for x1, sum up the 1s in the second section and this is the value for x2, and so on, sum up the 1s in the nth section and this is the value for xn

And conversely, if we have a solution we can construct the corresponding subdivision by doing the exact same thing in reverse, i.e. if we have a solution (x1, x2, ... , xn) we build a subdivision by grouping the first x1 1s together, then the first x2 remaining 1s together and so on

This shows that the number of solutions to the above equation is equal to the number of subdivisions of the sum of 1s (note that we allow some sections of the subdivision to be empty)

Now how do we count the number of subdivisions of the sum of 1s?

Well we need to divide the sum into n sections

So take (n-1) bars like this one: |

And treat them as dividing elements, i.e. we will put them among the 1s and the first section of 1s contains all 1s before the first occurrence of a bar, thr second section of 1s contains all 1s after the first bar and before the second bar, and so on, the nth section of 1s contains all 1s after the (n-1)st bar /// HERE is why in the binomial I said the number is 2 and not 3

For example with your problem we need to find the solutions of x1+x2+x3=4

So we write 4=1+1+1+1

And for example subdivide the sum like that:

1|+1+1|+1

Two bars separate three sections

And this generates the solution (1,2,1)

From now it's easy

We need to count the number of ways to place T many 1s and (n-1) many bars

Despite treating the bars as separators in a sum, it's better to ignore the plus signs since then multiple configurations of bars would correspond to the same subdivision

(I mean that we want to treat the partitions 1|+1+1|+1 and 1+|1+1+|1 as the same)

So instead we need the same sequence with the pluses omitted, so 1|11|1

Such sequences are of length T+(n-1)

And are uniquely determined by choosing (n-1) positions in which to put bars, the remaining positions get immediately filled by 1s

So the amount of those sequences of (T+(n-1)) choose (n-1)

In your particular problem, the value of T is 4 (the total number of balls you want to pick), and the value of n is 3 (the number of colors you may select)

So the total amount will be (4+3-1) choose (3-1)

[olive gull]

You also might want to google something like "stars and bars combinatorics" and you'll get plenty more explanations

I'm not too good at explaining combinatorics

[olive gull]

I'm not entirely sure what you mean here

But it is interesting to see how different modifications of the problems change the solution

If we add to the total number of red, blue and green balls among which we can pick, we don't change anything

So even if we had 600 red balls initially, 250 blue and 31 green then as long as we still want to pick 4 balls the answer will be the same

If we had more colors, for example yellow, and we still had at least 4 yellow balls

Then when we do the equation we would add an additional variable Y

So the value of n would change from 3 to 4, and the final answer would be (7 choose 3)

The problem gets trickier when some color has less balls than the total amount we can pick

Consider the following modification: we have 10 red, 10 green and 5 blue balls, and we want to pick 7 total balls among them

Then the equation approach does not quite work

Because if we do the equation R+G+B=7, then the solution (0,1,6) doesnt correspond to a way to pick the balls

Because we can't pick 6 blue balls among 5

Let's see how we can deal with this problem

We wish to find all solutions of R+G+B=7 in which B<=5

To do this, we will count all solutions of R+G+B=7 and then subtract the number of solutions in which B>=6

The unrestricted solutions we compute by the above formula: (7+3-1) choose (3-1)

The solutions in which B>=6 we compute in the following way

Since B has to be an integer that is at least 6, we can write it as B=6+B'

Now the restriction for B' becomes 6+B'=B>=6, i.e. B'>=0, so the restriction is that B' is just a non-negative integer

By substituting for B in the initial equation we get

R+G+6+B'=7

We can rewrite this as R+G+B'=1

And now we seek solutions for this new equation where each variable is just a non-negative integer, and this equation suits our formula

So its solutions are (1+3-1) choose (3-1)

This is the number of all solutions of R+G+B=7 in which the value of B is at least 6

So the number of solutions of that equation in which B<=5 is (9 choose 2) - (3 choose 2)

Things get trickier if two or more variables are bound from above

Imagine you have 14 red, 15 green and 16 blue balls and you want to pick a total of 35 balls

Now when we do the equation R+G+B=35 we only want to count the number of solutions in which R<=14, G<=15 and B<=16

And we have to use the same trick and the inclusion-exclusion principle

All solutions without following the restriction that each color has limited supply, are (37 choose 2)

Now we will get our answer by subtracting from that the number of solutions in which R>=15 OR G>=16 OR B>=17

And by the inclusion exclusion formula we get that

(R>=15 OR G>=16 OR B>=17) =
(R>=15) + (G>=16) + (B>=17) -

• (R>=15 AND G>=16) -
• (R>=15 AND B>=17) -
• (G>=16 AND B>=17) +

• (R>=15 AND G>=16 AND B>=17)

Where "(expression)" is short for the number of solutions which satisfy the expression

Since each of those expressions involves only lower bounds for the value of a variable, we can use the same trick as above to compute them

We are left to compute them

By using the same trick as above (when we substituted B' for B) we can compute:

(R >=15) = (22 choose 2)

(G>=16) = (21 choose 2)

(B>=17)=(20 choose 2)

For the expressions with two lower bounds we do a similar trick

For example for (R>=15 AND G>=16) we will put R=R'+15 and G=G'+16

By substituting in the equation R+G+B=35 we will get R'+15+G'+16+B'=35

Which simplifies to R'+G'+B'=4

So (R>=15 AND G>=16)=(6 choose 2)

Similarly we get that:

(R>=15 AND B>=17)=(5 choose 2)

(G>=16 AND B>=17)=(4 choose 2)

And finally, we have that (R>=15 AND G>=16 AND B>=17)=0 since if the variables satisfy this condition you will need to find the solution in non-negative integers of R'+G'+B'=-13 and you can't have non-negative integers add up to a negative integer

And now you plug the numbers into the above formula