Before you start, make sure you know: Quadratic equations (Math 8 (Pre-Algebra))
Emma and five friends are at a pizza party. Everyone high-fives everyone else exactly once. How many high-fives is that? Counting them one by one gets messy fast. By the end of this page you'll count them in one line, and you'll handle much harder "choose a group" problems too.
Combinations and the binomial coefficient
A combination is a selection where order does not matter: a committee, a hand of cards, the toppings on a pizza. Choosing Ava, then Ben, then Chloe gives the same group as choosing Chloe, then Ava, then Ben.
Why divide by $k!$? Count ordered lists first: there are $n(n-1)\cdots(n-k+1)$ of them. Every group of $k$ items shows up as $k!$ different lists (all its orderings), so each group has been counted $k!$ times. Dividing by $k!$ fixes that.
Card problems are choosing problems too. A standard US deck has 52 cards in 4 suits (hearts, diamonds, clubs, spades) of 13 cards each. A few problems here use a 40-card deck (sometimes called a "Spanish deck") with 4 suits of 10 cards each, and one of its suits is named "coins." Treat any suit exactly like hearts: it is just a group of 10 cards. Drawing cards "simultaneously" (or being dealt a hand) means order does not matter, so you use a combination.
Practice★☆☆Not started
To prepare a salad, you have $8$ different ingredients available (lettuce, tomato, carrot, onion, cucumber, tuna, corn, and olives). Calculate how many different salads…
To prepare a salad, you have $8$ different ingredients available (lettuce, tomato, carrot, onion, cucumber, tuna, corn, and olives). Calculate how many different salads of $4$ ingredients you can make.
An exam consists of $10$ questions. The teacher indicates that students must choose and answer only $6$ of them. Determine in how many different ways a student can…
An exam consists of $10$ questions. The teacher indicates that students must choose and answer only $6$ of them. Determine in how many different ways a student can select the questions to answer.
"Everyone plays everyone once" and "everyone shakes hands with everyone" are the same problem: count the pairs of people. A pair $\{A, B\}$ is the same as $\{B, A\}$, so order does not matter.
Back to the pizza party: 6 friends give $\binom{6}{2}=\dfrac{6\cdot 5}{2}=15$ high-fives. That is exactly the 15 lines in the figure.
Practice★☆☆Not started
$14$ players are taking part in a chess tournament. If each player must face everyone else exactly once, determine the total number of games that will be played in the…
$14$ players are taking part in a chess tournament. If each player must face everyone else exactly once, determine the total number of games that will be played in the tournament.
There are $12$ people in a business meeting. At the end, everyone says goodbye by shaking hands exactly once. Calculate how many handshakes take place in total.
There are $12$ people in a business meeting. At the end, everyone says goodbye by shaking hands exactly once. Calculate how many handshakes take place in total.
On a grid formed by $9$ points distributed in $3$ rows and $3$ columns, determine how many different triangles can be formed using these points as vertices. Keep in mind…
On a grid formed by $9$ points distributed in $3$ rows and $3$ columns, determine how many different triangles can be formed using these points as vertices. Keep in mind that three collinear points do not form a triangle.
When the unknown appears inside a binomial coefficient, expand the factorial formula, simplify, and solve. The result is often a linear or quadratic equation, so you may need to factor or use the quadratic formula.
When an equation has two coefficients, expand both, put them over a common denominator, and combine like terms before solving. Often a lot of cancellation happens.
Practice★★☆Not started
Solve the following equation to find the value of the natural number $n$: $C_{n, 2} = 45$
Solve the following equation to find the value of the natural number $n$:
Many selections have conditions like "2 juniors and 3 seniors" or "exactly 3 of a certain kind." Split the problem into independent blocks, count each block with a combination, and multiply.
When a problem says "exactly $k$ of a special kind," split everything into "special" and "other." Choose $k$ from the special group and the rest from the other group. In a lottery problem, for example, the "special" numbers are the winning ones. In a card problem, the "special" cards might be all the cards of one suit.
Practice★★☆Not started
A company needs to form a project team consisting of $3$ engineers and $2$ economists. If there are $8$ engineers and $5$ economists available on the staff, calculate…
A company needs to form a project team consisting of $3$ engineers and $2$ economists. If there are $8$ engineers and $5$ economists available on the staff, calculate how many different teams can be formed.
$5$ cards are drawn simultaneously from a $40$-card Spanish deck (divided into $4$ suits of $10$ cards each). Determine in how many of the possible results there are…
$5$ cards are drawn simultaneously from a $40$-card Spanish deck (divided into $4$ suits of $10$ cards each). Determine in how many of the possible results there are exactly $3$ cards of the coins suit.
A lottery game consists of choosing $6$ numbers from a total of $49$. If the winning combination of $6$ numbers is already known, calculate how many different possible…
A lottery game consists of choosing $6$ numbers from a total of $49$. If the winning combination of $6$ numbers is already known, calculate how many different possible bets would obtain exactly $4$ correct numbers.
Two more kinds of conditions show up all the time.
Required members. If some items must be chosen, they are already in the group. Choose the rest from the remaining items.
"At least." You have two strategies.
Add the cases: "at least 3" means exactly 3, exactly 4, and so on. Add those counts.
Complement: "at least 1" means everything minus "none." Count all the groups, then subtract the groups that fail.
Practice★★☆Not started
On a test with $12$ questions, you must answer a total of $8$. However, the first $3$ questions are required. Determine the number of different ways you can complete…
On a test with $12$ questions, you must answer a total of $8$. However, the first $3$ questions are required. Determine the number of different ways you can complete your selection of questions.
A hospital must form a night shift team of $5$ people, selected from a group of $7$ doctors and $6$ nurses. Calculate how many different teams can be formed if…
A hospital must form a night shift team of $5$ people, selected from a group of $7$ doctors and $6$ nurses. Calculate how many different teams can be formed if regulations require the team to contain at least $3$ doctors.
An urn contains $6$ red balls, $5$ blue balls, and $4$ green balls. $4$ balls are drawn simultaneously. Calculate how many different outcomes contain exactly $2$ red…
An urn contains $6$ red balls, $5$ blue balls, and $4$ green balls. $4$ balls are drawn simultaneously. Calculate how many different outcomes contain exactly $2$ red balls and at least $1$ blue ball.
Combinations also count routes. Suppose a robot (or you, walking city blocks) must go from $A$ to $B$ moving only right or up. If the trip needs $m$ steps right and $p$ steps up, every route is a sequence of $m+p$ steps. A route is determined once you decide which of those steps go right.
Practice★★☆Not started
A robot moves along a grid from point $A$ to point $B$. It can only move to the right or upward, advancing one intersection at each step. Calculate the number of…
A robot moves along a grid from point $A$ to point $B$. It can only move to the right or upward, advancing one intersection at each step. Calculate the number of different paths it can follow.
A robot moves along a grid from node $A$ to node $B$, moving only to the right and upward. It must pass through node $C$ to pick up a package. Determine how many valid…
A robot moves along a grid from node $A$ to node $B$, moving only to the right and upward. It must pass through node $C$ to pick up a package. Determine how many valid routes exist.
What if you may pick the same item more than once? At a frozen yogurt shop you can order 3 scoops from 4 flavors, and "two vanilla and one mint" is allowed. Order still does not matter, but now repeats are possible.
The same formula counts ways to give identical items to different people. For each item you decide who gets it, and since the items are identical, only the totals matter. The people play the role of the "types."
Dominoes: unordered pairs with repeats
A domino tile has two halves, each showing a value. The tile $[2|5]$ is the same tile as $[5|2]$, so order does not matter. But both halves may show the same value (a "double" like $[3|3]$), so repeats are allowed. A set of dominoes is therefore a count of unordered pairs with repeats: $k=2$, and $n$ is the number of different values on a half.
To count the non-doubles, notice that they are the pairs with two different values. That is an ordinary combination, $\binom{n}{2}$. You can also get it by subtracting: total tiles minus the $n$ doubles.
Practice★★☆Not started
A bakery sells $6$ different types of cakes. Determine in how many different ways $4$ cakes can be bought, keeping in mind that several of the same type can be chosen.
A bakery sells $6$ different types of cakes. Determine in how many different ways $4$ cakes can be bought, keeping in mind that several of the same type can be chosen.
You have $8$ identical tickets for a concert and you want to divide them among your $4$ best friends. Calculate how many ways you can distribute them, knowing that a…
You have $8$ identical tickets for a concert and you want to divide them among your $4$ best friends. Calculate how many ways you can distribute them, knowing that a friend can receive several tickets or even none.
The traditional game of dominoes goes up to double-six (the values range from $0$ to $6$). A manufacturer decides to create a "super dominoes" set that goes up to…
The traditional game of dominoes goes up to double-six (the values range from $0$ to $6$). A manufacturer decides to create a "super dominoes" set that goes up to double-nine (the values range from $0$ to $9$). Calculate how many total tiles this new set will have and how many of them will not be doubles.
What if each type must appear at least once? Do it in two steps. First reserve one item of each type, so the requirement is satisfied. Then distribute what is left with no restrictions.
Practice★★★Not started
An ice cream parlor offers $5$ different flavors. You want to buy $8$ tubs of ice cream for a party, but you want to make sure you get at least one tub of each of the…
An ice cream parlor offers $5$ different flavors. You want to buy $8$ tubs of ice cream for a party, but you want to make sure you get at least one tub of each of the $5$ flavors. Calculate how many different ways you can place your order.