Combinations problem Watch

jameshyland29
Badges: 9
Rep:
?
#1
Report Thread starter 1 week ago
#1
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.
Last edited by jameshyland29; 1 week ago
0
reply
DFranklin
Badges: 18
Rep:
?
#2
Report 1 week ago
#2
(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.
0
reply
jameshyland29
Badges: 9
Rep:
?
#3
Report Thread starter 1 week ago
#3
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/...ractice/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.
Last edited by jameshyland29; 1 week ago
0
reply
jameshyland29
Badges: 9
Rep:
?
#4
Report Thread starter 1 week ago
#4
(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!?
0
reply
DFranklin
Badges: 18
Rep:
?
#5
Report 1 week ago
#5
(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.
0
reply
jameshyland29
Badges: 9
Rep:
?
#6
Report Thread starter 1 week ago
#6
(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!
0
reply
jameshyland29
Badges: 9
Rep:
?
#7
Report Thread starter 1 week ago
#7
(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/...ractice/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/...ractice/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!
0
reply
DFranklin
Badges: 18
Rep:
?
#8
Report 1 week ago
#8
(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).
1
reply
jameshyland29
Badges: 9
Rep:
?
#9
Report Thread starter 1 week ago
#9
Ah yes that's it. Thank you once again!
0
reply
DFranklin
Badges: 18
Rep:
?
#10
Report 1 week ago
#10
(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).
0
reply
jameshyland29
Badges: 9
Rep:
?
#11
Report Thread starter 1 week ago
#11
(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?
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of Derby
    Postgraduate and Professional Open Evening - Derby Campus Postgraduate
    Tue, 22 Jan '19
  • University of the West of England, Bristol
    Undergraduate Open Afternoon - Frenchay Campus Undergraduate
    Wed, 23 Jan '19
  • University of East London
    Postgraduate Open Evening Postgraduate
    Wed, 23 Jan '19

Brexit: Given the chance now, would you vote leave or remain?

Remain (1525)
79.26%
Leave (399)
20.74%

Watched Threads

View All
Latest
My Feed