Counting models

When every outcome of an experiment is equally likely but there are far too many to list, how is a probability found by counting, and which outcomes really are equally likely?

Where you are 4 in Foundations

Why this exists

Result 7 of Probability axioms and sample spaces turns a finite sample space whose outcomes all have the same probability into the formula P(A)=|A|/|\Omega|. The formula is only as useful as the counting behind it. A mahjong set without flower tiles has 136 tiles, and a hand of 13 tiles can be dealt from it in \binom{136}{13}\approx 4.84\times 10^{17} ways. Nobody lists those hands. To find the chance that a hand holds all three dragons, one counts instead: multiplying choices, dividing out orders that do not matter, and correcting for overlaps.

Counting also forces a modeling question the formula hides: which outcomes are equally likely? Four tiles that look identical are still four tiles, and a record that forgets which copy was drawn, or in what order, can merge equally likely outcomes in unequal numbers. This lesson sets up the equally likely model, the counts it needs, and inclusion-exclusion for any finite number of events.

Definition

A uniform model, also called the classical model, is a finite sample space \Omega in which every outcome has the same probability, P(\{\omega\})=1/|\Omega|. By Result 7 of Probability axioms and sample spaces, every event A then has

P(A)=\frac{|A|}{|\Omega|},

where |A| is the number of outcomes in A. Equal likelihood is an assumption about the physical experiment, justified by symmetry: a shuffle that favors no order, a draw that favors no item. A counting model is a uniform model together with the counts that evaluate |A| and |\Omega|.

Most counting models come from sampling: k items drawn one at a time from n distinguishable items. There are four ways to sample and record.

order keptorder forgotten
with replacementsequences, n^kmultisets, \binom{n+k-1}{k}
without replacementsequences of distinct items, (n)_ksubsets, \binom{n}{k}

Here (n)_k=n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!} is the falling factorial, the count of permutations; \binom{n}{k}=\dfrac{n!}{k!\,(n-k)!} is the combination count; and the multiset count is derived in Combinations with repetition: stars and bars. When the draws are uniformly random, three of the four cells are uniform models. The multiset cell is not (Boundaries).

The multinomial coefficient, for nonnegative integers with k_1+\dots+k_r=n, is

\binom{n}{k_1,\,k_2,\,\dots,\,k_r}=\frac{n!}{k_1!\,k_2!\cdots k_r!}.

It counts the ways to split n distinguishable items into r labeled groups of sizes k_1,\dots,k_r. With r=2 it is \binom{n}{k_1}.

The set used throughout has three suits (bamboo, characters, dots) with ranks 1 to 9, four identical copies of each, for 108 suit tiles; and four winds (east, south, west, north) and three dragons (red, green, white), four copies each, for 16 wind tiles and 12 dragon tiles, 28 honor tiles in all. That is 34 kinds, four copies of each. The deal used here is a simplified model, not the rules of any one game: each of four players receives 13 tiles and the other 84 stay in the wall. The tiles are shuffled so that every order of the 136 is equally likely, and identical copies are treated as distinguishable, as if each carried an invisible serial number. The shuffle cannot see the serial numbers, so labeling changes no probability; it is what makes the outcomes equally likely.

Intuition

In a uniform model, P(A) is the share of all equally likely shuffles in which A happens. Any coarser description of a shuffle is safe provided every description is shared by the same number of shuffles. Recording a hand as a set forgets the order in which its tiles arrived, and every set of 13 tiles arrives in exactly 13! orders, so sets are equally likely and the ratio of counts is the same in both records (Result 3). Recording only kinds is not safe: a hand’s east-wind part reads “four east winds” for one choice of tiles, but “one east wind” for four choices. Count labeled tiles first, then read off whatever the event is about.

Inclusion-exclusion is the bookkeeping for overlaps. Adding the probabilities that a hand lacks the red dragon and that it lacks the green one counts twice every hand that lacks both. Subtracting the pairs, adding back the triples and so on leaves each outcome counted exactly once.

Results

Result 1 (multiplication principle, as in The fundamental counting principle). Suppose each outcome is built in k stages, with n_1 choices at the first stage and, whatever was chosen earlier, n_i choices at stage i, and that different sequences of choices give different outcomes. Then there are n_1n_2\cdots n_k outcomes.

Result 2 (sampling counts). From n distinguishable items there are n^k ordered samples of size k with replacement, (n)_k without replacement, and \binom{n}{k}=(n)_k/k! subsets of size k.

Result 3 (order can be forgotten). Draw k of n distinguishable items one at a time without replacement, with all (n)_k sequences equally likely. Then the set of items drawn is equally likely to be each of the \binom{n}{k} subsets, and any event that depends only on that set has the same probability in either model.

Result 4 (multinomial count). The number of ways to split n distinguishable items into labeled groups of sizes k_1,\dots,k_r is \binom{n}{k_1,\,\dots,\,k_r}.

Result 5 (marked items, as in Probability with counting formulas). Of N items, K are marked, and a subset of size n is chosen uniformly. For 0\le k\le n,

P(\text{exactly }k\text{ marked})=\frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}},

with \binom{a}{b}=0 when b<0 or b>a.

Result 6 (inclusion-exclusion). Let A_1,\dots,A_n be events in any probability space and

S_j=\sum_{i_1<i_2<\cdots<i_j}P(A_{i_1}\cap\cdots\cap A_{i_j}).

Then

\begin{aligned} P(A_1\cup\cdots\cup A_n)&=S_1-S_2+S_3-\cdots\\ &\quad+(-1)^{n+1}S_n, \end{aligned}

and so the probability that none occurs is 1-S_1+S_2-\cdots+(-1)^nS_n. For n=2 this is the addition rule (Result 5 of Probability axioms and sample spaces, and Venn diagrams and counting a union); the counting version for many sets is Inclusion-exclusion for three or more sets, and derangements.

Why it is true

Result 1. By induction on k; one stage is clear. If the first k-1 stages give n_1\cdots n_{k-1} partial outcomes, each extends in n_k ways, and extensions of different partial outcomes differ, so there are (n_1\cdots n_{k-1})\,n_k outcomes.

Result 2. With replacement each of the k stages has n choices. Without replacement stage i has n-(i-1) choices whatever came before, giving (n)_k. For subsets, let c be their number and build each ordered sample in two stages: choose its set (c ways), then order the set (k! ways, by Result 1). Every ordered sample arises exactly once, so (n)_k=c\cdot k!.

Result 3. Fix a subset B of size k. The sequences whose items form B are the k! orderings of B, so the set drawn equals B with probability k!/(n)_k=1/\binom{n}{k}, the same for every B. An event that depends only on the set is a union of such disjoint events, so its probability is (number of subsets in it)/\binom{n}{k} in both models.

Result 4. Put the n items in a row (n! ways) and give the first k_1 to group 1, the next k_2 to group 2, and so on. Every split arises, and a given split arises from exactly k_1!\cdots k_r! rows, since reordering inside each group (Result 1) changes the row but not the split. So there are n!/(k_1!\cdots k_r!) splits.

Result 5. Here |\Omega|=\binom{N}{n}. A subset with exactly k marked items is built by choosing k of the K marked items and n-k of the N-K unmarked ones, and different choices give different subsets, so Result 1 gives the numerator. When k>K or n-k>N-K there is no such subset, which the convention records.

Result 6. The events cut \Omega into at most 2^n disjoint pieces, one for each way of saying, for every i, whether A_i occurs; Figure 1 of Probability axioms and sample spaces shows the four pieces when n=2. The union and every intersection A_{i_1}\cap\cdots\cap A_{i_j} are disjoint unions of pieces, so by finite additivity both sides of the formula are sums of piece probabilities, and it suffices to show each piece is counted equally often on both sides. Take a piece on which exactly m of the events occur. If m=0 it lies in no A_i and appears on neither side. If m\ge 1 it appears once on the left. On the right it lies in A_{i_1}\cap\cdots\cap A_{i_j} exactly when all j indices are among its m events, so it appears \binom{m}{j} times in S_j, and its total coefficient is, by the binomial theorem,

\begin{aligned} \sum_{j=1}^{m}(-1)^{j+1}\binom{m}{j}&=1-\sum_{j=0}^{m}(-1)^j\binom{m}{j}\\ &=1-(1-1)^m=1. \end{aligned}

Worked examples

Example 1

A pair from the first two tiles

Hiro turns over the first two tiles of a shuffled set. Find the probability that they are the same kind of tile, once with order kept and once with order forgotten.

Solution

With order kept, \Omega is the set of ordered pairs of different tiles, and |\Omega|=(136)_2=136\cdot 135=18{,}360 by Result 2. A matching pair is built in two stages: any first tile (136 ways), then one of the 3 other copies of its kind. So P=\dfrac{136\cdot 3}{18{,}360}=\dfrac{408}{18{,}360}=\tfrac{1}{45}.

With order forgotten, \Omega is the set of 2-tile subsets, \binom{136}{2}=9180 of them. A matching subset is a kind (34 ways) and two of its four copies (\binom{4}{2}=6 ways), so P=\dfrac{204}{9180}=\tfrac{1}{45}. The answers agree because of Result 3: each subset comes from 2 ordered pairs, so both counts halve. A check: whatever the first tile, the second is equally likely to be any of the other 135, and 3 of them match, giving \tfrac{3}{135}=\tfrac{1}{45}.

Example 2

Repeated kinds with replacement

Yuna draws a tile, notes its kind, returns it and reshuffles, k times. Find the probability p_k that all k kinds are different, and the smallest k for which a repeated kind is more likely than not.

Solution

Take \Omega to be the ordered k-tuples of labeled tiles, 136^k equally likely outcomes by Result 2. For all kinds to differ, draw i must avoid the 4(i-1) tiles of the kinds already seen, leaving 136-4(i-1) choices whatever those kinds were. By Result 1,

\begin{aligned} p_k&=\frac{136\cdot 132\cdots(136-4k+4)}{136^k}\\ &=\frac{4^k\,(34)_k}{4^k\,34^k}=\frac{(34)_k}{34^k}. \end{aligned}

This is the answer for drawing kinds uniformly from 34, which is legitimate here because every kind has the same number of copies. Since p_{k+1}/p_k=(34-k)/34<1, the probability of a repeat, 1-p_k, grows with k. Multiplying out, p_7\approx 0.5162 and p_8\approx 0.4099, so a repeat has probability about 0.4838 after 7 draws and 0.5901 after 8. The smallest k is 8, as Figure 1 shows.

This is the birthday problem with 34 kinds in place of 365 days. The inequality 1-x\le e^{-x} gives p_k\le \exp\!\big(-(1+2+\cdots+(k-1))/34\big), which equals e^{-k(k-1)/68}, so a repeat is more likely than not once k(k-1)>68\ln 2\approx 47.1: a number of draws on the order of \displaystyle \sqrt{34}, far fewer than 34.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0.25 0.50 0.75 1.00
P(\text{repeat})
k
Figure 1The probability that some kind repeats among k draws with replacement from 34 equally likely kinds, 1-(34)_k/34^k. It first passes \tfrac{1}{2} at k=8.
Example 3

Honor tiles in a dealt hand

Yuna is dealt 13 tiles. Find the probability that exactly 3 of them are honor tiles, and the probability that none are.

Solution

Whichever 13 positions of the shuffled row the deal gives her, the tiles there arrive as an ordered sample without replacement, so by Result 3 her hand is a uniform 13-tile subset of the 136. Mark the 28 honor tiles and apply Result 5 with N=136, K=28, n=13:

\begin{aligned} P(\text{exactly }3)&=\frac{\binom{28}{3}\binom{108}{10}}{\binom{136}{13}}\approx 0.2622,\\ P(\text{none})&=\frac{\binom{108}{13}}{\binom{136}{13}}\approx 0.0426. \end{aligned}

Here \binom{28}{3}=3276 counts the honor part and \binom{108}{10} the suit part. By the complement rule, her hand holds at least one honor tile with probability about 0.9574.

Example 4

Where the red dragons go

After the deal, find the probability that each of the four players holds exactly one red dragon.

Solution

First with the whole deal as the outcome. A deal is a split of the 136 labeled tiles into five labeled groups of sizes 13,13,13,13,84, and by the proof of Result 4 each split comes from the same number (13!)^4\,84! of orders of the row, so splits are equally likely, \binom{136}{13,\,13,\,13,\,13,\,84} of them. A favorable deal hands the four red dragons one to each player (4! ways) and then splits the other 132 tiles into groups of sizes 12,12,12,12,84. The probability is

\begin{aligned} P&=\frac{4!\;\dfrac{132!}{(12!)^4\,84!}}{\dfrac{136!}{(13!)^4\,84!}}\\ &=\frac{24\cdot 13^4}{136\cdot 135\cdot 134\cdot 133}\\ &=\frac{28{,}561}{13{,}633{,}830}\approx 0.002095. \end{aligned}

A smaller model gives the same answer with less work. The event depends only on where the four red dragons lie, and by Result 3 their set of positions is uniform among \binom{136}{4}=13{,}633{,}830 sets. A favorable set has one position in each player’s 13, so there are 13^4=28{,}561 of them. The best sample space is the smallest one that is still uniform and still decides the event.

Example 5

All three dragons in one hand

Find the probability that Yuna’s 13 tiles include at least one red, one green and one white dragon.

Solution

Let R, G, W be the events that her hand has no red, no green, no white dragon. The event wanted is the complement of R\cup G\cup W. A hand in R is a 13-subset of the 132 other tiles, so P(R)=\binom{132}{13}/\binom{136}{13}\approx 0.6659, and the same holds for G and W. A hand in R\cap G avoids 8 tiles, and one in R\cap G\cap W avoids 12. With T=\binom{136}{13}, Result 6 gives

\begin{aligned} P(R\cup G\cup W)&=S_1-S_2+S_3\\ &=\frac{3\binom{132}{13}-3\binom{128}{13}+\binom{124}{13}}{T}\\ &\approx 1.99767-1.31286+0.28360\\ &=0.96841. \end{aligned}

So all three dragons appear with probability about 0.0316. The first sum S_1 exceeds 1: the three events overlap heavily, and the corrections are comparable in size to the first term.

Example 6

No tile in its own place

Hiro shuffles the nine bamboo tiles of ranks 1 to 9, one of each, and lays them face down in positions 1 to 9. Position i is a match if the tile of rank i lands there. Find the probability of no match, then the same for n tiles and its limit as n grows.

Solution

Take \Omega to be the 9! orders and let A_i be a match at position i. If j given positions must match, those tiles are fixed and the other 9-j go in any order, so P(A_{i_1}\cap\cdots\cap A_{i_j})=(9-j)!/9!. There are \binom{9}{j} choices of positions, so

S_j=\binom{9}{j}\frac{(9-j)!}{9!}=\frac{1}{j!}.

By Result 6, P(\text{no match})=\sum_{j=0}^{9}\dfrac{(-1)^j}{j!}=\dfrac{16{,}687}{45{,}360}\approx 0.367879. The same argument with n tiles gives q_n=\sum_{j=0}^{n}(-1)^j/j!, a partial sum of the Maclaurin series e^x=\sum_{j\ge 0}x^j/j! at x=-1 (Taylor and Maclaurin series). That series converges for every x, so q_n tends to e^{-1}\approx 0.367879 as n grows; for n=9 the two differ by about 2.5\times 10^{-7}. The count 9!\,q_9=133{,}496 is the number of derangements of Inclusion-exclusion for three or more sets, and derangements.

Example 7

Vandermonde’s identity from probability

Prove that for integers 0\le K\le N and 0\le n\le N,

\sum_{k=0}^{n}\binom{K}{k}\binom{N-K}{n-k}=\binom{N}{n}.
Solution

Mark K of N items and choose a subset of size n uniformly. Let E_k be the event that exactly k chosen items are marked, k=0,1,\dots,n. Every subset has some number of marked items between 0 and n, and only one, so the E_k are pairwise disjoint with union \Omega. By finite additivity and P(\Omega)=1, \sum_k P(E_k)=1. Substituting Result 5 and multiplying by \binom{N}{n} gives the identity; terms with k>K or n-k>N-K are 0 on both readings. As a check with N=7, K=4, n=3: 1+12+18+4=35=\binom{7}{3}.

Boundaries

Equal likelihood is assumed, not derived. The counts give probabilities only after a symmetry argument for the model. If the tiles are not shuffled, for instance if the wall keeps the previous hand’s tiles together, no count describes the deal.

Records that merge outcomes unequally are not uniform. Two draws with replacement recorded as an unordered pair of kinds have \binom{35}{2}=595 possible records, but two east winds has probability \tfrac{1}{1156} while an east and a south wind has \tfrac{2}{1156}. Combinations with repetition: stars and bars counts the multisets correctly; they are simply not equally likely. Likewise a hand recorded by kinds is not uniform over the possible kind records.

A uniform model needs a finite sample space. No probability gives every positive integer the same value (Exercise 17 of Probability axioms and sample spaces), and a uniform point of an interval is modeled by length, not by counting.

Inclusion-exclusion is a finite identity. Result 6 is stated for finitely many events. Stopping after an odd number of terms gives an upper bound for the union and stopping after an even number gives a lower bound (the Bonferroni inequalities). Exercise 17 proves the first two; the general case is stated here without proof, and it follows from the same piece count once one knows that \sum_{j=0}^{t}(-1)^j\binom{m}{j}=(-1)^t\binom{m-1}{t} for m\ge 1.

Where this goes next

In a uniform model, conditioning on B restricts the count, P(A\mid B)=|A\cap B|/|B|; Conditioning and Bayes' rule, rigorously develops conditioning in general (school version Finding a conditional probability). Result 5 is the probability mass function of the hypergeometric distribution, and counting the \binom{n}{k} arrangements of successes among draws with replacement gives the binomial one, both in Discrete distributions: binomial, geometric, Poisson. Draws with replacement, as in the second example, are independent and draws without replacement are not, a contrast made precise in Independence of events and variables. The matching problem returns as a random variable, the number of matches, whose expected value is 1 for every n, a fact stated here and proved in Expectation, linearity and indicators.

Exercises

Choosing the sample space

  1. Find the probability that the first two tiles of a shuffled set are both wind tiles.
  2. Find the probability that the first three tiles are all dots, and the probability that they are all from one suit.
  3. Find the probability that the first tile turned over is a dragon and the second is a wind.
  4. Hiro draws a tile, returns it and reshuffles, 5 times. Find the probability that all five are suit tiles, and the probability that at least one is an honor tile.
  5. Yuna makes 3 draws with replacement and records only the unordered list of kinds, so there are \binom{36}{3}=7140 possible records. Find the probability of the records {east, east, south} and {east, south, west}, and compare each with \tfrac{1}{7140}.

Hands and deals

  1. Find the probability that a 13-tile hand contains no wind tile.
  2. Find the probability that a 13-tile hand contains exactly 2 wind tiles.
  3. Find the probability that a 13-tile hand contains all four east winds.
  4. Find the probability that a 13-tile hand has every tile from one suit.
  5. After the deal, find the probability that all four white dragons are held by one player, and the probability that all four are still in the wall.
  6. The nine bamboo tiles of ranks 1 to 9, one of each, are shuffled and split into 3 for Hiro, 3 for Yuna and 3 left on the table. How many splits are there? Find the probability that Hiro’s three ranks are consecutive.

Inclusion-exclusion and matching

  1. Hiro shuffles the 16 wind tiles alone and draws 6. Find the probability that he has at least one of each of the four winds.
  2. Find the probability that a 13-tile hand is missing at least one of the three suits.
  3. The six dots tiles of ranks 1 to 6, one of each, are laid in a random order in positions 1 to 6. Find the probability of exactly two matches, and of none.
  4. Yuna draws with replacement from the 36 bamboo tiles and notes only the rank. Find the smallest number of draws for which a repeated rank is more likely than not, and its probability.

Proofs

  1. Draw k of n distinguishable items one at a time without replacement, all (n)_k sequences equally likely. Prove that for every j\le k and every item t, the probability that draw j is t equals \tfrac{1}{n}.
  2. With S_j as in Result 6, prove S_1-S_2\le P(A_1\cup\cdots\cup A_n)\le S_1.
  3. With q_n=\sum_{j=0}^{n}(-1)^j/j!, prove \left|q_n-e^{-1}\right|\le\dfrac{1}{(n+1)!}.
  4. Prove that the sum of \binom{n}{k_1,\,\dots,\,k_r} over all nonnegative integers with k_1+\dots+k_r=n equals r^n.
Answers
  1. \tfrac{2}{153}\approx 0.0131. As an unordered pair (Result 3), \binom{16}{2}/\binom{136}{2}=120/9180.
  2. \tfrac{7}{402}\approx 0.0174 and \tfrac{7}{134}\approx 0.0522. There are 36 dots tiles, so \binom{36}{3}/\binom{136}{3}=7140/410{,}040; the three one-suit events are disjoint and equally likely, so triple it.
  3. \tfrac{8}{765}\approx 0.0105. Order matters: \dfrac{12\cdot 16}{136\cdot 135}=\dfrac{192}{18{,}360}.
  4. (27/34)^5\approx 0.3158 and about 0.6842. Each of the 136^5 sequences is equally likely and 108^5 use only suit tiles; 108/136=27/34. The second is the complement.
  5. \tfrac{3}{39{,}304} and \tfrac{6}{39{,}304}, against \tfrac{1}{7140}. Each ordered triple of kinds has probability (4/136)^3=1/34^3=1/39{,}304. The first record comes from 3 orders (where the south wind falls) and the second from 3!=6, so the first is below \tfrac{1}{7140}\approx\tfrac{5.5}{39{,}304} and the second above it.
  6. \binom{120}{13}/\binom{136}{13}\approx 0.1810. The hand is a 13-subset of the 120 tiles that are not winds.
  7. \binom{16}{2}\binom{120}{11}/\binom{136}{13}\approx 0.2879, by Result 5 with K=16.
  8. \tfrac{143}{2{,}726{,}766}\approx 5.24\times 10^{-5}. The hand is the four east winds and 9 of the other 132: \binom{132}{9}/\binom{136}{13}=\dfrac{13\cdot 12\cdot 11\cdot 10}{136\cdot 135\cdot 134\cdot 133}.
  9. 3\binom{36}{13}/\binom{136}{13}\approx 1.43\times 10^{-8}. Each suit has 36 tiles and the three events are disjoint.
  10. About 2.10\times 10^{-4} and 0.1415. The positions of the white dragons are a uniform 4-subset of 136. One player: 4\binom{13}{4}/\binom{136}{4}=2860/13{,}633{,}830=\tfrac{286}{1{,}363{,}383}. The wall: \binom{84}{4}/\binom{136}{4}=\tfrac{30{,}627}{216{,}410}.
  11. 1680 splits and \tfrac{1}{12}. Result 4 gives \dfrac{9!}{3!\,3!\,3!}=1680. Hiro’s set is uniform among \binom{9}{3}=84 (Result 3), and 7 of them are consecutive, \{1,2,3\} to \{7,8,9\}: \tfrac{7}{84}.
  12. \tfrac{80}{143}\approx 0.559. Let A_i be “no wind of kind i”. Then S_1=4\binom{12}{6}/\binom{16}{6}=3696/8008, S_2=6\binom{8}{6}/8008=168/8008, and S_3=S_4=0 since 6 tiles cannot avoid 12. The union has probability 3528/8008=\tfrac{63}{143}; subtract from 1.
  13. About 0.04401. Missing one given suit leaves 100 tiles, two suits 64, all three the 28 honors: \dfrac{3\binom{100}{13}-3\binom{64}{13}+\binom{28}{13}}{\binom{136}{13}}, about 0.044094-0.000081 plus a last term below 10^{-10}.
  14. \tfrac{3}{16} and \tfrac{53}{144}\approx 0.368. Choose the 2 matches (\binom{6}{2}=15 ways); the other 4 tiles must have no match, which by the sixth example’s formula happens in 4!\left(1-1+\tfrac12-\tfrac16+\tfrac1{24}\right)=9 orders: 15\cdot 9/720. None: 6!\,q_6=265, and 265/720=\tfrac{53}{144}.
  15. 4 draws, with probability \tfrac{131}{243}\approx 0.539. Each rank has 4 copies, so ranks are uniform over 9 as in the second example: 1-\dfrac{9\cdot 8\cdot 7\cdot 6}{9^4}=1-\dfrac{3024}{6561}. With 3 draws it is 1-\tfrac{504}{729}=\tfrac{25}{81}<\tfrac12.
  16. Sequences with t at draw j: place t there, then fill the other k-1 draws in order from the remaining n-1 items, (n-1)_{k-1} ways by Result 1. Since (n)_k=n\,(n-1)_{k-1}, the probability is \tfrac{1}{n}.
  17. Use the pieces in the proof of Result 6. A piece on which exactly m\ge 1 events occur has coefficient 1 in the union, m in S_1, and m-\binom{m}{2}=\tfrac{m(3-m)}{2} in S_1-S_2. For every integer m\ge 1, \tfrac{m(3-m)}{2}\le 1\le m (m=1,2 give 1, and m\ge 3 gives at most 0). A piece with m=0 has coefficient 0 in all three. Multiply by the piece probabilities, which are nonnegative, and add.
  18. e^{-1}-q_n=\sum_{j>n}(-1)^j/j! is the tail of an alternating series whose terms 1/j! decrease to 0, since 1/(j+1)!=\tfrac{1}{j+1}\cdot\tfrac{1}{j!}. By the Alternating series and their error bound, the tail is at most its first term in absolute value, \tfrac{1}{(n+1)!}.
  19. Count the ways to give each of n items one of r labels: r^n by Result 1. Group the labelings by the sizes (k_1,\dots,k_r) of the label classes. A labeling with those sizes is exactly a split into labeled groups of those sizes, so there are \binom{n}{k_1,\,\dots,\,k_r} of them by Result 4. Each labeling has exactly one size vector, so the counts over all size vectors add to r^n. With r=2 this is \sum_k\binom{n}{k}=2^n.
math.wiki · CC-BY-SA-4.0