A combination is a way of choosing elements from a set in which order does not matter.

Consider the following example: Lisa has 1212 different ornaments and she wants to give 55 ornaments to her mom as a birthday gift (the order of the gifts does not matter). How many ways can she do this?

We can think of Lisa giving her mom a first ornament, a second ornament, a third ornament, etc. This can be done in 12!7! \frac{12!}{7!} ways. However, Lisa’s mom is receiving all five ornaments at once, so the order Lisa decides on the ornaments does not matter. There are 5! 5! reorderings of the chosen ornaments, implying the total number of ways for Lisa to give her mom an unordered set of 55 ornaments is 12!7!5! \frac{12!}{7!5!} .

Notice that in the answer, the factorials in the denominator sum to the value in the numerator. This is not a coincidence. In general, the number of ways to pick k k unordered elements from an n n element set is n!k!(nk)! \frac{n!}{k!(n-k)!} . This is a binomial coefficient, denoted (nk) n \choose k .

Worked Examples

1. How many ways are there to arrange 3 chocolate chip cookies and 10 raspberry cheesecake cookies into a row of 13 cookies?

Solution: There are 13×12×11 13 \times 12 \times 11 ways to chose 3 distinct chocolate chip cookies. However, the order of these chocolate chip cookies doesn't matter. Hence, we divide by 3×2×1 3 \times 2 \times 1 , to obtain 13×12×113×2×1=286 \frac {13 \times 12 \times 11}{3 \times 2 \times 1} = 286 ways.


2. How many ordered non-negative integer solutions (a,b,c,d) (a, b, c, d) are there to the equation a+b+c+d=10 a + b + c + d = 10 ?

Solution: To solve this problem, we use a technique called "Stars and Bars", which was popularized by William Feller. We create a bijection between the solutions to a+b+c+d=10 a + b + c + d = 10 and sequences of 13 digits, consisting of ten 1's, and three 0's. Given a set of four integers whose sum is 10, we create a sequence that starts with a a 1's, then has a 0, then has b b 1's, then has a 0, then has c c 1's, then has a 0, then has d d 1's. Conversely, given such a sequence, we can set a a to be equal to the length of the initial string of 1's (before the first 0), set b b equal to the length of the next string of 1's (between the first and second 0), set c c equal to the length of the third string of 1's (between the second and third 0) and set d d equal to the length of the fourth string of 1's. It is clear that such a procedure returns the starting set, hence we have a bijection .Now, it remains to count the number of such sequences. We pick 3 positions for the 1's and the remaining positions are 0's. Hence, there are (133)=286 {13 \choose 3}= 286 such sequences.


3. Both of the previous answers are 286. Is this a happy coincidence?

In the second question, we gave a bijection between solutions to a+b+c+d=10 a+b+c+d=10 and sequences of length 13 with 10 0's and 3 1's. For the first question, we can also create a bijection between the arrangement of cookies and the sequences of length 13 with 10 0's and 3 1's, by letting each raspberry cheesecake cookie be a 1, and each chocolate chip cookie be a 0. Therefore, we have a bijection between solutions to the first and second questions, which explains why they have the same answer!

Note by Arron Kau
7 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...