Permutations, Combinations and Probability

Dice probability with conditions

Dice probability with conditions asks for the chance of an event when one or more dice are thrown and the outcome must satisfy a restriction, such as 'every die shows an even face', 'every die shows a letter from a given set', 'the sum is prime', 'the second value is a multiple of the first', or 'exactly one six appears'. Always begin by fixing the sample space. A fair die is unbiased, so each of its six faces has probability \frac{1}{6}. For two dice thrown together, the sample space consists of ordered pairs, and there are 6\times 6=36 equally likely outcomes. Even when the dice are described as identical, you must treat the first throw and the second throw as distinct, because the pair (2,5) and the pair (5,2) are different outcomes.

Throws of separate dice are independent, so when the condition must hold on every die, the joint probability is the product of the single-die probabilities: P(A \text{ and } B)=P(A)\,P(B). Expressions such as 'on each die', 'both dice', and 'each of the two rolls' signal this product rule. For a fair die, three even faces out of six give P(\text{even})=\frac{3}{6}=\frac{1}{2}, so the probability that both dice show even numbers is \frac{1}{2}\times\frac{1}{2}=\frac{1}{4}, which corresponds to 3\times 3=9 favourable pairs out of 36. A value such as \frac{1}{36} denotes a single ordered pair rather than the whole event, while \frac{1}{12} and \frac{1}{8} do not arise from this product at all.

When the condition is that each die shows a face from a given subset, count the allowed faces first. If three of the six faces are allowed, each die has probability \frac{1}{2} and the joint probability is \frac{1}{4}, whatever the labels on the faces are. Students often confuse this with 'at least one die' showing a face from the set. The latter is the complement of 'no die does', so it equals 1-\left(\frac{1}{2}\right)^2=\frac{3}{4}, and the two phrasings must not be mixed.

When the question fixes a specific value on a specific throw, the event is a single ordered pair. For 'a 1 on the first roll and a 4 on the second', the answer is \frac{1}{6}\times\frac{1}{6}=\frac{1}{36}\approx 0.028. The number \frac{1}{6} answers only a question about one roll, and \frac{5}{6} is the probability of not obtaining a given face on one roll, so neither can stand for a two-roll sequence.

Dice need not carry the numbers 1 to 6. A die may have only some labels. If each of four allowed labels has probability \frac{1}{4}, then each ordered pair of two such dice has probability \frac{1}{4}\times\frac{1}{4}=\frac{1}{16}. To handle a condition on the sum, list the possible sums, see which satisfy the condition, and count the pairs that give them. 'Greater than 11' means at least 12, and an impossible sum simply contributes nothing to the count. As a worked example, if the allowed labels are 1, 3, 4 and 6 and the sum must be at least 9, the qualifying pairs are (3,6), (6,3), (4,6), (6,4) and (6,6), so the probability is \frac{5}{16}.

For 'exactly k successes in n independent throws', you must count the arrangements as well as the probability of one arrangement. For exactly one six in three rolls, the six may occupy any of 3 positions, and each arrangement has probability \frac{1}{6}\left(\frac{5}{6}\right)^2=\frac{25}{216}. Hence the answer is \binom{3}{1}\cdot\frac{1}{6}\left(\frac{5}{6}\right)^2=\frac{75}{216}=\frac{25}{72}. Dropping the factor \binom{3}{1} gives the common trap value \frac{25}{216}.

Conditions that relate the two numbers, such as 'the second is a multiple of the first' or 'the sum is prime', are best handled by enumerating the 36 ordered pairs, grouped by the first value. A multiple here means b=ka for a positive integer k, so b=a itself counts. For a first value a=1, all six values of b qualify. For a=2 the qualifying values are 2, 4 and 6; for a=3 they are 3 and 6; and for a=4,5,6 only b=a qualifies. The total is 6+3+2+1+1+1=14, giving \frac{14}{36}=\frac{7}{18}. Treating the counts as uniform leads to wrong choices such as \frac{1}{6} or \frac{5}{18}.

For a prime sum, note that two dice give sums from 2 to 12, and that 1, 4, 6, 8, 9, 10 and 12 are not prime. The prime sums possible are 2, 3, 5, 7 and 11, which arise from 1, 2, 4, 6 and 2 ordered pairs respectively. Adding these gives 15 favourable outcomes out of 36, so the probability is \frac{15}{36}=\frac{5}{12}. Counting only the small primes gives too few outcomes, while miscounting a single sum such as 7 changes the total.

Key expressions in this topic:

• favourable outcomes — outcomes that satisfy the stated condition, counted out of the total sample space. e.g. Of the 36 ordered pairs of two dice, 4 have both values greater than 4, so the probability is \frac{4}{36}=\frac{1}{9}.
• at least one — use the complement: P(\text{at least one})=1-P(\text{none}). e.g. For two dice, P(\text{at least one even})=1-\frac{1}{4}=\frac{3}{4}.
• exactly — requires a binomial count with \binom{n}{k} for the positions of the successes.
• multiple of — b=ka for a positive integer k. e.g. 6 is a multiple of 3, but 5 is not.
• prime sum — for two dice, a sum equal to 2, 3, 5, 7 or 11.

Permutations with restricted positions

A permutation with restricted positions is an arrangement of distinct objects in which a condition limits where some object may go, whether two objects may sit together, or how some objects must be ordered relative to others. The usual strategy is to count the unrestricted total first and then remove the forbidden cases, or to place the most constrained object first and arrange the rest freely. For n distinct objects in a row, the total is n!, so every restricted count starts from n! and is adjusted from there.

The first tool is the complement method. When one object must not occupy one given position, the forbidden arrangements are those in which that object is fixed in the position, and the remaining n-1 objects fill the other seats in (n-1)! ways. The permitted count is therefore n! - (n-1)!. Do not multiply by (n-1) when the condition is a prohibition, because that treats the forbidden positions as allowed ones.

The second tool is the block method for adjacency. If two objects must sit together, glue them into one block and order the two objects inside it in 2 ways, giving 2 \times (n-1)! arrangements. If they must not sit together, subtract this from the total, giving n! - 2(n-1)!. When an additional condition fixes the left-to-right order of two of the objects, exactly half of the valid arrangements satisfy it, because swapping those two labels is a bijection between the two sets. Divide the count by 2 in that case.

A third pattern is separation. If two objects must be separated by exactly one person, their seat numbers differ by 2. List the possible seat pairs, multiply by the orders of the two objects, and then count the remaining objects in the free seats while respecting any neighbour restriction. Check each placement separately, because the number of free neighbours of a fixed object changes with its location.

When a position is fixed by a condition and a second object has a neighbour restriction, fix the fixed position first, then place the most restricted objects in the remaining seats, and only then fill the rest. Enumerate the cases that break the neighbour rule explicitly so that none is double counted.

A permutation matrix is a special case: each row and each column of a grid contains exactly one marked cell. Choosing the column for each row in turn gives n! valid marking patterns, so a 3 \times 3 grid has 3! = 6.

The last pattern is relative-order (inequality) constraints on distinct digits or objects. Read each inequality as a ranking statement. An object that must exceed exactly k others must have rank k+1 among the group, so it is forced to a specific value when the set is \{1,2,\ldots,n\}. A practical method is to test each candidate value against all the inequalities, using the number of smaller and larger values that each candidate needs. For example, if a digit must be greater than two digits and less than two others among \{1,2,3,4,5\}, it must equal 3, because only 3 has exactly two smaller and two larger digits.

• complement method — count all arrangements and subtract the forbidden ones; e.g. 5! minus the arrangements with one object in a fixed seat gives 5! - 4! = 96.
• block method — treat two objects that must be together as one unit; e.g. 2 \times 3! for two objects together among four.
• exactly one person between — the seat numbers differ by 2, not 1.

Arrangements of distinct items in all orders

When n distinct items are arranged in every possible order, each complete ordering is a different outcome, and the total is the number of permutations of n objects, n! = n \times (n-1) \times \cdots \times 1. For four distinct items, this gives 4! = 24 orderings. A problem that asks for every order to be tried therefore reduces to computing n!, provided the items are all different and each one is used exactly once.

Beware of the common distractors in this family. Doubling the count, as 2 \times n!, gives the total for two independent counters rather than one. The power 2^n counts yes/no choices for including or excluding each item, which is a subset count rather than an ordering count. Halving the count, n!/2, is justified only when some symmetry or identical-object condition removes half the orders, and no such condition is present for distinct items.

When only some of the items are used, the count is an ordered selection, written as the permutation ^nP_r = \frac{n!}{(n-r)!}. Here n is the number of available candidates and r is the number of positions. Equivalently, ^nP_r = \binom{n}{r} \times r!, which means choose the set first and then arrange it. Using digits from a restricted set to form a number is a standard application. The single-digit primes are 2, 3, 5 and 7, so four digits are available. Choosing three distinct ones and placing them in order gives ^4P_3 = 4 \times 3 \times 2 = 24 numbers.

Two mistakes recur in this topic. The first is allowing repetition: if digits may repeat, each of r positions has m choices, giving m^r, which is 64 for 4 candidates in 3 positions, but the distinct-digit requirement rules this out. The second is ignoring order: \binom{4}{3} = 4 counts only the sets of three primes, and each set contributes 3! = 6 arrangements, so ignoring order undercounts. Two positions chosen from four candidates gives ^4P_2 = 12, which counts two-digit arrangements, not three-digit numbers.

Counting arrangements on a circle is a separate but related topic in combinatorics. Passages on this subject often pair a statement that a method is 'sometimes' used with one claiming it is 'always' used. A universal claim with 'always' is contradicted by a source that says 'sometimes', while a statement that some instances occur is supported by the same source. Read qualifiers such as always, sometimes, and often carefully when checking inferences.

• distinct items — each item is different, so swapping two items produces a new ordering.
• ordered selection — choose r of n items where order matters, ^nP_r.
• with repetition — each position has the full set of m choices, giving m^r.
• all orders of four distinct items — 4! = 24.

Pigeonhole principle for colour picks

The pigeonhole principle states that if more objects are placed into boxes than there are boxes, some box must receive at least two objects. Its generalized form says that if n objects are placed into k boxes, some box holds at least \lceil n/k \rceil objects, because otherwise the total would be at most k(\lceil n/k \rceil - 1) < n. In a question asking for the smallest number of picks that guarantees a result, the method is to find the worst case, meaning the largest number of picks that can still avoid the condition, and then add one. If the goal is two balls of the same colour and there are k colours, the worst case takes one ball of each colour, so the answer is k+1, provided every colour has at least one ball. Thus with three colours the answer is 4, regardless of how many balls each colour contains.

For a goal of m balls of the same colour, the worst case takes m-1 balls of each colour. A colour with fewer than m-1 balls can contribute only its own count c_i, so the answer is \sum_i \min(c_i, m-1) + 1. For example, if a bag holds 2 red, 5 blue and 9 green balls and we want 3 of one colour, the worst case draws 2 red, 2 blue and 2 green, which is 6 balls, so the answer is 7. A common trap is to answer with the total number of balls or the number of colours, instead of the worst case plus one.

The same principle governs distributions. If n objects are spread over k categories, the principle guarantees that some category holds at least \lceil n/k \rceil objects, so 100 objects over 10 categories force a category with at least 10. It guarantees only the existence of such a crowded category, not which one, and it says nothing about every category being non-empty, because the objects may all fall into a few categories. To refute a claim about a particular category or about the first few categories, one needs only a single valid distribution that violates it, such as placing every object in one category.

Statements that require every category to be occupied, or that cap the size of one specific category, fail whenever the distribution is unconstrained. A counterexample with all objects in one category, or with all objects in the last few categories, settles such a statement.

Map coloring with adjacent regions

A proper colouring of a graph assigns colours to its vertices so that no two vertices joined by an edge share a colour. The smallest number of colours that allows a proper colouring is the chromatic number. In map colouring, two regions are adjacent when they share a boundary segment of positive length, and sharing only a single point does not count; the four colour theorem states that any planar map can be coloured with at most four colours. When a question places objects such as the corners of a solid, the edges of the solid define adjacency, so the problem becomes a graph colouring problem on those corners.

Two simple bounds apply. If a graph has no edges, one colour suffices. If it has at least one edge, one colour is impossible, so the chromatic number is at least 2. A graph is bipartite exactly when its vertices can be split into two sets with every edge joining the two sets, equivalently when it contains no odd cycle. A bipartite graph with at least one edge has chromatic number exactly 2, since one colour can be used for each set. The graph formed by the corners and edges of a cube is bipartite, for instance because the parity of the sum of the corner coordinates separates adjacent corners.

To solve such a problem, first check for an odd cycle or a triangle, and if there is none, look for a bipartition, which can often be found by parity or by breadth-first search alternating colours. For example, a cycle with six vertices has chromatic number 2, while a cycle with five vertices needs 3, and the complete graph on four vertices needs 4 because every pair of its vertices is adjacent. A frequent error is to answer with the number of vertices or the number of regions instead of the chromatic number.

Adjacent swap sorting steps

An adjacent swap interchanges two neighbouring items. When all items are distinct, the number of inversions, that is, the number of pairs (i,j) with i<j and a_i > a_j, measures how far a sequence is from sorted order. Each adjacent swap changes the inversion count by exactly one, so the minimum number of adjacent swaps needed to sort a sequence equals its inversion count. For example, the sequence 3 1 2 has two inversions, (3,1) and (3,2), and it is sorted in two swaps: 3 1 2 to 1 3 2, then to 1 2 3.

When items are of two identical types, only the pattern of types matters. Let the target arrangement be fixed. Count the pairs consisting of one item of the first type and one item of the second type that stand in the wrong relative order. Interchanging an adjacent pair of different types changes this count by exactly one, while interchanging two identical neighbours changes nothing and wastes a step. Hence each step can reduce the count by at most one, which gives a lower bound.

The bound is attained by moving items one pair at a time, so the minimum number of steps equals the number of mismatched pairs that must be reversed. In the arrangement X X Y, the target Y X X requires reversing the two pairs formed by each X with the Y, so the count is 2 and two steps suffice: X X Y to X Y X, then to Y X X. Note that the count is the number of pairs, not the number of items; if there are 3 items of one type and 3 of the other, the count can be as large as 3 \times 3 = 9.

Common errors include counting only the number of items that move, adding the counts instead of multiplying them, and treating swaps of identical neighbours as useful. Always verify that the chosen lower bound is achievable by constructing an explicit sequence of swaps of the required length.

Spinner outcome probability

A spinner, a die, or any similar device is analysed with the classical definition of probability. When every outcome is equally likely, the probability of an event is P(E)=\frac{\text{number of favourable outcomes}}{\text{total number of equally likely outcomes}}. The formula applies only when the outcomes are truly equally likely, so the first task is to check that each sector or face has the same chance of stopping the arrow.

When several devices are used together, the sample space is built with the multiplication rule. If the spins are independent, the result of one spin does not change the chances of the other, and the number of ordered outcomes is the product of the numbers of outcomes of each device. For two spinners with 8 equally likely sectors each, there are 8\times 8=64 equally likely ordered pairs, and each pair has probability \frac{1}{64}.

To find an event such as 'the sum equals a given value', list the ordered pairs (a,b) with a+b=s in which both entries lie in the allowed range. For s=8 with entries from 1 to 8, the pairs run from (1,7) to (7,1), and the pair (4,4) is counted once. Order matters, because (2,6) and (6,2) come from different spinners and are different outcomes. Counting unordered sets instead is a common error.

The probability is the favourable count multiplied by \frac{1}{64}, or equivalently divided by 64. Fractions such as \frac{4}{64} and \frac{1}{16} denote the same number, so answers should be compared after reduction. It is useful to check the count against the total before choosing among the options.

Example: two fair dice are rolled, and we want the probability that the sum is 7. The total number of ordered outcomes is 6\times 6=36. The ordered pairs with sum 7 are (1,6),(2,5),(3,4),(4,3),(5,2),(6,1), six in all, so P=\frac{6}{36}=\frac{1}{6}.

Binomial probability of exact successes

A binomial experiment has a fixed number n of independent trials, and each trial has only two results: success with probability p and failure with probability 1-p. The number of successes X then follows a binomial distribution, and the probability of exactly k successes is P(X=k)=\binom{n}{k}p^{k}(1-p)^{n-k}.

The coefficient \binom{n}{k} counts the ways to choose which k of the n trials are successes. Each specific arrangement with k successes has probability p^{k}(1-p)^{n-k}, because independence allows the probabilities to be multiplied. Omitting the coefficient gives only the probability of one particular order, which is a frequent mistake. The same reasoning applies when a fair die is rolled several times and one particular face must appear exactly once.