Counting problem

Steven G

Steven G

Elite Member
Joined
Dec 30, 2014
Messages
14,383
I need a hint for this one. The problem is innocently stated but I am having trouble with it.

Suppose n people attend a party and bring a gift for everyone else. All guests put their gift in a big pile and when they leave, they each randomly take n-1 gifts. In how many ways can this be done if no one is to get any of their gifts?
 
Last edited:
There are \(\displaystyle n(n-1)\) gifts.

There are \(\displaystyle n(n-1) - (n-1) = (n-1)^2\) gifts that aren't yours.

You have to choose \(\displaystyle (n-1)\) from these.

So there are \(\displaystyle (n-1)^2\) C \(\displaystyle (n-1)\) ways for you to choose gifts that aren't yours.

That's just for one person though. Hmmm...I see your problem. Nice question! Need more time.
 
Jomo said:
I need a hint for this one. The problem is innocently stated but I am having trouble with it.

Suppose n people attend a party and bring a gift for everyone else. All guests put their gift in a big pile and when they leave, they each randomly take n-1 gifts. In how many ways can this be done if no one is to get any of their gifts?
Click to expand...
This strikes me as the derangement problem taken to another level.

Where did this come from? Does the context suggest any techniques? What have you tried?
 
Dr.Peterson said:
This strikes me as the derangement problem taken to another level.

Where did this come from? Does the context suggest any techniques? What have you tried?
Click to expand...
A tutoring student of mine taking a combinatorics course asked me this one. I immediately knew that I was stumped.
I started to look at specific cases on my own time but ran out of time.
 
I asked the student if he was in a graduate level course and he said no.
 
I have neither the time nor the energy to attack this, but, if I did, I might work it out for n = 2, 3, 4, and 5, to seek a paatern.
 
JeffM said:
I have neither the time nor the energy to attack this, but, if I did, I might work it out for n = 2, 3, 4, and 5, to seek a pattern.
Click to expand...
I started to do that, and then realized that, unless I'm mistaken, this is not hard at all. (It's easy to be mistaken, though!) I was just expecting it to be hard, so I hadn't tried.

Since I can't get any of my own gifts, isn't it just as if I chose who gets each of mine? And the same for everyone else? There's a very simple formula.
 
Dr.Peterson said:
I started to do that, and then realized that, unless I'm mistaken, this is not hard at all. (It's easy to be mistaken, though!) I was just expecting it to be hard, so I hadn't tried.

Since I can't get any of my own gifts, isn't it just as if I chose who gets each of mine? And the same for everyone else? There's a very simple formula.
Click to expand...
I think it is more complicated. You've got to make sure that by the time the nth person gets what's left, that there are none of the gifts he brought left.
 
Harry_the_cat said:
I think it is more complicated. You've got to make sure that by the time the nth person gets what's left, that there are none of the gifts he brought left.
Click to expand...
That's how I was initially thinking; but that issue arises only if you think of it sequentially. All we care about is the number of possible distinct outcomes, not the process by which they are selected.

Ah! What I am missing is that mine could all go to the same person, for example; they don't have to go to distinct people. Then, how mine are distributed does change possibilities for others. So it is back to the complexity I originally envisioned, though I think looking only at the outcomes may still help.
 
Dr.Peterson said:
That's how I was initially thinking; but that issue arises only if you think of it sequentially. All we care about is the number of possible distinct outcomes, not the process by which they are selected.

Ah! What I am missing is that mine could all go to the same person, for example; they don't have to go to distinct people. Then, how mine are distributed does change possibilities for others. So it is back to the complexity I originally envisioned, though I think looking only at the outcomes may still help.
Click to expand...
Also, the gifts are put in a big pile. You don't get to choose who your presents go to.
 
Ok.
n=2 is obvious. There is only one way: A takes B's gift, B takes A's gift.

n=3. A brings gifts A1 and A2, B brings gifts B1 and B2, C brings gifts C1 and C2.
Say A picks gifts first. Choices are:
ABC
B1, B2C1, C2 (B has to take both C1&C2 so no C gifts are left)A1, A2
B1, C1A1, C2 or A2, C2 (must take C2)A2, B2 or A1, B2
B1, C2""
B2, C1""
B2, C2""
C1, C2A1, A2B1, B2

So for n=3, there are 1 + 4*2 +1 =10 ways the presents can be taken. (By " I mean similar pattern applies.)
Agree?
 
This student was just shooting these hard questions at me and I could do almost none of them. It was the strangest thing. Then later that same day I tutored another student in combinatorics and I easily did every problem. That session had to be my worst experience as a tutor. I'll post the other problems after this one settled.
 
Harry_the_cat said:
Also, the gifts are put in a big pile. You don't get to choose who your presents go to.
Click to expand...
You're missing my point. A question about how many ways something can happen can always be thought of in terms of choosing: How many ways could the gifts be distributed if it were done intentionally? The idea of randomness is ultimately irrelevant (particularly since this is not a probability question), and it isn't necessary for recipients to be choosing what they get rather than givers choosing or some outside actor doing so, as long as we get all possibilities. And a key to solving these is often to remodel the problem, looking at it from a different perspective, such as a different process for obtaining the same result.

I have no idea yet whether a focus on where each gift goes rather than what each person gets will help at all.
 
Jomo said:
I need a hint for this one. The problem is innocently stated but I am having trouble with it.

Suppose n people attend a party and bring a gift for everyone else. All guests put their gift in a big pile and when they leave, they each randomly take n-1 gifts. In how many ways can this be done if no one is to get any of their gifts?
Click to expand...
One approach is to do the counting without the restriction, then subtract the number of cases where one or more guests get their own gifts. Unfortunately, the second part appears at least as complex as the original problem.
 
Here's a way of visualising this problem, shown here for 3 people. (Hopefully this will give someone insight towards a better solution.)

From AFrom BFrom Cways
To A
0​
1​
1​
2
To B
1​
0​
1​
2
To C
1​
1​
0​
2
total 8


From AFrom BFrom Cways
To A
0​
0​
2​
1
To B
2​
0​
0​
1
To C
0​
2​
0​
1
total 1


From AFrom BFrom Cways
To A
0​
2​
0​
1
To B
0​
0​
2​
1
To C
2​
0​
0​
1
total 1

Grand total = 8+1+1 = 10 ways

The diagonal TL to BR in each matrix must contain zeros. Then, find all possible tables where rows and columns sum to 2. Then calculate the ways to distribute the gifts. NOTE: we have been assuming that the gifts from every person are all different.

I wrote some code to explore this for other n...

n=2 gives 1 table and 1 way
n=3 gives 3 tables and 10 ways
n=4 gives 138 tables and 13,833 ways
n=5 gives 68,290 tables and 3,993,445,276 ways
 
You must log in or register to reply here.
Top