Permutation And Combination - APTITUDE Learning

Permutation and Combination: Formulas and Easy Solved Examples

A permutation is an arrangement in which order matters. A combination is a selection in which order does not matter. The central decision is simple: if the same objects change places, does that create a new result?

Suppose A, B and C are students. Choosing A and B for a two-person team gives the same team as choosing B and A, so this is a combination. Making A captain and B vice-captain is different from making B captain and A vice-captain, so this is a permutation.

This article begins with basic counting and factorials. It then builds through permutations, combinations, repeated objects, circular seating, conditions such as together or apart, digit restrictions, committee selection and the distribution of identical objects.

1 / 6

Counting foundations, factorials, permutations and combinations

Basics: Count Choices One Step at a Time

Before learning formulas, understand the multiplication principle. If one task has $a$ choices and a second task has $b$ choices, and both tasks must happen, the total number of outcomes is:

a \times b

Example: A student must choose one mathematics elective from 6 options and one science elective from 4 options. How many choices are possible?

We have two separate lists. The first list has 6 mathematics subjects. The second list has 4 science subjects. The student must take one subject from each list.

Start with one mathematics subject. That one subject can be paired with science choice 1, science choice 2, science choice 3 or science choice 4. So one mathematics subject makes 4 pairs. The same is true for each of the other 5 mathematics subjects.

We could add $4 + 4 + 4 + 4 + 4 + 4$ . Multiplication is the shorter way to write this repeated addition. Therefore:

6 \times 4 = 24

There are 24 possible pairs of electives. Each final answer contains one mathematics subject and one science subject. That is why we multiply the two numbers of choices.

Position-filling method

Many counting problems can be seen as empty positions. Write the number of choices for each position, then multiply.

Example: A four-digit PIN uses digits 0 to 9, and repetition is allowed. How many PINs are possible?

A PIN has four empty places, which we can picture as _ _ _ _. The available digits are 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. This gives 10 choices for the first empty place.

A PIN is a code, so 0 is allowed at the beginning. Repetition is also allowed. This means that after using a digit, we do not remove it. For example, after putting 7 in the first place, all 10 digits, including 7, can still go in the second place.

Therefore, each of the four places has 10 choices:

10 \times 10 \times 10 \times 10 = 10^{4} = 10, 000

The answer 10,000 means there are 10,000 different four-place PINs, starting at 0000 and ending at 9999. The position method is the base from which the permutation formula grows.

Factorials

The factorial of a positive integer $n$ , written $n!$ , is the product of all positive integers from $n$ down to 1.

n! = n (n - 1) (n - 2) \dots 2 \times 1

For example:

5! = 5 \times 4 \times 3 \times 2 \times 1 = 120

By definition, $0! = 1$ . This keeps permutation and combination formulas correct when $r = n$ or $r = 0$ .

Example: In how many ways can 6 different books be arranged on a shelf?

We have 6 books, and every book is different. We also have 6 places on the shelf. Changing the order creates a new shelf arrangement, so we must count every possible order.

For the first place, any of the 6 books may be used. After placing one book, it is no longer available for another place, so only 5 books remain. After placing the second book, 4 remain. The number of choices keeps falling until the final place has only 1 book left.

6 \times 5 \times 4 \times 3 \times 2 \times 1 = 6! = 720

Changing the order changes the shelf, so all 720 orders are different arrangements. The symbol $6!$ is simply a short name for the product of those six falling choice counts.

The Central Decision: Does Order Matter?

Ask this before selecting a formula:

If I use the same objects but change their order or roles, do I get a new result?

If yes, use a permutation or the position method. If no, use a combination.

Situation	Does order matter?	Method
Arrange books on a shelf	Yes	Permutation
Form a letter string	Yes	Permutation
Award gold, silver and bronze	Yes	Permutation
Select a committee	No	Combination
Choose pizza toppings	No	Combination
Count handshakes	No	Combination

Words such as “select” and “choose” are clues, but they are not enough on their own. Choosing a captain and vice-captain has different roles, so order matters even though the action begins with choosing people.

Permutation: Arranging Some Objects

If $r$ distinct objects are arranged from $n$ distinct available objects without repetition, the number of permutations is:

^{n} P_{r} = \frac{n!}{(n - r)!}

Here, $n$ is the number available and $r$ is the number of positions to fill.

Why the formula works

The first position has $n$ choices. The second has $n - 1$ , and this continues for $r$ positions.

^{n} P_{r} = n (n - 1) (n - 2) \dots (n - r + 1)

The factorial formula is a shorter way to write the same product.

Example: Seven students are available. In how many ways can 3 of them stand in an ordered row?

We have 7 different students but only 3 positions. We are not only choosing a group. We are placing one student first, one second and one third. A, B, C and B, A, C use the same students, but they make different rows. This tells us that order matters.

Fill the positions slowly. The first position can take any of the 7 students. Once that student is standing there, 6 students remain for the second position. After two students have been used, 5 remain for the third position.

7 \times 6 \times 5 = 210

Using the formula gives the same result:

^{7} P_{3} = \frac{7!}{(7 - 3)!} = \frac{7!}{4!} = 7 \times 6 \times 5 = 210

The same three students in a different order form a new row, so permutation is correct. The final answer 210 counts complete three-position rows, not only groups of three students.

Different roles are ordered positions

Example: Choose a captain and vice-captain from 8 students.

There are 8 students and two jobs. The jobs are not equal. One student will be captain and another will be vice-captain. If A is captain and B is vice-captain, swapping their jobs gives a different result.

Choose the captain first. Any of the 8 students can take this job. That chosen student cannot also be vice-captain, so only 7 students remain for the second job. For each of the 8 captain choices, there are 7 vice-captain choices.

8 \times 7 =^{8} P_{2} = 56

A as captain with B as vice-captain differs from B as captain with A as vice-captain. The answer 56 counts pairs with named jobs, not ordinary two-person teams.

Combination: Selecting Without Order

If $r$ distinct objects are selected from $n$ distinct objects and order does not matter, the number of combinations is:

^{n} C_{r} = \frac{n!}{r! (n - r)!}

Why we divide by $r!$

The permutation $^{n} P_{r}$ counts every selected group in all $r!$ possible orders. A combination treats those orders as the same group, so we divide:

^{n} C_{r} = \frac{^{n} P_{r}}{r!}

Equivalently:

^{n} P_{r} =^{n} C_{r} \times r!

Example: Select 3 subjects from 8 available subjects.

We need only a group of 3 subjects. The subjects do not receive first, second and third places. A group containing Maths, Physics and Chemistry stays the same group if we write Physics, Chemistry and Maths.

If we first counted ordered choices, every group would appear $3! = 6$ times. For one chosen group ABC, those orders are ABC, ACB, BAC, BCA, CAB and CBA. We want to count that group only once, so the combination formula divides by $3!$ .

^{8} C_{3} = \frac{8!}{3! 5!}

Expand only enough to cancel $5!$ :

^{8} C_{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56

There are 56 possible groups of three subjects. Each group is counted once, no matter how its members are written.

Useful combination facts

^{n} C_{0} =^{n} C_{n} = 1

There is one way to choose nothing and one way to choose everything.

^{n} C_{r} =^{n} C_{n - r}

Choosing $r$ objects to include is the same as choosing the other $n - r$ objects to leave out. For example, $^{10} C_{8} =^{10} C_{2}$ , and the second form is quicker to calculate.

Common Pair-Counting Applications

Handshakes

One handshake is made by an unordered pair of people. A shaking hands with B is the same handshake as B shaking hands with A.

Example: Twelve people each shake hands with every other person once. Find the number of handshakes.

A handshake needs exactly 2 people. It has no first person and second person. When Ravi shakes hands with Meena, Meena shaking hands with Ravi is not another handshake. Therefore, each unordered pair of people creates one handshake.

We choose 2 people from 12 without giving them different roles:

^{12} C_{2} = \frac{12 \times 11}{2} = 66

The division by 2 removes the double count. The answer 66 means there are 66 different pairs of people, so there are 66 handshakes.

Diagonals of a polygon

A line joining any two vertices is either a side or a diagonal. A polygon with $n$ vertices has $^{n} C_{2}$ pairs of vertices and $n$ sides.

diagonals =^{n} C_{2} - n = \frac{n (n - 3)}{2}

Example: Find the number of diagonals in a hexagon.

A hexagon has 6 corner points, also called vertices. Any two corners can be joined by a line. Choosing two corners from six gives $^{6} C_{2} = 15$ lines in total.

However, not every one of those lines is a diagonal. Six pairs of neighbouring corners make the 6 outer sides of the hexagon. A diagonal must join corners that are not next to each other. Therefore, remove those 6 sides from the 15 lines.

15 - 6 = 9

Therefore, a hexagon has 9 diagonals. We use a combination because joining corner A to corner D is the same line as joining D to A.

Repetition Allowed and Repetition Not Allowed

The phrase “repetition allowed” tells you that an item remains available after use. If there are $n$ choices for each of $r$ ordered positions, the count is:

n^{r}

If repetition is not allowed, the choices fall after each position:

n (n - 1) (n - 2) \dots (n - r + 1) =^{n} P_{r}

Example: Form 3-letter strings from 7 different letters without repetition.

We have 7 available letters and three ordered spaces: _ _ _. A string changes when its letters change places, so order matters. The words “without repetition” mean a letter must be removed from the available choices after it is used.

The first space has 7 choices. After one letter is used, the second space has 6 choices. After another letter is used, the last space has 5 choices.

7 \times 6 \times 5 =^{7} P_{3} = 210

The answer 210 counts different three-letter strings. If repetition had been allowed, no letter would be removed, every position would have 7 choices, and the answer would be $7^{3} = 343$ .

Numbers, Codes and the Special Role of Zero

A code can usually begin with 0. A number cannot begin with 0 because that leading zero does not add a digit. This small difference changes many answers.

A lower-limit restriction

Example: Use digits 0 to 7 without repetition to form four-digit numbers greater than 3000.

The available digits are $0,1,2,3,4,5,6,7$ . A four-digit number has a thousands place, hundreds place, tens place and units place. The thousands place controls whether the number is greater than 3000.

Putting 0 first would not make a four-digit number. Putting 1 or 2 first would make a number smaller than 3000. The first digit can therefore be only 3, 4, 5, 6 or 7. This gives 5 choices.

After the first digit is chosen, one of the 8 digits has been used. Repetition is not allowed, so 7 choices remain for the second place. After that, 6 remain for the third place and 5 for the final place.

5 \times 7 \times 6 \times 5 = 1050

The answer 1050 counts four-digit numbers greater than 3000 with no repeated digit. Zero is allowed in the last three positions. It is only blocked from the first position.

Even numbers with no repetition

Example: Form five-digit even numbers from $0,1,2,3,4,5,6$ without repetition.

We need to obey three facts at the same time. The number must have five digits, so its first digit cannot be 0. It must be even, so its last digit must be 0, 2, 4 or 6. No digit may repeat.

Zero affects the first and last places in different ways. If zero is already used at the end, it cannot cause trouble at the beginning. If a non-zero even digit is used at the end, zero is still available but cannot be placed first. Since these situations have different choice counts, we split them into two cases.

Case 1: The last digit is 0. Fix 0 in the units place. The first digit can now be any of 1 to 6, so it has 6 choices. After the first and last digits are fixed, 5 digits remain for the first middle place, then 4 and then 3.

6 \times 5 \times 4 \times 3 = 360

Case 2: The last digit is 2, 4 or 6. There are 3 choices for the last digit. Once one is used, 6 digits remain, but one of them is 0. The first digit can use only the 5 non-zero choices. After fixing both ends, 5, 4 and 3 choices remain for the middle positions.

3 \times 5 \times 5 \times 4 \times 3 = 900

Add the separate cases:

360 + 900 = 1260

The two cases cannot overlap because a number cannot end in both 0 and a non-zero digit. We add them to get 1260. Case splitting is needed because choosing 0 for the final position changes the number of choices at the first position.

Arrangements with Repeated Objects

When some objects are identical, swapping identical copies does not create a new arrangement. If there are $n$ total objects, with identical groups of sizes $p, q, r$ and so on, then:

distinct arrangements = \frac{n!}{p! q! r! \dots}

We divide because the basic $n!$ count treats identical copies as if they were different.

Example: How many distinct arrangements can be made from BANANA?

BANANA has 6 letter positions. If all six letters had their own identity, we would begin with $6! = 720$ orders. But the three A's look exactly the same. Swapping only those A's does not make a new visible word. The three A's can swap among themselves in $3! = 6$ ways that we must not count separately.

The two N's also look the same. They can swap in $2! = 2$ invisible ways. We therefore divide the large count by both repeated groups.

\frac{6!}{3! 2!} = \frac{720}{6 \times 2} = 60

There are 60 visible arrangements. Every visible arrangement had been counted $3! \times 2! = 12$ times inside the original $6!$ count, so division removes those extra copies.

Fixed positions with repeated letters

Example: How many arrangements of SUCCESS begin with S and end with C?

SUCCESS has seven letters: S, U, C, C, E, S, S. The first and last places are already fixed. Put one S in the first place and one C in the last place.

Now cross out the copies that were used. The letters left for the five middle spaces are S, S, U, C and E. Among these remaining letters, only S repeats, and it repeats twice.

Only S repeats in the middle, so:

\frac{5!}{2!} = 60

The answer 60 counts only arrangements that begin with S and end with C. Always remove the fixed letters before counting what remains. Do not use the old repetition counts after some copies have already been fixed.

Circular Arrangements

In a row, there is a fixed first place. Around a round table, rotating everyone together does not change who sits next to whom. Fix one person to remove these repeated rotations.

For $n$ distinct people around a round table:

(n - 1)!

Example: In how many rotationally different ways can 5 people sit around a round table?

If we used $5!$ , we would count the same seating five times. For example, everyone moving one seat to the right changes the seat numbers, but nobody gets a new left or right neighbour.

To remove this repeated rotation, choose one person and keep that person in one fixed seat. We are not reducing the real choices. We are only choosing one fixed viewing point. The other 4 people may now be arranged around that person in $4!$ ways.

(5 - 1)! = 4! = 24

The answer 24 counts neighbour orders around the table. This formula treats rotations as the same. It treats mirror images as different unless the arrangement is a necklace or reflections are explicitly identical.

When Objects Must Stay Together: The Block Method

If some objects must remain next to one another, tie them mentally into one block. First arrange the block with the other objects, then arrange the members inside the block.

Example: Arrange the letters of MANGO so that both vowels stay together.

The letters are M, A, N, G and O. The vowels are A and O. The condition says they must be next to each other, so imagine putting a band around them. The band makes them move as one packet while we arrange the outside objects.

The outside objects are the vowel packet, M, N and G. That is 4 objects, not 5. They can be placed in $4!$ orders.

4! = 24

The packet itself is not fixed inside. It may read AO or OA, giving $2! = 2$ inside orders.

4! \times 2! = 24 \times 2 = 48

The answer 48 counts full letter arrangements. We multiply because every outside order can use either inside order.

A larger block

Example: Eight different books are placed on a shelf. Three specified mathematics books must stay together.

There are 8 different books. Three named mathematics books must be side by side. Tie those three books into one block. The other 5 books stay separate.

For the outside shelf, we now have 1 block plus 5 other books, giving 6 objects. These can be arranged in $6!$ ways. However, the mathematics block can hold its three different books in $3!$ internal orders. Both the outside order and inside order matter.

6! \times 3! = 720 \times 6 = 4320

Therefore, 4320 shelf arrangements keep all three specified mathematics books together.

When Objects Must Stay Apart: Use the Complement

“Not together” is often easier to count as all arrangements minus together arrangements.

not together = total - together

Example: Seven people stand in a row. How many arrangements keep A and B apart?

The word “apart” means A and B must not stand next to each other. Counting every allowed gap directly is possible, but it is easy to miss a case. The opposite group is much easier: arrangements where A and B are together.

First count every row without using the restriction. All 7 different people can be arranged in:

7! = 5040

Next count the unwanted rows. Tie A and B into one block. This block plus the other 5 people gives 6 outside objects. They have $6!$ orders. Inside the block, A and B may be AB or BA, so multiply by 2.

6! \times 2 = 1440

Every row is either a together row or an apart row. No row can be in both groups. Therefore, subtract the unwanted together rows from all rows:

5040 - 1440 = 3600

Therefore, 3600 complete rows keep A and B apart.

Together and apart in a circle

The block method still works around a circle, but use the circular formula for the outside objects.

Example: Seven people sit around a round table, with A and B adjacent.

“Adjacent” means sitting next to each other. Tie A and B into one block. The block plus the other 5 people gives 6 objects around the circle.

Six circular objects have $(6 - 1)! = 5!$ orders because rotations are the same. A and B can switch places inside their block, so each outside seating has 2 inside orders.

(6 - 1)! \times 2! = 5! \times 2 = 240

The answer 240 counts rotationally different seatings with A and B together. For seatings where A and B are not adjacent, subtract 240 from the total $(7 - 1)! = 6! = 720$ circular arrangements, giving 480.

Relative Order Without Adjacency

“A appears before B” does not mean A must stand immediately before B. They may have other people between them.

Example: Six different people stand in a row. Find the arrangements in which A appears before B.

“A before B” only tells us their left-to-right order. It does not say that they must touch. A may be many places before B.

Without restrictions, the six people have $6! = 720$ rows. Every row belongs to one of two groups: A comes before B, or B comes before A. The groups are equal in size. To see why, take any row from the first group and swap only A and B. This makes exactly one matching row in the second group.

\frac{6!}{2} = \frac{720}{2} = 360

The answer 360 counts all rows where A is somewhere to the left of B. This half rule works because the two relative orders are equally possible.

Selecting Teams and Committees with Conditions

Committee members have equal roles, so use combinations. Translate words such as exactly, at least and cannot both be selected before calculating.

Exactly a given composition

Example: Form a five-person team from 7 boys and 6 girls with exactly 3 girls.

The final team has 5 places, but team members do not have different jobs, so order does not matter. The word “exactly” means only 3 girls are allowed, not 2 and not 4.

After choosing 3 girls, the five-person team still needs 2 people. Those 2 people must be boys. Choose 3 of the 6 girls and, for each such choice, choose 2 of the 7 boys.

^{6} C_{3} \times^{7} C_{2} = 20 \times 21 = 420

The answer 420 counts complete five-person teams. We multiply because each girl selection must be paired with a boy selection.

At least a given number

Example: Form a four-person committee from 6 men and 5 women with at least 2 women.

The committee has 4 people. “At least 2 women” means 2 or more women. With only four committee places, the allowed counts are exactly 2 women, exactly 3 women and exactly 4 women.

For exactly 2 women, the other 2 members must be men. For exactly 3 women, the other 1 must be a man. For exactly 4 women, no man is needed. These groups cannot overlap because one committee cannot have two different numbers of women, so we add their counts.

^{5} C_{2}^{6} C_{2} +^{5} C_{3}^{6} C_{1} +^{5} C_{4}^{6} C_{0}

= 10 (15) + 10 (6) + 5 (1) = 215

The three cases give 150, 60 and 5 committees. Adding them gives 215 valid committees. Writing every allowed makeup first prevents us from missing the all-women case.

At least one specified person

Example: Choose a five-person group from 12 people. At least one of 3 specified seniors must be present.

The group has 5 people, and at least one of 3 named seniors must be included. Allowed groups may contain 1, 2 or 3 seniors. Counting those cases separately would work, but the only unwanted case is much simpler: no senior at all.

There are $^{12} C_{5}$ total five-person groups. If a group has no senior, all five members must come from the other $12 - 3 = 9$ people. There are $^{9} C_{5}$ such unwanted groups.

^{12} C_{5} -^{9} C_{5} = 792 - 126 = 666

The answer 666 counts groups containing one or more of the specified seniors. This complement is shorter than adding the cases with exactly 1, 2 and 3 seniors.

Two people cannot both be selected

Example: Select a four-person group from 10 people, but two specified people cannot both be selected.

The condition does not ban both people completely. The first may appear alone, the second may appear alone, and neither may appear. Only a group containing the two of them together is invalid.

Begin with all $^{10} C_{4}$ four-person groups. For an invalid group, put both specified people into the group first. Two of the four places are now filled. Choose the remaining 2 members from the other 8 people, giving $^{8} C_{2}$ invalid groups.

^{10} C_{4} -^{8} C_{2} = 210 - 28 = 182

The answer 182 counts groups that do not contain the forbidden pair together. “Cannot both be selected” does not mean that neither may be selected.

Select First, Then Assign a Role

Some counting situations use combination and permutation in separate steps.

Example: From 8 people, choose a five-person committee and then choose its chairperson.

This arrangement has two stages. First make a group of five equal committee members. Then give one of those selected members the special chairperson job.

In the first stage, order does not matter, so select the committee using a combination:

^{8} C_{5} = 56

In the second stage, look only inside the chosen committee. It has 5 members, and any one of them can be chairperson. Therefore, every one of the 56 committees creates 5 final outcomes.

^{8} C_{5} \times 5 = 56 \times 5 = 280

The answer 280 counts a committee together with its named chairperson. Do not use only $^{8} C_{5}$ , because that ignores the chair. Do not arrange all five members either, because only one role is special.

Required Items in an Ordered String

If a string must contain a particular item, it can be useful to select the other items first and then arrange the complete set.

Example: Form four-letter strings from the six different letters in ORANGE. Every string must contain O, and no letter repeats.

ORANGE has 6 different letters: O, R, A, N, G and E. Each answer must be a four-letter string, and O must appear in it. Since O is already fixed as a member of the string, we need to find only three more members.

Choose those 3 letters from R, A, N, G and E. At this stage, order does not matter because we are only deciding which letters will be used.

^{5} C_{3} = 10

Now we have a set of 4 different letters: O and the three we selected. A string is ordered, so arrange these 4 letters in all $4!$ ways.

^{5} C_{3} \times 4! = 10 \times 24 = 240

The answer 240 counts full four-letter strings that contain O exactly once. This is a “select, then arrange” problem. The relation $^{n} P_{r} =^{n} C_{r} r!$ explains why these two stages fit together.

Counting Subsets

For each element of a set, there are two choices: include it or leave it out. Therefore, a set with $n$ elements has:

2^{n} subsets

This count includes the empty subset, which selects nothing.

Example: How many non-empty subsets does a five-element set have?

Take each of the five elements one at a time. For every element, we make one of two choices: put it in the subset or leave it out. The five choices happen independently, so the total number of choice patterns is:

2 \times 2 \times 2 \times 2 \times 2 = 2^{5} = 32

One pattern leaves out every element. That pattern creates the empty subset. We need non-empty subsets, so remove this one unwanted subset.

2^{5} - 1 = 31

Therefore, the set has 31 subsets containing at least one element.

Distributing Identical Objects: Stars and Bars

Distribution looks different from arrangement, but both use counting. The objects are identical, the recipients or boxes are distinct, and dividers separate the shares.

For non-negative integer solutions of:

x_{1} + x_{2} + \dots + x_{k} = n

the number of solutions is:

^{n + k - 1} C_{k - 1}

This is called the stars-and-bars method. The $n$ identical units are stars and the $k - 1$ dividers are bars.

Positive shares

If every variable must be positive, give one unit to each variable first. For:

x_{1} + x_{2} + \dots + x_{k} = n, x_{i} ge 1

the number of positive integer solutions is:

^{n - 1} C_{k - 1}

Example: Find the positive integer solutions of $x + y + z = 10$ .

We are not looking for just one answer. We are counting all ordered triples $(x, y, z)$ of positive whole numbers whose sum is 10. Positive means each variable must receive at least 1. Zero is not allowed.

Imagine 10 identical sweets and three labelled children called x, y and z. Give one sweet to each child first. This uses 3 sweets and guarantees that every value will be positive. There are $10 - 3 = 7$ sweets left.

Those 7 extra sweets may now be shared in any way, including giving no extra sweet to one child. The first sweet already given keeps that child's final value positive.

Represent the 7 extra units by seven stars. To split one row into three labelled parts, place two bars. Stars before the first bar go to x, stars between the bars go to y, and stars after the second bar go to z.

There are 7 identical stars and 2 identical bars, making 9 symbol positions. Choosing which 2 positions contain the bars completely decides one sharing pattern:

^{9} C_{2} = 36

For example, **|***|** gives 2 extra units to x, 3 to y and 2 to z. Adding the first unit gives $(x, y, z) = (3,4,3)$ , and $3 + 4 + 3 = 10$ .

The answer 36 counts all positive integer triples, including different orders. For example, $(3,4,3)$ and $(4,3,3)$ are different because x and y have changed values.

Example: Distribute 10 identical balls among 3 distinct boxes so every box receives at least one ball.

The balls are identical, so exchanging two balls does not make a new result. The boxes are distinct, which means box A, box B and box C have their own names. A distribution of $(3,4,3)$ differs from $(4,3,3)$ because different boxes receive the larger share.

Every box must receive at least one ball. Put one ball into each box first. This uses 3 of the 10 balls. Now 7 balls remain, and they can be placed freely because the “at least one” rule has already been satisfied.

Seven identical balls and two identical dividers make nine symbols. Choosing the two divider positions gives:

^{7 + 3 - 1} C_{3 - 1} =^{9} C_{2} = 36

Therefore, there are 36 valid distributions. The balls must be identical and the boxes must be distinct for this exact formula to apply.

A Reliable Counting Method

Use this short process:

Name the objects and positions. Are you arranging people, choosing a group, filling digits or sharing identical items?
Test order. Would swapping the same chosen items make a new result?
Check repetition. Does an item remain available after it is used?
Mark restrictions. Look for zero, even, exactly, at least, together, apart, before or fixed positions.
Choose a counting shape. Use positions, cases, a block, a complement, combinations or stars and bars.
Multiply within one case. Use multiplication when choices must happen together.
Add separate cases. Use addition when one case or another may happen and the cases do not overlap.
Check for double counting. Ask whether the same final outcome was counted in more than one way.

Common Mistakes

Choosing a formula from one keyword

“Choose a captain and vice-captain” is a permutation because the roles differ. Decide by meaning, not only by the word choose.

Forgetting internal block arrangements

After treating A and B as one block, multiply by $2!$ for AB and BA. A block of three different objects contributes $3!$ internal arrangements.

Letting a number begin with zero

Zero may begin a PIN or code, but it cannot begin a fixed-length number.

Using $n!$ for repeated letters

Divide by the factorial of every identical group. For BANANA, divide by both $3!$ and $2!$ .

Confusing “before” with “immediately before”

A before B allows gaps. Immediately before means AB must be treated as an ordered block.

Subtracting the wrong invalid case

If two people cannot both be chosen, remove only groups containing both. Groups containing just one of them are valid.

Mixing identical and distinct objects

Stars and bars counts distributions of identical objects into distinct boxes. Different balls create a different counting problem.

Formulas and Cheat Sheet

Pattern	Formula or method
Multiplication principle	Multiply choices for steps that must all happen
Factorial	$n! = n (n - 1) \dots 1$ , with $0! = 1$
Permutation without repetition	$^{n} P_{r} = dfrac n! (n - r)!$
Combination	$^{n} C_{r} = dfrac n! r! (n - r)!$
Relation	$^{n} P_{r} =^{n} C_{r}, r!$
Ordered positions with repetition	$n^{r}$
Arrange all $n$ distinct objects	$n!$
Repeated objects	$dfrac n! p! q! \dots$
Round-table arrangement	$(n - 1)!$
Required adjacent group	Treat it as one block, then count internal orders
Required separation	Total arrangements minus together arrangements
Subsets of an $n$ -element set	$2^{n}$
Non-empty subsets	$2^{n} - 1$
Diagonals in an $n$ -gon	$dfrac n (n - 3) 2$
Non-negative solutions in $k$ variables	$^{n + k - 1} C_{k - 1}$
Positive solutions in $k$ variables	$^{n - 1} C_{k - 1}$

The most important check comes before every formula: decide whether changing the order changes the result. Then handle repetition and restrictions. Once those choices are clear, the count usually becomes a small set of position counts, combinations, cases, blocks or complements.

Safe Shortcuts

Multiply the choices at successive steps when one choice is followed by another. Add counts only for separate cases that cannot happen together.
Use $^{n} P_{r} =^{n} C_{r}, r!$ when a problem first selects $r$ objects and then arranges all selected objects.
For “at least one” or “none” conditions, count the unrestricted total and subtract the opposite case when that opposite is shorter.
For repeated objects, divide $n!$ by the factorial of each repetition count. This is safe only when the repeated objects are truly identical.
For a circular arrangement with rotations treated as the same, use $(n - 1)!$ . If reflections are also treated as the same, check whether another division by 2 is required.
When objects must stay together, make them one block first, arrange the blocks, and then arrange inside the block. Multiply those two counts.
When a number cannot begin with zero, handle the first digit separately before counting the remaining positions.

These shortcuts are safe only after deciding whether order matters, repetition is allowed and any positions have special restrictions. They shorten counting, not the decision about what is being counted.

Frequently Asked Questions

What is the difference between permutation and combination?

A permutation counts arrangements where order matters. A combination counts selections where order does not matter. ABC and BAC are different permutations but represent the same combination of A, B and C.

What are the formulas for permutation and combination?

For $0 le r le n$ :

^{n} P_{r} = \frac{n!}{(n - r)!},^{n} C_{r} = \frac{n!}{r! (n - r)!}

How do I know whether order matters?

Swap two chosen items. If the result changes, order matters. Medal winners, letter strings and assigned roles are ordered. Teams, committees and card hands are usually unordered.

Why is permutation larger than combination?

A permutation counts every order of each selected group. Each group of $r$ distinct objects has $r!$ orders, so $^{n} P_{r} =^{n} C_{r} \times r!$ .

What does repetition allowed mean?

It means an object may be used again after it fills a position. With $n$ choices for each of $r$ ordered positions, there are $n^{r}$ results.

How are repeated letters arranged?

Begin with the factorial of the total number of letters. Divide by the factorial of the count of each repeated letter:

\frac{n!}{p! q! \dots}

What is the circular permutation formula?

For $n$ distinct people around a round table, rotations are the same, so there are $(n - 1)!$ arrangements. This formula assumes reflections are still different.

When should I use the block method?

Use it when people or objects must be adjacent. Treat the required group as one outside object, arrange all outside objects, then multiply by the possible orders inside the block.

How do I count arrangements where two objects are not together?

Usually count all arrangements and subtract the arrangements where they are together. The together part can be found with the block method.

What is the stars-and-bars formula?

For $x_{1} + \dots + x_{k} = n$ with every variable at least 0, the number of integer solutions is $^{n + k - 1} C_{k - 1}$ . If every variable must be at least 1, it is $^{n - 1} C_{k - 1}$ .

What does “at least” mean in committee questions?

At least $k$ means $k$ or more. List every allowed group size, or use total minus the unwanted cases when the complement is shorter.