Year 12s: what will be the first way you research your future options? >>

Combinations problem

My question is based on MOG 2011 problem 2:
https://bmos.ukmt.org.uk/home/ukmog-2011-solutions.pdf

In general, if there are n items to placed exhaustively into 3 boxes, (n+2)c2 gives the number of possible arrangements. Take n = 3 for example:

Combinations of the form:

o
o
o
_ _ _ (3 permutations)

o
o o
_ _ _ (6 permutations)

o o o
_ _ _ (1 permutation)

Total = 5c2 = 10 possibilities.

Now I'm wondering if there's a more intuitive way to visualise why the formula (n+2)c2 gives the correct answer, than the way given in the MOG solutions, which roughly states (again using the n = 3 example):

There are three items (let's say balls) to be placed into three boxes (A,B,C from left to right)...

Take the arrangement of balls:

O O O

and place two separators between them...

O | O O | (for example)

This instance corresponds to 1 ball in box A, 2 balls in box B, and 0 balls in box C.

Now if I'm understanding it correctly, this method is essentially saying that there are 5 possible positions for the two separators, as follows (underscores denoting possible positions for the separators):

_ O _ O _ O _ _

My issue with this is the asymmetry: it doesn't seem to allow for the possibility of 0 balls in box A, 0 balls in box B, and 3 balls in box C.

Is there a more intuitive way to visualise how it is that the formula (n+2)c2 holds?

Thanks.

(edited 5 years ago)

Reply 1

DFranklin

Original post by jameshyland29

My issue with this is the asymmetry: it doesn't seem to allow for the possibility of 0 balls in box A, 0 balls in box B, and 3 balls in box C.

||OOO, surely?

Possibly stating the obvious, but the "|" don't define the boxes, they define the gaps between the boxes, so to speak.

Reply 2

jameshyland29

While on the subject (I'm hoping there's somebody out there who finds these problems as easy and enjoyable as I find them hard and enjoyable!)...

https://www.cl.cam.ac.uk/admissions/undergraduate/csat/practice/p2/q17

(ii) You have n distinct balls {1,2,3...N} to be placed in N distinct buckets. In how many ways can this be done such that one buckets remains empty:

Can anybody spot the flaw in the following argument?

Given a row of N buckets:

There are Nc2 ways to choose the positions of the empty bucket and the bucket that contains 2 balls.

There are Nc2 ways to choose the two balls that go in the same bucket.

There are then (N-2) buckets and (N-2) distinct balls remaining which can be assigned in (N-2)! ways.

So this gives:

Nc2 x Nc2 x (N-2)! which is apparently only half the correct value. My solution makes sense in my head so I'd be really grateful if someone can point out where the factor of 2 that I'm missing comes from.

Thanks.

(edited 5 years ago)

Reply 3

jameshyland29

Original post by DFranklin

||OOO, surely?

Possibly stating the obvious, but the "|" don't define the boxes, they define the gaps between the boxes, so to speak.

Well that's what I'd expect, but then where exactly are the five places from which two are chosen?

_ _ O_O_O_ _

that's six places!?

Reply 4

DFranklin

Original post by jameshyland29

Well that's what I'd expect, but then where exactly are the five places from which two are chosen?

_ _ O_O_O_ _

that's six places!?

I feel you're looking at this the wrong way; my immediate reaction is "you're looking for arrangements of IIOOO", so there are 5 places. (*)
So perhaps what you're really asking is why you're counting arrangements of IIOOO. To me, it's because each "I" indicates a gap between boxes (and so there are 2 of them), and you have 3 balls. You need to convince yourself that there's a 1-1 correspondence between arrangements of IIOOO and distributions of the balls.

Alternatively (and I think you might be happier with this):

For each box, write "O" the number of times there are the ball in the box, then write "I"

Note however that the position of the last "I" is fixed (it's always the last letter written), so we can ignore it.

(*) I feel this possibly doesn't directly answer your question, but then I have no idea what _ _ O_O_O_ _ is supposed to reference, so I have no idea how to help directly.

Reply 5

jameshyland29

Original post by DFranklin

my immediate reaction is "you're looking for arrangements of IIOOO", so there are 5 places.

I see that straight away now. Thank you. You'll be glad to hear there's no need for me to attempt to explain the underscore system!

Reply 6

jameshyland29

Original post by jameshyland29

While on the subject (I'm hoping there's somebody out there who finds these problems as easy and enjoyable as I find them hard and enjoyable!)...

https://www.cl.cam.ac.uk/admissions/undergraduate/csat/practice/p2/q17

(ii) You have n distinct balls {1,2,3...N} to be placed in N distinct buckets. In how many ways can this be done such that one buckets remains empty:

Can anybody spot the flaw in the following argument?

Given a row of N buckets:

There are Nc2 ways to choose the positions of the empty bucket and the bucket that contains 2 balls.

There are Nc2 ways to choose the two balls that go in the same bucket.

There are then (N-2) buckets and (N-2) distinct balls remaining which can be assigned in (N-2)! ways.

So this gives:

Nc2 x Nc2 x (N-2)! which is apparently only half the correct value. Can anybody spot where the missing factor of 2 arises?

Thanks!

Original post by jameshyland29

While on the subject (I'm hoping there's somebody out there who finds these problems as easy and enjoyable as I find them hard and enjoyable!)...

https://www.cl.cam.ac.uk/admissions/undergraduate/csat/practice/p2/q17

(ii) You have n distinct balls {1,2,3...N} to be placed in N distinct buckets. In how many ways can this be done such that one buckets remains empty:

Can anybody spot the flaw in the following argument?

Given a row of N buckets:

There are Nc2 ways to choose the positions of the empty bucket and the bucket that contains 2 balls.

There are Nc2 ways to choose the two balls that go in the same bucket.

There are then (N-2) buckets and (N-2) distinct balls remaining which can be assigned in (N-2)! ways.

So this gives:

Nc2 x Nc2 x (N-2)! which is apparently only half the correct value. Can anybody spot where the missing factor of 2 arises?

Thanks!

Bump for the second problem in this thread that I'm still a bit baffled by!

Reply 7

DFranklin

Original post by jameshyland29

Bump for the second problem in this thread that I'm still a bit baffled by!

The order of the two "special" buckets matters (since they are special in different ways).

Reply 8

jameshyland29

Ah yes that's it. Thank you once again!

Reply 9

DFranklin

Original post by jameshyland29

Ah yes that's it. Thank you once again!

No problem.

I suspect you already know this, but it's definitely a good idea to try small examples on problems like this to check your answer/thought process (or just to get some ideas).

Reply 10

jameshyland29

Original post by DFranklin

No problem.

I suspect you already know this, but it's definitely a good idea to try small examples on problems like this to check your answer/thought process (or just to get some ideas).

If anything I do too much of this, so that I suspect my exam papers are going to end up in a horrific mess. What would you say is the optimal layout for this "rough" work -- in a margin down the side, on a separate page, or neatly as part of the main argument?