Corrected exercises: counting (201-SN1-RE)

$7!=7\times 6\times 5\times 4\times 3\times 2\times 1=5040$.

$10!=10\times 9\times 8\times 7!$, so $\dfrac{10!}{7!}=10\times 9\times 8=720$.

Pitfall: computing $10!=3{,}628{,}800$ and $7!=5040$ separately, then dividing. The result is the same, but with two large numbers to copy without error.

$P(8,\,3)=\dfrac{8!}{5!}=8\times 7\times 6=336$.

Reading: three ORDERED places, 8 choices for the first, 7 for the second, 6 for the third.

$\dbinom{10}{4}=\dfrac{10\times 9\times 8\times 7}{4\times 3\times 2\times 1}=\dfrac{5040}{24}=210$.

The $5040$ arrangements of 4 objects out of 10 fall into bundles of $4!=24$ that contain the same objects: each bundle is a single combination.

By symmetry, $\dbinom{12}{10}=\dbinom{12}{2}=\dfrac{12\times 11}{2}=66$.

Keeping 10 objects out of 12 is exactly deciding which 2 to leave out: the two choices match up one to one.

$(n+1)!=(n+1)\times n\times(n-1)!$, so $\dfrac{(n+1)!}{(n-1)!}=(n+1)\,n$.

For $n=9$: $10\times 9=90$.

Five places, four choices at each, and the choice at one place does not reduce the next ones: $4^{5}=1024$.

Pitfall: writing $P(4,\,5)$. There is no arrangement of 5 distinct objects out of 4; here the bases may repeat, so this is a sequence with repetition.

If the 8 objects were all distinct, there would be $8!=40{,}320$ arrangements.

Swapping the 3 identical objects among themselves does not change the arrangement ($3!=6$ ways), and neither does swapping the other 2 ($2!=2$ ways): each visible arrangement has been counted $6\times 2=12$ times.

$\dfrac{8!}{3!\,2!}=\dfrac{40{,}320}{12}=3360$.

$\dbinom{6}{2}=15$ and $\dbinom{4}{1}=4$: two choices made one after the other multiply, $15\times 4=60$.

The $x^{3}$ term of $(1+x)^{7}$ is $\dbinom{7}{3}\,1^{4}\,x^{3}$, so the coefficient is $\dbinom{7}{3}=\dfrac{7\times 6\times 5}{6}=35$.

$\dbinom{n}{2}=\dfrac{n(n-1)}{2}=45$ gives $n(n-1)=90=10\times 9$, so $n=10$.

The equation $n^{2}-n-90=0$ also has the root $n=-9$, rejected: $n$ is a number of objects.

Inclusion-exclusion formula: $|A\cup B|=|A|+|B|-|A\cap B|=25+18-7=36$.

The 7 common elements belong to both sets: the sum $25+18$ counts them twice, so we remove them once.

A code is built in four steps: the letter (8 choices), then the first digit (10 choices), the second (10), the third (10).

The number of choices at a step does not depend on the earlier choices: the multiplication principle applies.

$8\times 10\times 10\times 10=8000$ codes.

The digits must be distinct: 10 choices for the first, 9 for the second (anything but the first), 8 for the third.

$8\times 10\times 9\times 8=5760$ accepted codes.

The NUMBER of choices at each step stays fixed, even though the LIST of choices depends on the earlier steps: that is all the multiplication principle requires.

“At least one 0” combines three cases (one, two or three zeros): go through the complement, “no 0”.

Codes with no 0 at all: $8\times 9\times 9\times 9=8\times 729=5832$.

Codes with at least one 0: $8000-5832=2168$.

The calculation $8\times 3\times 100$ produces C400 twice: by choosing the 0 in the second place and then “0” for the third, and by choosing the 0 in the third place and then “0” for the second. It produces C000 three times, once per chosen place.

For one station, each event $Z_{i}$ contains $10\times 10=100$ codes, each intersection $Z_{i}\cap Z_{j}$ contains $10$, and $Z_{1}\cap Z_{2}\cap Z_{3}$ a single one.

$|Z_{1}\cup Z_{2}\cup Z_{3}|=3\times 100-3\times 10+1=271$.

Check: $8\times 271=2168$, the result of c). The diagram in the solution shows the eight regions: $3\times 81+3\times 9+1=271$ and $729$ codes with no 0.

Pitfall: $300$ is not wrong by accident, it weights each code by its number of zeros, $243\times 1+27\times 2+1\times 3=300$. Counting means counting each code ONCE.

A station code has a digit in second position, a blank code has the letter L: no label is in both families, not even BL07 and B407.

The two families are disjoint, so the addition principle applies: $8000+100=8100$ labels.

The addition principle does not require the families to “look little alike”, it requires them to have NO element in common; that is what had to be checked.

With $k$ digits, there are $8\times 10^{k}$ codes. At least $25{,}000$ are needed: $10^{k}\ge 3125$.

$k=3$ gives $8000$ codes, not enough; $k=4$ gives $80{,}000$ codes. The smallest number of digits is $4$.

One more digit multiplies the capacity by 10, which leaves room for the following years.

The nine vials are distinct and all placed: this is a permutation of 9 objects.

9 choices for position 1, 8 for position 2, and so on: $9!=362{,}880$ orders.

Position 1 is fixed. The other 8 vials remain to be arranged in positions 2 to 9: $8!=40{,}320$ orders.

Glue E1 and E2 into a single block. After the blank, 7 objects remain to be arranged: the block and the 6 extracts, giving $7!=5040$ arrangements.

Inside the block, two orders: E1E2 or E2E1. Total: $2\times 7!=10{,}080$ orders.

The solution figure shows one of these orders: the block occupies positions 4 and 5.

Pitfall: forgetting the factor 2 of the block, or arranging 8 objects instead of 7. The block REPLACES two vials, it is not added to them.

The orders of b) split into two disjoint families: standards adjacent or not. Through the complement:

$40{,}320-10{,}080=30{,}240$ orders in which the standards are not adjacent.

Counting the non-adjacent positions directly is possible but longer; the complement avoids forgetting a case.

Swapping the labels E1 and E2 turns an order where E1 comes before E2 into an order where E2 comes before E1, and vice versa.

This swap pairs the orders two by two, without missing any or counting any twice: the two families therefore have the same number of elements.

$\dfrac{8!}{2}=20{,}160$ orders in which E1 comes before E2.

Pitfall: answering $10{,}080$ as in c). “Before” does not mean “right before”.

The positions are numbered: filling positions 1 to 4 with 4 distinct extracts is an arrangement, $P(6,\,4)=6\times 5\times 4\times 3=360$.

If the order did not matter, we would only choose a group of 4 extracts: $\dbinom{6}{4}=15$.

Ratio: $\dfrac{360}{15}=24=4!$. Each group of 4 extracts can be arranged in $4!$ ways in the 4 positions: $P(6,\,4)=4!\times\dbinom{6}{4}$.

This is the link between arrangements and combinations: first decide WHICH objects, then in WHAT ORDER.

The 4 controls are identical: only the SET of chosen wells matters, not the order in which they are chosen. This is a combination.

$\dbinom{24}{4}=\dfrac{24\times 23\times 22\times 21}{4\times 3\times 2\times 1}=\dfrac{255{,}024}{24}=10{,}626$ choices.

The strains are different: putting s1 in A1 and s2 in B3 is not the same as the reverse. This is an arrangement.

$P(24,\,4)=24\times 23\times 22\times 21=255{,}024$ placements.

Ratio: $\dfrac{255{,}024}{10{,}626}=24=4!$. Each choice of 4 wells from a) takes the 4 strains in $4!$ ways.

The thread of the series: the same plate, the same wells, but two outcomes are “the same” only in a). The sentence that says so comes before the formula.

Two steps: choose the row (4 ways), then 4 wells among the 6 of that row, $\dbinom{6}{4}=15$ ways.

$4\times 15=60$ choices. Two different rows give different choices, and no choice lies in two rows at once: nothing is counted twice.

There are exactly 4 rows: 4 wells in 4 different rows means ONE well per row.

Such a choice is therefore described by the column of the well in A, that of B, that of C, that of D, all different: $6\times 5\times 4\times 3=P(6,\,4)=360$ choices.

The solution figure shows one of them: A2, B5, C1, D4.

Pitfall: dividing by $4!$ “because order does not matter”. But the wells were never ordered: the row is a label that already tells the 4 wells apart, and each set of 4 wells is produced only once.

“At least one”: go through the complement, “no well in row A”, that is 4 wells taken from the 18 of rows B, C and D.

$\dbinom{18}{4}=\dfrac{18\times 17\times 16\times 15}{24}=3060$, so $10{,}626-3060=7566$ choices.

Pitfall: first choosing “the” well in row A (6 ways), then 3 others among 23. This calculation counts twice a choice with two wells in row A: there is no “designated” well.

Off the edge: rows B and C, columns 2 to 5, that is $2\times 4=8$ wells.

$\dbinom{8}{4}=\dfrac{8\times 7\times 6\times 5}{24}=70$ choices.

This plan protects the controls, at the cost of far fewer choices: $70$ against $10{,}626$.

“Mayflies” translates to $E$, “no stoneflies” to the complement $\overline{P}$, and “but” to an intersection: $E\cap\overline{P}$.

The stations of $E$ split into those in $P$ and those not in $P$: $|E\cap\overline{P}|=|E|-|E\cap P|=52-24=28$.

$=52+31+45-24-33-19+15=67$ stations.

Why the $+15$: a station in the center is counted 3 times in the first sum, then removed 3 times with the intersections. It must be added back once so that it counts exactly once.

$80-67=13$ stations with none of the three groups.

“No group” is the complement of “at least one group”: $\overline{E\cup P\cup T}$. By De Morgan's law, it is also “neither $E$, nor $P$, nor $T$”: $\overline{E}\cap\overline{P}\cap\overline{T}$.

These stations lie outside the three circles, in the rectangle of the 80 stations.

Start from the center, $|E\cap P\cap T|=15$, then remove the center from each pairwise intersection:

$E\cap P$ only: $24-15=9$; $E\cap T$ only: $33-15=18$; $P\cap T$ only: $19-15=4$.

Then each group alone: $E$ alone $52-9-18-15=10$; $P$ alone $31-9-4-15=3$; $T$ alone $45-18-4-15=8$.

Exactly one group: $10+3+8=21$ stations.

Check: $10+3+8+9+18+4+15=67$, the result of b).

Exactly two groups: $9+18+4=31$ stations. The 80 stations are equally likely, so $P=\dfrac{31}{80}=0.3875$.

Pitfall: taking $24+33+19=76$ stations. These three intersections all contain the 15 stations of the center, which have THREE groups.

In the sum $|E|+|P|+|T|$, a station is counted once for each set that contains it.

The 21 stations with one group count 1 time, the 31 with two groups 2 times, the 15 with three groups 3 times, the 13 with no group 0 times:

$21\times 1+31\times 2+15\times 3=21+62+45=128$.

The total 128 is therefore not a number of stations, and it has no reason to be less than 80: the data are consistent.

Each inner number of row 7 is the sum of the two numbers just above it in row 6, and each row starts and ends with $1$:

$1$; $1+6=7$; $6+15=21$; $15+20=35$; $20+15=35$; $15+6=21$; $6+1=7$; $1$.

So $\binom{7}{3}=\binom{6}{2}+\binom{6}{3}=15+20=35$, which $\dfrac{7\times 6\times 5}{3!}=35$ confirms.

The row reads the same in both directions: that is the symmetry $\binom{n}{k}=\binom{n}{n-k}$, a free check.

Row 4 is $1,\ 4,\ 6,\ 4,\ 1$:

$(a+b)^{4}=a^{4}+4a^{3}b+6a^{2}b^{2}+4ab^{3}+b^{4}$.

The coefficient of $a^{2}b^{2}$ is $\binom{4}{2}=6$: among the 4 factors $(a+b)$, choose the 2 that supply $b$.

Apply the binomial theorem with $a=2x$ and $b=-1$. The general term is $\binom{5}{k}(2x)^{5-k}(-1)^{k}$.

$x^{3}$ appears for $5-k=3$, that is $k=2$: $\binom{5}{2}(2x)^{3}(-1)^{2}=10\times 8x^{3}\times 1=80x^{3}$.

The coefficient is $80$.

Pitfall: answering $\binom{5}{2}=10$ and forgetting that the $2$ is raised to the power along with $x$: $(2x)^{3}=8x^{3}$, not $2x^{3}$.

$x^{2}$ appears for $5-k=2$, that is $k=3$: $\binom{5}{3}(2x)^{2}(-1)^{3}=10\times 4x^{2}\times(-1)=-40x^{2}$.

The coefficient is $-40$.

Pitfall: losing the sign. The $-1$ is part of the binomial term, and $(-1)^{k}$ is negative for odd $k$.

The general term is $\binom{6}{k}\left(x^{2}\right)^{6-k}\left(\dfrac{3}{x}\right)^{k}=\binom{6}{k}\,3^{k}\,x^{12-2k-k}=\binom{6}{k}\,3^{k}\,x^{12-3k}$.

It is independent of $x$ when $12-3k=0$, that is $k=4$: $\binom{6}{4}\times 3^{4}=15\times 81=1215$.

Check that $k=4$ is indeed an integer between $0$ and $6$; otherwise, the expansion would have no constant term.

With $a=b=1$: $\sum_{k=0}^{7}\binom{7}{k}=(1+1)^{7}=2^{7}=128$.

With $a=1$ and $b=-1$: $\sum_{k=0}^{7}\binom{7}{k}(-1)^{k}=(1-1)^{7}=0$.

Check on the row: $1+7+21+35+35+21+7+1=128$, and $1-7+21-35+35-21+7-1=0$.

The first three terms give $1+0.2+0.018=1.218$. The calculator gives $(1.02)^{10}\approx 1.21899$, that is $1.219$ to the nearest thousandth.

The difference comes mostly from the fourth term, $\binom{10}{3}0.02^{3}=120\times 0.000008\approx 0.00096$: the following terms quickly become negligible because $0.02$ is small.

Pitfall: the “simple” growth $1+10\times 0.02=1.2$ forgets the compounding, the $\binom{10}{2}$ term: the population grows by nearly $22\,\%$, not $20\,\%$.

Each spin has 2 orientations, independently of the others: $2^{6}=64$ configurations.

A configuration with 2 spins up is determined by the POSITIONS of these 2 spins, chosen out of 6, without order: $\binom{6}{2}=15$. Its magnetization is $M=2\times 2-6=-2$.

Pitfall: $P(6,\,2)=30$. Choosing “position 1 then position 4” or “position 4 then position 1” gives the same configuration.

A configuration with $k$ spins up is completely determined by the set of positions of its up spins, and that set can be any $k$-element subset of $\{1,\dots,n\}$. There are therefore $\binom{n}{k}$ such configurations.

Having exactly $k$ spins up means having exactly $n-k$ spins down: the two families are the SAME family, described by its up spins or by its down spins.

Counting this family by the positions of the down spins gives $\binom{n}{n-k}$. The same set counted in two ways gives the same number: $\binom{n}{k}=\binom{n}{n-k}$.

This is a proof by double counting: no calculation, only a one-to-one correspondence.

Let $1\le k\le n-1$. The configurations with $k$ spins up split into two families, according to the last spin.

Last spin up: the first $n-1$ spins carry exactly $k-1$ spins up, giving $\binom{n-1}{k-1}$ configurations.