How to get my head around combinatorics?

I just get confused so easily, lets say I have 8 muffins each of different flavor:

How many ways are there to select 16 muffins? I originally thought 8^16 but assume that we dont care about ordering it should be much much lower than this.

According to my textbook its just "n+k-1 choose k-1" where n = # objects and k = #types which gives us 23c7 = 245157

This doesnt make any sense to me.

If the question were "how many ways can we select 2 muffins" then obviously its 8c2 if we don't allow repetition, and 8c2 + 2*8 if we do allow repetition.

But when r > n in the case of the above, choosing 16 muffins from 8 types I dont know what to do because the question evaluates to 8c16 which is 0, so I have to mindlessly follow the formula which is stupid if I don't even understand it at an intuitive sense.

The book tries to explain it by modeling it into some retarded dogshit using "strings of 1's and 0's" or some retardation because they can't even explain it coherently themselves.

Can anyone explain to me how to pick 16 muffins from 8 different types in an understandable way?

Other urls found in this thread:

en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
twitter.com/AnonBabble

>and 8c2 + 2*8 if we do allow repetition.

I meant 8c2 + 8

bump

gonna try to help.
you want to choose 16 muffins. see those 16 as a vector, a list, whatever you wish.

(a) If you care about the order :
muffin 1 : you have 8 possibilities.
muffin 2 : same.
...
muffin 16 : same.
total of possibilities : 8^16

(b) If you don't care about the order :
Let's take an example list. Let's say muffin 1 is 1, etc.
[1,2,1,4,2,3,4,8,8,1,3,3,2,7,6,6]
Saying that you don't care about the order is saying that the above list is the exact same as this one :
[1,1,1,2,2,2,3,3,3,4,4,6,6,7,8,8]
or any other one that have 3 1s, 3 2s, 3 3s, ...

So your list is fully represented by the numbers of 1s, 2s, ... up to 8s. You now have to count the number of lists of 8 integers ranging from 0 to 16 so that the sum of those integers is 16.

help please?

a) yes thats understandable and trivial

b) is more of my concern, I don't care about order so I allow repetitions (the above list is the same as the below list but it is also counted).

According to the book there are 27 choose 7 ways of doing this, what id like is an intuitive understanding for this. (They use the formula n+k-1 choose k-1 to solve this) but I don't really get the intuitive sense behind the formula

23 choose 7*

Here is a reasoning. Tell me if it makes sense.

We need to choose 8 integers between 0 and 16 which all summed make 16. Do you agree? Let's call them ai :
choose 0 ≤ ai ≤ 16 with
a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 = 16

Let's work with 16 as n.

(a) I start with a simpler case. Choosing two numbers which sum is n.
a1 + a2 = n
with 0 ≤ ai ≤ n
Let's call choice(2,n) this number of possibilities. .
Starting with a1, we have n+1 possibilities. Once a1 is chosen, we have no choice fore a2 : a2 = n - a1. So choice(2, n) = n+1.

(b) Let's see now choice(3, n).
a1 + a2 + a3 = n
with 0 ≤ ai ≤ n
Suppose we choose a1, say k. Then we have to choose a2 + a3 = n - k. We have the case in (a) with the sum being n-k instead of n. The number of choices is choice(2,n-k).
So:
choice(3,n) = sum(k=0 to n) choice(2,n-k)
= sum (k=0 to n) n+1-k
= sum (j=1 to n+1) j
= (n+1)(n+2)/2

(c) again, choice(4, n) = sum (k=0 to n) choice(3,n-k).

If I were you, I would program this recurring function up to choice(8,n), with n=16.

I'm a complete brainlet when it comes to combinatorics and probability.

I've gone through the first chapters of several books several times and can solve the problems but never actually understand the material on an intuitive level.

After having made a little research, it appears that your problem exactly falls under the very well studied problem called "counting with repetitions".

My little algorithm above makes "intuitive" the counting, but yields a number that does not help seeing the "big picture" with n=16 and your 8 muffins.

Here is another point of view.
Let's define:
Def1: a k-combination with repetition of elements of a set E with n elements is the selection of k objects of E.
Def2: a k-combination with repetition is a function defined on E that goes in [1,k] (it associates an element of E with the number of times it is counted, ie its number of repetitions) such that sum (x in E) f(x) = k

Here, k=16 and n=8 (reversed notation compared to the above calculations, sorry).

The counting you want to make is the counting of the 16-repetitions in a set of cardinal 8.

The main result is the following :
Proposition: the number of k-combination with repetition of elements of a set E of cardinal n is equal to the polynomial coefficient (n+k-1, k) = (n+k-1)! / k! (n-1)!

There are several demonstrations for this. See the wikipedia page in french, for example.

If we apply this result to your case, then we get to calculate:
k=16
n=8
n+k-1 = 23
n-1 = 7

23! / 16! 7! = 245 157 possibilites.

Well you just told me the formula... but I dont understand it intuitively, I mentioned this in the op

I dont understand at all

>muh intuition fags
the worst kind of mathematics students

I dont understand, Im trying with small numbers but I dont even get whats happening

if 3 permutation 2 = [12] [21] [13] [23] [31] [32]
3 combination 2 = [12] [23] [13]
the proposed formula gives 4 combination 1 = 4but what does that mean
what extra thing is accounted for
(n objects = 3, k types = 2)

This is the correct way to do it. This is how you would be taught it in a discrete class or even intro to proofs.

What is it you don't understand in ? Are you familiar with recurring functions / series ?

I will try to explain in another way.

A)
Let's assume you have k=5 balls of n=3 different kinds, and you want to put them into 3 different boxes. A box can be represented by a vertical line I, and a ball can be represented by a O. For example, the scheme below:
OO I O I OO
says that you have 2 balls of the 1st kind, 1 of the 2nd, 2 of the third kind. Do you agree that this scheme is equivalent to the lists we talked about earlier? The above scheme would be equivalent to the list [2,2, 1,2,2].

B)
The scheme is thus composed of k + n - 1 symbols (-1 because we don't need symbol at the extremities). Here 5 + 3 - 1 = 7 symbols. Do you agree with that?

C)
Now, we can say that the schemes as the one above are given by simply choosing where to put the O's, when the I are given anyways. For instance, if you were to place the O's one by one, the scheme would start with II. Then it could become OII, then OOII, then OOIOI, and so on, reaching the final state of the scheme in k steps. Alright?

D)
So, we are choosing the place of k symbols among k + n - 1, which can be made of (n+k-1, k) different ways. This is how you get the formula stated above.

Are you convinced?

>sorry mistake
>to the list to the list [2,2,1,3,3].

>sorry again
>to the list [1,1,2,3,3].

>(n objects = 3, k types = 2)
Watch out, in the above formulations:
* n in the number of types
* k the number of objects you pick.

In your case,
n=8 types
k=16 muffins

intro to probability and stats is when I realized I was a brainlet and changed my major to comp e

this thread makes my head hurt

>You now have to count the number of lists of 8 integers ranging from 0 to 16 so that the sum of those integers is 16.
not OP
but why is this listlength used in a division rather than subtracted from the firstlength?

At first you count all permutations, then you remove then you remove permutations that are equivalent. But my head still can not entirely understand why division rather than subtraction is used in this removal.

I don't think I fully understand what you mean by "subtraction" and "division".
I'll try to make it clearer.

There is no division, the fact that you see a division is probably due to the awkward choice of numbers, the fact that 16 is the double of 8 is pure chance.

Let's change the figures and take 11 picks among a set of 3 muffins instead.

A pick of 11 muffin is modeled by a list. Let's call type (a) this kind of list :

[1,3,1,1,2,1,3,2,2,1,2]

The fact that we don't care about the order tells us that all lists that have the same occurrences of 1s, 2s and 3s as the list above are counted as 1, they are all equivalent. If the only relevant data is the counting of occurrences, you can agree that we can define another type of list representing the pick. Let's call this second type (b) :

[5,4,2]

So, in order to count all the lists of type (a), we now count the number of lists of type (b).

So that the initial problem is rewritten in another combinatorics problem:

Counting the distinct lists
[a1, a2, a3]
with 0 ≤ ai ≤ 11
and a1+a2+a3 = 11

(this latter sum representing the total number of pickings of objects, which is 11)

that makes sense

I was thinking moreof nCr being the same as nPr except divided by the number of permutations that are equivalent, if that makes sense

nPr = n(n-1)...(n-k+1).
The writing with a division is useful and very natural, but not particularly meaningful: nPr = n! / (n-k)!

n! is the number of permutations of n objects.
(n-k)! is the number of permutations of (n-k) objects.

We don't do n! - (n-k)! though.

nPr makes sense to me
nCr less so

Let's consider n elements. Now we are making lists of those elements, in which the order is not taken into account (this is the difference between combination and permutation). We are counting them.

Lists of 1 element:
You have n choices for your element.
You then have n distinct lists.
Each list can be permuted 1 different way.
Total number is n

Lists of 2 elements:
You have n(n-1) choices for your elements.
You then have n(n-1) distinct lists.
Each list can be permuted in 2 different ways. So 2 lists are counted as one. If 2 is counted 1, n(n-1) is counted n(n-1)/2 (proportionality).
Total number of lists is: n(n-1)/2

Lists of 3 elements:
You have n(n-1)(n-2) choices for your elements.
You then have n(n-1)(n-2) distinct lists.
Each of thoses lists of 3 elements can be permuted in 3x2 different ways. So 3x2 lists are counted as one. If 3x2=6 is counted 1, n(n-1)(n-2) is counted n(n-1)(n-2)/6 (proportionality).
Total number of lists is: n(n-1)(n-2)/3x2

And so on.

The division by k! is just saying "all of those k! equivalent lists are counted as 1".

>Each of thoses lists of 3 elements can be permuted in 3x2 different ways. So 3x2 lists are counted as one. If 3x2=6 is counted 1, n(n-1)(n-2) is counted n(n-1)(n-2)/6 (proportionality).
>The division by k! is just saying "all of those k! equivalent lists are counted as 1".

thanks, it made it a bit more clear
I can accept that it leads to the correct count and I see that each list is counted k! times, and need to be accounted for
though I do not entirely understand why it is dividing leads to the correct count, even if I can go on just accepting that it is the case

lmao, let smart people like me and t. tao deal with combinatorics and stick to calc iii like every other wannabe pleb

thanks, I'm positively glad if I could help.

I can give you a last tip. If you want to convince yourself, just make packs, like when you were in school. I am being serious because it is a very handy way to think about counting (even thinking about how we group units, which determines the counting system we use: decimal, octal, whatever).

Can you please imagine your n(n-1)(n-2) lists for me? See, they all are in front of you, like little balls in the playground we we were kids.
Now, make packs of 6 of them, because you know that 6 of them are alike and you want to group them.

Question is: how many packs of 6 can you make?

unless I misunderstand you pick two of the length 3-lists to make a pack of 6, and each choice can be permuted 2x1 times, so m(m-1)/2

is the division to distribute in some handwavy sense the [correction of] repeated countings of each list over the total?

>you pick two of the length 3-lists to make a pack of 6
No, I make packs of 3!
And 3! happens to be 3x2x1 = 6 = 2 times the length of lists, but this is no general rule.
When you're counting lists of 5 elements, you make packs of 120 = 5!
When you count lists of k elements, you make packs of k!

>m(m-1)/2
this is the counting in the case of lists of 2
total number of lists = m(m-1)
size of packs for grouping lists that are counted as one = 2! = 2
mC2 = m(m-1)/2

oh wait right so I think I understand
so the pool of elements is say indexed from 1 to n
and the lists of length 3 that contain the same set of indexes in some order make a pack
and each pack counts as one

and each pack contains the same amount of items,
and each item uniquely maps to one and only one pack
so dividing by the number of items in a pack results in number of packs, which is the number of combinations

>and each item uniquely maps to one and only one pack
I mean, each set of items(indexes) of length 3 which is what the original n(n-1)(n-2) counts
but yeah

that's it user, that's very much it

>and each pack contains the same amount of items
yes, it contains k! items, where k is the length of the lists you're counting

thanks a ton, this was my main trouble with combinatorics

applying it was not too problematic without understanding it completely, but it still felt a bit dodgy

The process of making packs is the exact purpose of equivalence classes. Two elements are said equivalent if they are in relation. They are considered as one, as regards to a given relation of course.

The lists that have the same elements but not in the same order is an example.
Another example is: two straight lines in the affine space are considered equivalent if they are parallel.
Another famous example : in [maths] \mathbb{Z} [/maths], given a number [maths] n[/maths], two numbers [maths]a[/maths] and [maths]b[/maths] are considered equivalent if they have the same remain in the euclidian division by [maths] n [/maths] : [maths] a \mathcal R b [/maths] if [maths] a = b (mod n) [/maths]. This transforms Z into a finite set of n elements which has amazing characteristics. Especially is n is prime.

The process of making packs is the exact purpose of equivalence classes. Two elements are said equivalent if they are in relation. They are considered as one, as regards to a given relation of course.

The lists that have the same elements but not in the same order is an example.
Another example is: two straight lines in the affine space are considered equivalent if they are parallel.
Another famous example : in [math] \mathbb{Z} [/math], given a number [math] n[/math], two numbers [math]a[/math] and [math]b[/math] are considered equivalent if they have the same remain in the euclidian division by [math] n [/math] : [math] a \mathcal R b [/math] if [math] a = b (mod n) [/math]. This transforms Z into a finite set of n elements which has amazing characteristics. Especially is n is prime.

Let us take [math]n[/math] an integer.
Let [math]E[/math] be a set of [math]n[/math] elements.

Let [math]k[/math] be another integer [math]k ≤ n[/math].
Let [math]L_k (E)=L_k[/math] be the set of lists of elements of [math]E[/math] with [math]k[/math] elements.
We know that [math]\#L_k = n(n-1)(n-2)...(n-k+1)![/math].

Let [math]\mathcal{R}[/math] be the binary relation defined by: [math]\forall a, b \in L_k, a \mathcal{R} b[/math] if [math]a[/math] and [math]b[/math] have the same elements but not in the same order. Mathematically, it is written: there exists a permutation [math]p[/math] that transforme [math]a[/math] in [math]b[/math], ie : [math]p : L_k \longmapsto L_k[/math] bijective so that [math]p(a)=b[/math]. A permutation is another word for a bijection in the case of finite sets.

We can show that [math]\mathcal{R}[/math] is an interesting type of relation : an equivalence relation. Therefore we can "group" the elements of [math]L_k[/math] through this relation. Given a list [math]a[/math], the equivalence class of [math]a[/math] is a subset of [math]L_k[/math] where all elements are in relations with [math]a[/math] (and with each other): ie it is the subset of [math]L_k[/math] where all lists have the same elements, whatever order they are in. It is the exact definition of what we called "packs" above.

More precisely. Let [math]a \in L_k[/math], we define [math]â=\{ b \in L_k, b \mathcal{R} a\}[/math]. So for [math]a[/math], [math]â[/math] denotes the "pack" to which it belongs (with other elements). We can prove the equivalence classes form a partition of [math]L_k[/math].

this makes sense yes

Read about the stars and bars method on wiki (Th 2)

en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) .

Your problem is like putting n indistinguishable objects (muffins) into k distinguishable boxes(colours).

Therefore you will have 16 stars and 7 bars (k-1 = 8-1 =7) which divide the stars into 8 different colours.

In your problem ,a colour may not be present in your selection, so two or more bars may be adjacent or a bar may occupy the starting or ending positions. Hence you simply have to choose k-1 positions for the bars (or n positions for the stars) from the total of n+k-1 stars and bars .

The answer is 23c7 = 23c16 = 245157

this has been said here

so you just read the formula and memorize it? Why take math u biology faggot

OP here cant believe this thread is still up, I understand this explanation which is also in my book but it feels like a cop out, I feel like the following:

>I dont intuitively understand problem A
>I model problem A into problem B which makes sense and is logically equivalent
>Solving problem B is logically equivalent to solving problem A
>I have solved problem A by solving problem B
I don't feel this is the right thing to do, after 2hours when I made this thread a couple of days ago I spent around 3 hours doing different combinations of stuff and just looking at the difference between the answer of repetition allowed / not allowed with ordering not mattering in both cases, afterward I thought I had it but looking back on this thread it still seems like I didn't truly understand it.

for I just didn't understand it at all, I don't understand why were talking about taking 8 integers and summing them to have a total value of 16, so everything afterwards doesnt mean anything to me, id prefer to stick to just the 8 types of muffin choosing 16 muffins example because I know whats "happening"

I dont know if im making any sense at all but I am just trying to """"realize"""" why n+k-1 choose n (or the equivalnet n+k-1 choose k-1) {here n= number of objects and k=types, this is how its defined in my book so Id rather not confuse myself with notation}. I agree that your modeled Ball and Box analogy makes sense and is correct but it feels like im cheating.

I took another approach and looked at it through the factorial notation, which is (n+k-1)!/n!*(k-1)! but alas AGAIN I cannot really understand it without using the ball and box's to visualize and accept what the reality of the equation is telling me.

Fuck man I don't know if im autistic or brain damaged but I just want to "feel" the equation if you know what I mean... I don't want to RELY on an analogy for me to intuitively understand it.

Sorry for making you type so much

also I just came to sci and saw this thread was still up so its very late... I will have to re-read everything in this thread and see the replies tomorrow which could be more than 15 hrs time sorry

sry for being brainlet

Halp

2/10

hao?

is it the probability of getting a sour from 6 purchases? Or the prob that the 6th one is gonna be the sour one?

you tell me sensei
you seem to have knowledge
go now and do the job
.
.
please do the job in both cases

mo~

user-kun can you just do it for me I am a brainlet desu

iie

mô burueinuletu-desu yo.

gambatte kudasaine.

we're all waiting on your answer.

yada yo! user-kun!!

just do it for me pls i just can't think anymore i fucked up an open book test by not bringing a FUCKING BOOK pls it's a blessing im still motivated to do some math.