Combinatorics

Introduction to Probability

1c. Combinatorics

1. Sets and probabilities

One-to-one correspondence.
[Si] "Foundations" : Sect 4 "Counting measure" : Item "Definition and basic properties".
Addition rule. Inclusion-exclusion.
- [Si] "Foundations" : Sect 4 "Counting measure" : Items "The addition rule", "The inclusion-exclusion formula".
- [BT] Sect 1.2 "Probabilistic models" : Item "Properties of probability laws" (p. 14).
- [GS] : Sect 3.2 "Combinations" : Item "Inclusion-exclusion principle" (p. 104).
Symmetric tree diagrams. Multiplication rule.
- [Si] "Foundations" : Sect 4 "Counting measure" : Items "The multiplication rule".
- [BT] Sect 1.6 "Counting" : Item "The counting principle" (p. 44).
- [GS] : Sect 3.1 "Permutations" : Items "Counting problems", "A counting technique", "Tree diagrams".
Ordered samples with replacement, powers.
- [Si] "Foundations" : Sect 4 "Counting measure" : Items "Product sets", "Functions and bit strings".
- [BT] Sect 1.6 "Counting" : Item "The counting principle" (p. 44).
Ordered samples without replacement, permutations, factorials.
- [Si] "Foundations" : Sect 5 "Combinatorial structures" : Item "Permutations".
- [BT] Sect 1.6 "Counting" : Item "k-permutations" (p. 46).
- [GS] : Sect 3.1 "Permutations" : Items "Permutations" (p. 79).
Unordered samples without replacement, combinations, binomial coefficients. Pascal's triangle. Binomial theorem. Binomial distribution.
- [Si] "Foundations" : Sect 5 "Combinatorial structures" : Items "Combinations", "Samples".
- [BT] Sect 1.6 "Counting" : Item "Combinations" (p. 47); see also "Independent trials and the binomial probabilities" (p. 41-).
Unordered samples with replacement.
- [Si] "Foundations" : Sect 5 "Combinatorial structures" : Item "Unordered samples with replacement".
Partitions, multinomial coefficients, multinomial theorem.
- [Si] "Foundations" : Sect 5 "Combinatorial structures" : Item "Multinomial coefficients".
- [BT] Sect 1.6 "Counting" : Item "Partitions" (p. 48).

Back to syllabus