Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Post History

#1: Initial revision by user avatar r~~‭ · 2020-12-30T06:05:54Z (about 3 years ago)
You have 8 people, and you have to pick 3 of them to get identical gifts. Even though the gifts are identical, let's give them labels: A, B, and C. Let's also number the people 1 to 8.

The first step is to figure out how many ways there are to hand out gifts in order. You have 8 choices for gift A, then 7 choices for gift B because you don't want to give to the same person who got gift A, and likewise 6 choices for gift C.

And now we get to the part about redundancies. Let's say for a moment that you gave gift A to person 3, gift B to person 5, and gift C to person 2. Let's call that outcome (3, 5, 2).

From the first step, you know you can make a list of outcomes like the above that is $8\cdot 7 \cdot 6 = 336$ items long. And since that list is all of the ways to give gifts in order to three people, you know that if (3, 5, 2) is on that list, then so is every rearrangement of those three numbers—(5, 3, 2), (2, 5, 3), etc. Because the gifts are identical, you can treat rearrangements as redundant.

So you can imagine organizing your list into groups, where two outcomes belong to the same group if, like (5, 3, 2) and (3, 5, 2), they are rearrangements of each other. (No outcome can belong to more than one group, because rearranging an outcome doesn't change the set of numbers that are in that outcome.) The answer you seek is the number of *groups* in the list, because each group corresponds to a single not-redundant outcome when all you care about is who gets a gift, not who gets which gift.

Is every group the same size? Yes, because no outcome can use the same number twice (that would mean someone got two gifts), so the numbers must all be different. And there are always $n!$ ways to rearrange $n$ different numbers.

 So you have a list of 336 outcomes, organized into groups of size $3! = 6$. How do you determine how many groups there are in the list? Hopefully the answer is now clearer.