Combinatorics question (1 Viewer)
- Thread starter milton
- Start date
no, that is incorrect because you're double-counting some cases where a certain person appears in your first r selection to put 1 in each group, and that certain person appears later in the same arrangement of groups in the r^(n-r) part
e.g. take n=3, r=2
there are 3 possible arrangements of groups ie
(A) (BC)
(B) (AC)
(C) (AB)
but your formula gives 3C2*2^(3-2)=6
this problem is much trickier than it seems
e.g. take n=3, r=2
there are 3 possible arrangements of groups ie
(A) (BC)
(B) (AC)
(C) (AB)
but your formula gives 3C2*2^(3-2)=6
this problem is much trickier than it seems
airie
airie <3 avatars :)
I hate typing in VB codes :S
One group with n-r+1 people, the rest with 1:
[nCn-r+1*r-1C1*r-2C1*...*1C1] / (r-1)!
One group with n-r people, one with 2, the rest with 1:
[nCn-r*rC2*r-2C1*...*1C1] / (r-2)!
One group with n-r-1 people, two with 2, the rest with 1:
[nCn-r-1*r+1C2*r-1C2*r-3C1*...*1C1] / [2! * (r-2)!]
... etc. until all possibilities exhausted.
And add them all together.
...Ugh. Such disgusting counting. x.x
One group with n-r+1 people, the rest with 1:
[nCn-r+1*r-1C1*r-2C1*...*1C1] / (r-1)!
One group with n-r people, one with 2, the rest with 1:
[nCn-r*rC2*r-2C1*...*1C1] / (r-2)!
One group with n-r-1 people, two with 2, the rest with 1:
[nCn-r-1*r+1C2*r-1C2*r-3C1*...*1C1] / [2! * (r-2)!]
... etc. until all possibilities exhausted.
And add them all together.
...Ugh. Such disgusting counting. x.x
I
icycloud
Guest
SPOILER WARNING
Do not click on the following link if you are trying to work this out for yourself.
For the rest, this is called a Stirling number of the second kind: http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html. I've had fond memories of these lol.
Do not click on the following link if you are trying to work this out for yourself.
For the rest, this is called a Stirling number of the second kind: http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html. I've had fond memories of these lol.
i came across Stirling numbers of the 2nd kind here http://www.stanford.edu/~dgleich/publications/finite-calculus.pdf. apparently they're used in discrete calculus (lol an oxymoron) to sum power series
Maybe I'm missing something but you are simply solving an equation of the form:
x1 + x2 + x3 + ... + xr = n
ie. placing n pidgeons into r holes (d/w im not gonna use pidgeon hole principle, its just an analogy)
now since we have the condition that xi > 0
we solve:
y1 + y2 + y3 + ... + yr = (n - r)
[where we have taken into account that every hole MUST have a pigeon, and as such reformulated the problem to consider the r holes and (n - r) remaining pidgeons]
the number of solutions to such a problem is:
(n - r + r - 1) C (r - 1)
= (n - 1) C (r - 1)
unless i misunderstood the problem ;d
x1 + x2 + x3 + ... + xr = n
ie. placing n pidgeons into r holes (d/w im not gonna use pidgeon hole principle, its just an analogy
)now since we have the condition that xi > 0
we solve:
y1 + y2 + y3 + ... + yr = (n - r)
[where we have taken into account that every hole MUST have a pigeon, and as such reformulated the problem to consider the r holes and (n - r) remaining pidgeons]
the number of solutions to such a problem is:
(n - r + r - 1) C (r - 1)
= (n - 1) C (r - 1)
unless i misunderstood the problem ;d
MY LAST THOUGHT - then sleep
FROM BEFORE:
x1 + x2 + x3 + ... + xr = n
now since we have the condition that xi > 0
we solve:
y1 + y2 + y3 + ... + yr = (n - r)
[where we have taken into account that every hole MUST have a pigeon, and as such reformulated the problem to consider the r holes and (n - r) remaining pidgeons]
the number of solutions to such a problem is:
(n - r + r - 1) C (r - 1)
= (n - 1) C (r - 1)
BUT we have the problem that people are distinguishable, there is nCr ways to choose the r original people in shifting from x to y
once we are at the y-problem, the rest of my solution is fine because the holes ARE distinguishable.
so amended solution : nCr . (n-1)C(r-1)
FROM BEFORE:
x1 + x2 + x3 + ... + xr = n
now since we have the condition that xi > 0
we solve:
y1 + y2 + y3 + ... + yr = (n - r)
[where we have taken into account that every hole MUST have a pigeon, and as such reformulated the problem to consider the r holes and (n - r) remaining pidgeons]
the number of solutions to such a problem is:
(n - r + r - 1) C (r - 1)
= (n - 1) C (r - 1)
BUT we have the problem that people are distinguishable, there is nCr ways to choose the r original people in shifting from x to y
once we are at the y-problem, the rest of my solution is fine because the holes ARE distinguishable.
so amended solution : nCr . (n-1)C(r-1)
Mill, refer to my counterexample in post #3 http://community.boredofstudies.org/2409838/post-3.html
i believe you are double counting some cases, namely when a particular person appears in your first r groups to guarantee every hole has something, and when that same person appears in the later group where it can go anywhere, and ends up in the same group
anyway, just read http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Stirling_numbers_of_the_second_kind
i believe you are double counting some cases, namely when a particular person appears in your first r groups to guarantee every hole has something, and when that same person appears in the later group where it can go anywhere, and ends up in the same group
anyway, just read http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Stirling_numbers_of_the_second_kind