General

Re: Another simple combinatorics question

ladyattis — Wed, 25 May 2011 18:59:37 GMT

Why use combinatronics for what can be solved easily with the pigeonhole principle?

Re: Another simple combinatorics question

S.N.P — Wed, 25 May 2011 18:56:29 GMT

Another question, good exercise. We have 10 prisoners who are to be placed in 5 cells, each of which has 2 bunks, how many pairings of prisoners are possible?

Re: Another simple combinatorics question

S.N.P — Wed, 25 May 2011 18:14:37 GMT

The problem is this, when you put the people into groups of 2 and 3, i.e when you count

30! / [ (2!)^6 * (3!)^6 ].

You don't only decide that Adam and Jessica are paired together, but also in which distinct "urn" they are paired in. Thus we can think of there 30 balls with the names of the persons and 12 urns in which to place these balls. 6 urns can fit 2 balls are labeled A2, B2, C2, D2, E2, F2 the others are labeled A3, B3, C3, D3, E3, F3.

So given that you have placed Adam and Jessica in A2, and Joe and Dianne in B2 etc, then yes there are 12! ways to place the urns on the 12 months. BUT, imagine that Adam and Jessica switched urn with Joe and Dianne, if we now placed these urns on the months again we would recount all those permutations that result in the same combination of names/months.

Re: Another simple combinatorics question

Smiling Dave — Wed, 25 May 2011 17:40:40 GMT

Thank you, SNP, that is a very clear analysis.

One final point. Can you [or anyone out there] tell me where the flaw is in my original reasoning? Why is it wrong to group the 30 people into sets of twos and threes, then put the twelve sets into the twelve months in 12! ways?

Re: Another simple combinatorics question

S.N.P — Tue, 24 May 2011 10:49:41 GMT

I think it's easier if you reverse the order, so we first choose which of the six months that will cointain 2 people and which that will contain 3.

12! / [ 6! * 6!]

Now, we line up all 30 people in an arbitrary manner.

Next we line up 30 tickets with the names of the months chosen in the first step. For example, If January has been chosen as one of the six months containing two people there will be two tickets with "Janurary" written on them, these two being indistinct.

Thus,

30! / [ (2!)^6 * (3!)^6 ]

Re: Another simple combinatorics question

Smiling Dave — Tue, 24 May 2011 00:29:36 GMT

Now, given that we have chosen a specific pairing/grouping of the persons, there are

12! / [6!*6!]

ways to place these pairings/groupings over 12 months.

Thank you for the reply, S.N.P.

Here's what's bothering me. The number you gave shows how many ways we can select 6 months out of twelve to be of one sort [in this case, destined to have two people born in them] and the other 6 of another sort [having three people born in them].

Say one of the groups is the two people Smith and Jones. Say January and February are two of the months selected to have two people. Having Smith and Jones born in January is not the same event as having them born in February. And I don't see where they are counted as two events in your scheme. It would seem to me that the only way to do that is to say, modifying your quoted statement:

Now, given that we have chosen a specific pairing/grouping of the persons, there are

12! [not 12! / 6!*6!]

ways to place these pairings/groupings over 12 months.

Re: Another simple combinatorics question

S.N.P — Mon, 23 May 2011 23:15:15 GMT

The total number of ways to place 30 people in 12 months

12^30.

Then we need to know in how many ways the persons may be paired up within the months. Here we have only chosen who will be paired with who, not in which month they will have their birthday. This is given by

30! / [ (2!)^6 * (3!)^6 ].

Now, given that we have chosen a specific pairing/grouping of the persons, there are

12! / [6!*6!]

ways to place these pairings/groupings over 12 months.

Another simple combinatorics question

Smiling Dave — Mon, 23 May 2011 19:51:05 GMT

The problem: Given thirty people, find the probability that among the twelve months
there are six containing two birthdays and six containing three.

My analysis: Total number of ways to have 30 people have birthdays is 12^30 [Book says to assume each month equally likely]. We call this number A.

Divvy the thirty people up into six groups of two and six groups of three in 30! / [2!]^6 *[3!]^6 ways. Call this number B.

Then consider the twelve months as twelve boxes in a row, and drop the twelve groups of people you just made, one group to a box, in 12! ways. Call this number C.

Probability is thus B*C / A.

Sadly, the book disagrees. The answer in the back has A and B alright, but replaces C with 12! / [6! *6!]

If you remember my previous post with a combinatorics problem, my mistake then was dropping the people into boxes one at a time, with one left over who I dropped into a random box. People pointed out correctly that this leads to double counting. This time I think I avoided that problem by grouping the people first, then dropping them in. And yet the book disagrees.

Any insights?