Corrected exercises: counting and probability (201-N11)

$\frac{11!}{8!}=\frac{11\times 10\times 9\times 8!}{8!}=11\times 10\times 9=990$. Pitfall: simplifying the numbers themselves, as if $\frac{11!}{8!}$ were equal to $\left(\frac{11}{8}\right)!$, which makes no sense.

$P(9,4)=\frac{9!}{(9-4)!}=\frac{9!}{5!}=9\times 8\times 7\times 6=3{,}024$: four decreasing factors starting from $9$.

$\binom{12}{4}=\frac{12\times 11\times 10\times 9}{4\times 3\times 2\times 1}$. Simplify before multiplying: $\frac{12}{4\times 3}=1$ and $\frac{10}{2}=5$, hence $11\times 5\times 9=495$.

By symmetry, $\binom{20}{17}=\binom{20}{3}=\frac{20\times 19\times 18}{3\times 2\times 1}=20\times 19\times 3=1{,}140$. Pitfall: applying the formula with $k=17$, seventeen factors in the numerator and in the denominator, for the same result at the price of many possible errors.

Ordered with replacement: each of the $5$ positions has $6$ choices, so $6^{5}=7{,}776$. Pitfall: taking $5^{6}=15{,}625$, by swapping the number of positions and the number of choices.

Unordered with replacement: $\binom{n+k-1}{k}=\binom{5+3-1}{3}=\binom{7}{3}=\frac{7\times 6\times 5}{6}=35$. Pitfall: $\binom{5}{3}=10$, which forbids repetition.

COCORICO has $8$ letters: C three times, O three times, R and I once each. $\frac{8!}{3!\,3!}=\frac{40{,}320}{36}=1{,}120$. Pitfall: $8!=40{,}320$, which counts as different the words obtained by swapping two C's or two O's.

The complete row is worth $\sum_{k=0}^{10}\binom{10}{k}=2^{10}=1{,}024$; the term $\binom{10}{0}=1$ is missing here, so the sum is $1{,}023$. Pitfall: answering $1{,}024$ without noticing that the sum starts at $k=1$.

Binomial theorem: the term in $x^{4}$ is $\binom{7}{4}(2x)^{4}(-1)^{3}=35\times 16x^{4}\times(-1)=-560x^{4}$. The coefficient is $-560$. Pitfall: forgetting the power of $2$, which gives $-35$, or the sign of $(-1)^{3}$, which gives $560$.

Through the complement: a set with $8$ elements has $2^{8}=256$ subsets; remove the empty set, $\binom{8}{0}=1$, and the eight singletons, $\binom{8}{1}=8$. That leaves $256-1-8=247$. Pitfall: removing only the singletons, which gives $248$.

If an operation breaks down into $k$ successive steps offering $n_{1},n_{2},\dots,n_{k}$ choices respectively, and if the number of choices at each step does not depend on the previous choices, then the total number of outcomes is the PRODUCT $n_{1}\times n_{2}\times\dots\times n_{k}$. On the figure, three starters each lead to two mains, and each of these six paths leads to two desserts: you read $3\times 2\times 2=12$ leaves. The tree makes the condition for applying the principle visible: every node of a given level carries the same number of branches.

Four positions, 26 choices each, independent: $26^{4}=456{,}976$ words. The result is written with thousands separators because the order of magnitude is the useful information: half a million, which a program lists in a fraction of a second.

IPv4: $2^{32}=4{,}294{,}967{,}296$, about 4.3 billion, fewer than the world's population, which explains the exhaustion of the supply. IPv6: $2^{128}\approx 3.4\times 10^{38}$, a number of a different order altogether, around $10^{28}$ addresses per person. Quadrupling the number of bits does not quadruple the number of addresses, it raises it to the fourth power: this is the point that the multiplication principle makes obvious.

$2^{24}=16{,}777{,}216$ shades, about 16.7 million. You can also see it as $256^{3}$, each component taking 256 values: both expressions give the same number, since $256=2^{8}$ and $\left(2^{8}\right)^{3}=2^{24}$.

With no constraint: $26\times 26\times 10^{4}=676\times 10{,}000=6{,}760{,}000$ identifiers. With two DISTINCT letters, the second choice offers only 25 possibilities: $26\times 25\times 10^{4}=6{,}500{,}000$. The loss is $260{,}000$ identifiers, about 3.8 percent. Note that the multiplication principle still applies, even though the number of choices at the second step depends on the first: what matters is that this NUMBER is always the same, here 25, whichever letter was already taken.

ORDERED WITHOUT REPLACEMENT, the permutations: $\frac{n!}{(n-k)!}$, for “how many podiums”. ORDERED WITH REPLACEMENT, the strings: $n^{k}$, for “how many passwords”. UNORDERED WITHOUT REPLACEMENT, the combinations: $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$, for “how many committees”. UNORDERED WITH REPLACEMENT: $\binom{n+k-1}{k}$, for “how many ways to distribute identical objects”. The fourth is the only one you do not invent in your head; the other three are recovered from the multiplication principle.

A complete ranking of 5 candidates is a PERMUTATION: $5!=120$. It is the special case $k=n$ of the permutations, where $\frac{5!}{0!}=5!$ since $0!=1$ by convention. This convention is not arbitrary: it is what makes the permutation formula valid all the way to the end.

DISTINCT: this is a permutation of 3 letters out of 26, that is $26\times 25\times 24=15{,}600$. WITH REPETITIONS: this is a string, that is $26^{3}=17{,}576$. The gap is small here, 11.2 percent, but forbidding repetitions ALWAYS reduces the number of passwords: a rule that forbids two identical letters therefore weakens the password instead of strengthening it, which is the opposite of intuition.

The order of the numbers does not matter and repetition is impossible: this is a combination. $\binom{49}{6}=\frac{49\times 48\times 47\times 46\times 45\times 44}{720}=13{,}983{,}816$, close to 14 million tickets. The probability of winning with one ticket is therefore about $7.15\times 10^{-8}$.

Four independent Boolean options: each is true or false, so $2^{4}=16$ configurations. If EXACTLY 2 must be turned on, you choose which ones without caring about the order: $\binom{4}{2}=6$. You can check consistency by summing over all sizes: $\binom{4}{0}+\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=1+4+6+4+1=16$ ✓, which is exactly the property of Pascal's triangle studied in the next exercise.

Count the $k$-element subsets of an $n$-element set, singling out one particular element $x$. These subsets split into two categories with no overlap. Those that CONTAIN $x$: you still have to choose $k-1$ elements among the $n-1$ others, which gives $\binom{n-1}{k-1}$. Those that do NOT contain it: you must choose the $k$ elements among the $n-1$ others, which gives $\binom{n-1}{k}$. Every subset falls into exactly one of the two cases, hence the equality. No computation, only a split into two.

On the figure, $\binom{4}{2}=6$ is indeed the sum of the two numbers above it in the previous row, $\binom{3}{1}=3$ and $\binom{3}{2}=3$, which the two strokes mark. This is the rule for building the triangle: each number is the sum of the two above it, the edges being 1 because there is only one empty subset and only one full subset.

COUNTING: the sum $\sum_{k=0}^{n}\binom{n}{k}$ counts all the subsets of the set, sorted by size; but you can also count a subset by deciding for EACH element whether it belongs to it or not, which gives $2^{n}$ by the multiplication principle. Both counts are about the same set, so they are equal. BINOMIAL THEOREM: the formula $(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}$, applied with $a=b=1$, gives directly $2^{n}=\sum_{k=0}^{n}\binom{n}{k}$. The figure displays these sums row by row: 1, 2, 4, 8, 16, 32, 64.

BY THE FORMULA: $\binom{10}{3}=\frac{10\times 9\times 8}{3\times 2\times 1}=\frac{720}{6}=120$. BY PASCAL: $\binom{10}{3}=\binom{9}{2}+\binom{9}{3}=36+84=120$ ✓. The first method is the one to use by hand, simplifying BEFORE multiplying; the second is useful when you build a complete table.

It runs into exactly the naive Fibonacci problem: the calls OVERLAP massively, because $\binom{n-1}{k-1}$ and $\binom{n-1}{k}$ go back down to the same subproblems. The number of calls becomes of the order of $\binom{n}{k}$ itself, hence astronomical. The remedy is the same: MEMOIZATION, or the iterative construction of the triangle row by row, which costs $O(nk)$ operations. This is the canonical example of dynamic programming, and it is no accident that the combinatorial relation and the algorithmic relation are the same equality.

SIMPLE VERSION: if you put $n+1$ or more objects into $n$ pigeonholes, at least one pigeonhole contains at least two objects. QUANTITATIVE VERSION: putting $m$ objects into $n$ pigeonholes, at least one pigeonhole contains at least $\left\lceil\frac{m}{n}\right\rceil$ objects. The proof is by contradiction: if every pigeonhole contained strictly fewer, the total would be strictly less than $m$, a contradiction.

The pigeonholes are the 12 months, the objects are the 13 people. Since $13>12$, at least one month contains two people ✓. Notice what the statement does NOT say: it does not say which month, nor how many pairs. It is a pure existence statement, of the same kind as the existence theorems of calculus, such as the intermediate value theorem.

$\left\lceil\frac{1000}{100}\right\rceil=10$: at least one slot contains at least 10 keys. This is a WORST-CASE guarantee, independent of the hash function used, however good it is. It explains why a hash table must provide for collision handling, chaining or probing, and why its access cost is constant only on average, never in the worst case.

A 256-bit hash function has exactly $2^{256}$ possible values, a finite number. The set of files, on the other hand, is infinite: you can build files as long as you like. So an infinity of objects is put into a finite number of pigeonholes, and the principle guarantees not only that a collision exists, but that infinitely many files share the same digest. The security of a hash function therefore does NOT rest on the absence of collisions, which is impossible, but on the difficulty of FINDING one.

Take one person $A$. They have 5 relationships, each of two types, acquaintance or stranger: by the pigeonhole principle, one of the two types appears at least $\left\lceil\frac{5}{2}\right\rceil=3$ times. Suppose $A$ knows three people $B$, $C$ and $D$. If two of them know each other, say $B$ and $C$, then $A$, $B$ and $C$ all know each other ✓. Otherwise, $B$, $C$ and $D$ are mutual strangers ✓. The case where $A$ is a stranger to three people is handled symmetrically. This is the first theorem of Ramsey theory, and it rests entirely on two applications of the pigeonhole principle.

$P(A)=\frac{\text{number of favourable outcomes}}{\text{number of possible outcomes}}$. The condition is that all the elementary outcomes be EQUALLY LIKELY, which is not automatic and must be justified: a random draw, a fair die, a uniform generator. On a non-uniform sample space the formula is wrong, and the classic error is to apply it to compound events rather than to elementary outcomes.

The sample space is the set of 5-card hands, that is $\binom{52}{5}=2{,}598{,}960$ equally likely hands. The favourable hands are built in two independent steps: choose 2 aces out of 4, that is $\binom{4}{2}=6$, and choose the 3 other cards among the 48 non-aces, that is $\binom{48}{3}=17{,}296$. Total: $6\times 17{,}296=103{,}776$. Probability: $\frac{103{,}776}{2{,}598{,}960}\approx 0.0399$, about 4 percent.

A byte has $2^{8}=256$ equally likely values. Those containing exactly three bits equal to 1 correspond to choosing the three positions out of eight: $\binom{8}{3}=56$. Probability: $\frac{56}{256}=0.21875$, about 22 percent. This is close to the maximum, which is reached at 4 bits equal to 1 with $\binom{8}{4}=70$ values out of 256: a random byte rarely has very few or very many bits turned on.

The 62 characters split into 52 letters and 10 digits. No digit means that all 8 positions are filled from the 52 letters: $52^{8}$ favourable outcomes out of $62^{8}$ possible. Probability: $\left(\frac{52}{62}\right)^{8}=0.8387^{8}\approx 0.2448$, about 24 percent. Nearly one random password in four contains no digit, which explains why security policies require one explicitly.

Because counting “at least one” requires distinguishing the cases of one, two, three digits and so on, whereas the opposite, “none”, is counted in one go. The rule is $P(\text{at least one})=1-P(\text{none})$. Here: $1-0.2448=0.7552$, about 76 percent. The habit applies to every statement starting with “at least”, and it will be decisive in the birthday problem of exercise 10.

$P(A\mid B)=\frac{P(A\cap B)}{P(B)}$ for $P(B)\neq 0$: it is the probability of $A$ once we KNOW that $B$ has occurred, in other words we replace the sample space by $B$. LAW OF TOTAL PROBABILITY: if $B_{1},\dots,B_{n}$ form a partition of the sample space, then $P(A)=\sum_{i}P(A\mid B_{i})P(B_{i})$. This is the formula that lets you go down the weighted tree of the figure by multiplying along the branches, then adding the favourable leaves.

Let $M$ be the event “the person has the disease” and $T$ the event “the test is positive”. $P(M)=0.01$, $P(T\mid M)=0.99$, $P(T\mid\overline{M})=0.05$. Total probability: $P(T)=0.01\times 0.99+0.99\times 0.05=0.0099+0.0495=0.0594$. Bayes: $P(M\mid T)=\frac{0.0099}{0.0594}=\frac{1}{6}\approx 0.1667$. Only ONE positive person in six is really sick.

Intuition spontaneously answers “about 99 percent”, confusing $P(T\mid M)$ with $P(M\mid T)$. The gap comes from the RARITY of the disease: out of 10,000 people, 100 are sick and 99 will be detected, but 9,900 are healthy and 495 of them will test positive wrongly. The false positives are five times more numerous than the true ones, not because the test is bad, but because it is applied to an immense population of healthy people. This is why rare diseases are not screened for systematically.

Let $S$ be the event “spam” and $G$ the event “the email contains the word free”. $P(G)=0.6\times 0.3+0.4\times 0.02=0.18+0.008=0.188$. Bayes: $P(S\mid G)=\frac{0.18}{0.188}\approx 0.9574$, about 96 percent. This time the result is very close to certainty, and the contrast with part b is worth noting: the same formula gives 17 percent here and 96 percent there. What changes is not the quality of the evidence, it is the PRIOR probability, 1 percent against 60 percent.

NO, it is impossible. Mutually exclusive means $A\cap B=\varnothing$, so $P(A\cap B)=0$. Independent means $P(A\cap B)=P(A)P(B)$, which is strictly positive since both probabilities are. The two conditions contradict each other. Intuitively: if $A$ and $B$ cannot happen together, then knowing that $A$ has occurred tells you something very strong about $B$, namely that it has not. Mutually exclusive is therefore the opposite of independent, not a synonym, and this confusion is one of the costliest in the chapter.

If $X$ takes the values $x_{1},\dots,x_{m}$ with probabilities $p_{1},\dots,p_{m}$, then $E(X)=\sum_{i}x_{i}p_{i}$. It is the WEIGHTED average of the values, and its interpretation is that of the law of large numbers: when you repeat the experiment a large number of times, the average of the observed results approaches $E(X)$. An expected value is therefore not a prediction for a single trial, it is a prediction for a large number of trials.

The element is at position $k$ with probability $\frac{1}{n}$, and the search then costs $k$ comparisons. So $E=\sum_{k=1}^{n}k\times\frac{1}{n}=\frac{1}{n}\times\frac{n(n+1)}{2}=\frac{n+1}{2}$. We recover the sum of the first integers proved by induction in the induction and recursion chapter: the two chapters meet here.

$E=\frac{1001}{2}=500.5$ comparisons on average, against 1000 in the WORST CASE, the one where the element is in the last position. The ratio is only 2: average-case analysis does not change the order of magnitude, and linear search remains linear. This is precisely what sets it apart from quicksort in part e, where the gap is a factor of thousands.

Let $X$ be the number of flips. We have $P(X=k)=\left(\frac{1}{2}\right)^{k}$, since you need $k-1$ tails followed by a head. So $E=\sum_{k\geq 1}k\left(\frac{1}{2}\right)^{k}=2$. A faster way to get it: the first flip costs 1; with probability $\frac{1}{2}$ it is over, otherwise you start again from zero. Hence $E=1+\frac{1}{2}E$, that is $E=2$. This reasoning by conditioning on the first step is the one used to analyze randomized algorithms.

ON AVERAGE: $2\times 10^{6}\times\ln\left(10^{6}\right)=2\times 10^{6}\times 13.8155\approx 2.76\times 10^{7}$ comparisons, about 28 million. WORST CASE: $\frac{\left(10^{6}\right)^{2}}{2}=5\times 10^{11}$, that is 500 billion, eighteen thousand times more. It is used anyway for two reasons. First, because the worst case corresponds to an already sorted array with a naive pivot choice, a situation that a RANDOM pivot makes extremely improbable. Second, because its hidden constant is small and it works in place, which makes it faster in practice than merge sort, even though merge sort is better in the worst case. Choosing an algorithm therefore requires looking at BOTH measures and knowing which one describes the real use.

FALSE, it is exactly the opposite. Forbidding repetitions REDUCES the set of possible passwords: with 3 characters out of 26, we go from $26^{3}=17{,}576$ to $26\times 25\times 24=15{,}600$, which is 11 percent fewer. Any rule that forbids something shrinks the search space and therefore makes a brute-force attack easier. What strengthens a password is INCREASING its length and the size of its alphabet, never adding constraints.

FALSE, and the statement confuses $P(T\mid M)$ with $P(M\mid T)$. With a prevalence of 1 percent and 5 percent false positives, Bayes' theorem gives $P(M\mid T)=\frac{1}{6}\approx 17$ percent. The reason is that healthy people are 99 times more numerous, so that their 5 percent of false positives swamp the true positives in number. A conditional probability and its converse have no reason to be close.

FALSE, and the two notions are even contradictory for events of nonzero probability. Mutually exclusive gives $P(A\cap B)=0$; independent gives $P(A\cap B)=P(A)P(B)>0$. Knowing that $A$ has occurred tells you, on the contrary, that $B$ has not, which is the height of dependence. Remember the wording: mutually exclusive is about SETS, independent is about INFORMATION.

FALSE, and it is impossible by the pigeonhole principle. A 256-bit hash function has only $2^{256}$ values whereas the possible files are infinite in number: infinitely many files therefore share each digest. What we ask of a good hash function is not the absence of collisions but the difficulty of FINDING one, which is a computational property and not a set-theoretic one.

FALSE. A hand of cards is a SET: receiving the ace then the king or the king then the ace gives the same hand. We therefore use COMBINATIONS, $\binom{52}{5}=2{,}598{,}960$. Using permutations would give $52\times 51\times 50\times 49\times 48=311{,}875{,}200$, which is 120 times too many, exactly the factor $5!$ that counts the orderings of one hand. The test to run every time: if two results differ only in their order, are they the same result?

Eight positions, 95 choices each: $95^{8}=6{,}634{,}204{,}312{,}890{,}625$, about $6.63\times 10^{15}$, a little over six quadrillion.

$\frac{6.63\times 10^{15}}{10^{10}}\approx 663{,}420$ seconds, or about $7.68$ days. An eight-character password, even with all the keyboard symbols, therefore falls in a week against dedicated hardware. Note that this figure is a WORST case, the average being half as long, around four days.

$95^{12}\approx 5.40\times 10^{23}$, so $\frac{5.40\times 10^{23}}{10^{10}}=5.40\times 10^{13}$ seconds, that is about $1.71\times 10^{6}$ years, nearly 1.7 million years. Four more characters take you from a week to a million years: the factor is $95^{4}\approx 81.5$ million.

$26^{8}=208{,}827{,}064{,}576\approx 2.09\times 10^{11}$, so $\frac{2.09\times 10^{11}}{10^{10}}\approx 21$ seconds. Conclusion: an eight-letter lowercase password does not last half a minute. Going from 26 to 95 characters multiplies the time by about 32,000, which is considerable, but remains trivial next to the effect of length.

$8\log_{2}95=8\times 6.570=52.6$ bits; $12\log_{2}95=78.8$ bits; $8\log_{2}26=8\times 4.700=37.6$ bits. Entropy is PROPORTIONAL to the length and only LOGARITHMIC in the alphabet size: adding 4 characters is worth $4\times 6.57=26.3$ bits, whereas going from 26 to 95 characters over 8 positions is worth only 15. Length therefore weighs far more, which is why recent recommendations favour long passphrases over short strings of exotic symbols, which are harder to remember for a smaller gain.

The first person can be born on any day, the second must avoid 1 day, the third 2, and so on. By the multiplication principle: $P(\text{all distinct})=\frac{365}{365}\times\frac{364}{365}\times\dots\times\frac{365-n+1}{365}=\prod_{k=0}^{n-1}\frac{365-k}{365}$. This is exactly the calculation of the COMPLEMENT recommended in exercise 5, and it is essential here: counting the matches directly would require distinguishing the cases with two, three, four people involved.

$P(\text{at least one})=1-\prod_{k=0}^{n-1}\frac{365-k}{365}$. For $n=23$: about $0.5073$, a little over one chance in two. For $n=50$: about $0.9704$, or 97 percent. The figure shows the very fast rise of this curve, almost vertical between 15 and 35 people.