Permutations and Combinations

1Multiply for and, add for or

If one task can be done in m ways and an independent second task in n ways, doing both together can be done in m\times n ways. Mutually exclusive alternatives add: choose route A or route B and the total is m+n. The whole of permutations and combinations is this principle applied to ordered slots or to unordered groups.

Independence is the condition that costs marks. If choosing the first object changes how many choices remain for the second, you are already in the falling-factorial world of {}^nP_r, not a free m\times n product of fixed sizes.

Figure. A letter from \{A,B,C\} and then a digit from \{0,\ldots,9\} multiplies: 3\times10=30. Adding 3+10=13 would count an or of exclusive cases, not both tasks together.

How it works

1. Name the tasksSplit the counting into successive decisions, each with a clear number of options.
2. And versus orMultiply when every decision must be made; add only when the cases partition the total and cannot overlap.
3. Watch dependenceIf an earlier choice removes options later, write the product as n(n-1)(n-2)\cdots, not as a constant m times a constant n.

2Permutations count ordered arrangements

The number of ordered arrangements of r objects chosen from n distinct objects is {}^nP_r=\dfrac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1). Order matters: AB and BA are different permutations.

When some of the n objects are identical — say p of one kind, q of another — the distinct linear arrangements of all n are \dfrac{n!}{p!\,q!\,\cdots}. Dividing by each repeat's factorial removes the swaps that look the same.

Figure. Ordered fillings of 3 seats from 5 objects: first seat 5 choices, then 4, then 3. The falling product is 5\times4\times3=60, matching 5!/(5-3)!.

How it works

1. Fill seats in orderFirst place has n choices, second n-1, and so on down to n-r+1 for the r-th place.
2. Compact as a factorialThe falling product is \dfrac{n!}{(n-r)!}. Use this form when a calculator or a later cancellation wants factorials.
3. Divide out identical swapsIf p letters are the same, those p! internal swaps were never distinguishable — divide by p!, and likewise for every other repeated kind.

3Identical letters shrink the arrangement count

For a word whose letters are not all distinct, the distinct permutations of all letters are \dfrac{n!}{p!\,q!\,\cdots}, where n is the length and p,q,\ldots are the frequencies of the repeated letters. Skipping any one of those denominators overcounts by swapping identical letters that the eye cannot tell apart.

Figure. MISSISSIPPI has 11 letters with I four times, S four times and P twice. Distinct arrangements are 11!/(4!\,4!\,2!)=39916800/1152=34650.

How it works

1. Count every letterList the frequency of each distinct character; n is the sum of those frequencies.
2. Write n! in the numeratorThat would be the answer if every letter were distinct.
3. Divide by each repeatFor each letter that appears k times, divide by k!. Omit a factor and you have counted invisible swaps.

4Combinations ignore order

The number of unordered selections of r objects from n distinct objects is {}^nC_r=\dfrac{n!}{r!(n-r)!}. Order does not matter: the pair {A, B} is one combination, whether you picked A first or B first.

Two identities are used constantly: {}^nC_r={}^nC_{n-r} (choosing who is in is choosing who is out), and Pascal's rule {}^nC_r+{}^nC_{r-1}={}^{n+1}C_r (a selection of r from n+1 either contains a fixed element or it does not).

C(n,r)=P(n,r)/r! drops order; the quotient is the definition, not a diagram.

How it works

1. Decide order is irrelevantCommittees, teams and subsets use {}^nC_r. Ranked posts use {}^nP_r.
2. Use symmetryPrefer {}^nC_r or {}^nC_{n-r}, whichever has the smaller r — the values are equal.
3. Pascal when building larger nTo relate neighbouring rows of Pascal's triangle, split on whether a distinguished element is included.

5Multiply combinations across groups

When a selection must take a fixed number from each of several groups — exactly k women from one pool and r-k men from another — choose inside each group with a combination, then multiply. The groups are independent once the quota for each is fixed.

For 'at least one' conditions on selections from n distinct objects, the clean route is the complement: total non-empty selections equal 2^n-1, because each object is in or out and the all-out case is forbidden.

Figure. Fix the quotas, then multiply: {}^5C_2=10 ways to choose the women and {}^7C_2=21 ways to choose the men, so 10\times21=210 committees. Adding the two combination counts would pick one group or the other, not both.

How it works

1. Fix the quotaTranslate 'exactly two women' into {}^5C_2 for women and {}^7C_2 for the remaining seats among men, or whatever the pools are.
2. Multiply across groupsIndependent combination counts multiply. Do not add them — that would choose a women-committee or a men-committee, not both.
3. Prefer complement for 'at least'Compute total selections minus the forbidden all-excluded (or all-from-one-group) case, rather than summing many overlapping 'at least' cases.

6Circular arrangements fix one seat

Arranging n distinct objects in a circle gives (n-1)! distinct arrangements, not n!. Rotations of the same cyclic order are the same seating: fix one person's position and arrange the other n-1 in the remaining seats.

If reflections are identified — a necklace that can be flipped — divide by 2 as well, giving \dfrac{(n-1)!}{2} when n\ge3 and no extra symmetry intervenes.

How it works

1. Fix one objectPin one person (or bead) to remove the rotational copies.
2. Arrange the restThe remaining n-1 objects may be permuted in (n-1)! ways around the circle.
3. Flip only if askedDivide by 2 when the problem treats clockwise and anticlockwise as the same object (necklace, bracelet).

7Blocks, gaps, and identical distributions

Three standard restrictions reuse the same counting tools. To keep certain items together, tie them into a single block, arrange the blocks, then multiply by the internal arrangements of the block. For no-two-together constraints, arrange the unrestricted items first and place the restricted ones in the gaps between them (the gap method).

Distributing n identical objects into r distinct boxes with each box allowed zero or more is the stars-and-bars count {}^{n+r-1}C_{r-1}. That is a combination in disguise — the objects are identical, so only how many land in each box matters.

Glue items into a block (one super item) or place gaps between fixed items — the counting cases live in the steps.

How it works

1. Together → one blockGlue the items that must stay together into a super item, arrange the super item with the others, then multiply by the internal permutations of the glue.
2. Apart → gapsSeat the free items first; k free items in a line create k+1 gaps (including ends). Choose gaps for the restricted items so no two share a gap when the rule forbids adjacency.
3. Identical into distinct boxesWrite {}^{n+r-1}C_{r-1} when objects are identical, boxes are distinct, and empty boxes are allowed.