combinatorics
[cite:;refer to @discrete_kenneth_2018 chapter 6 counting]
some examples:
- [cite:;refer to @berger_inference_2002 example 1.2.18]
books
a walk through combinatorics seems to be recommended everywhere on the web (from what ive seen)
- homemahmoozbrainresources/Miklos Bona - A Walk Through Combinatorics_ An Introduction to Enumeration, Graph Theory, and Selected Other Topics-World Scientific Publishing Company (2023).pdf
- homemahmoozbrainresources/Kenneth Rosen - Discrete Mathematics and Its Applications-McGraw-Hill Higher Education (2018).pdf
- https://math.stackexchange.com/questions/1454339/undergrad-level-combinatorics-texts-easier-than-stanleys-enumerative-combinator
- kenneth's discrete maths
- homemahmoozbrainresources/[Texts in Theoretical Computer Science. An EATCS Series ] Stasys Jukna (auth.) - Extremal Combinatorics_ With Applications in Computer Science (2011, Springer) [10.1007_978-3-642-17364-6] - libgen.li.pdf
some combinatorics from college
combinatorics is the theory of enumeration, where we look at elements of a set as options
rule of sum
let $A,B$ be disjoint finite sets, then $|A \cup B| = |A| + |B|$
in other words, if the set $A$ had $n$ elements ($n$ options) and $B$ had $m$ elements ($m$ options) such that $A \cap B = \varnothing$ then there exist $n+m$ total options to pick from $A \cup B$
let $A,B$ be disjoint finite sets, then $|A \cup B| = |A| + |B|$
in other words, if the set $A$ had $n$ elements ($n$ options) and $B$ had $m$ elements ($m$ options) such that $A \cap B = \varnothing$ then there exist $n+m$ total options to pick from $A \cup B$
if $A,B$ are finite sets such that $A \subseteq B$, then $|B\textbackslash A| = |B|-|A|$
if a nest had 5 red eggs numbered 1-5 and 3 blue eggs numbered 1-3, how many options do we have if we wanted to pick a single egg?
the answer is $5+3=8$ because the eggs differ
the answer is $5+3=8$ because the eggs differ
we use the rule of sum when we encounter the word or
rule of product
if $A,B$ be finite sets, then $|A \times B| = |A| \cdot |B|$
in other words, if $A$ had $n$ elements and $B$ had $m$ elements, then there exist $n \cdot m$ options to pick a pair from $A \times B$
if $A,B$ be finite sets, then $|A \times B| = |A| \cdot |B|$
in other words, if $A$ had $n$ elements and $B$ had $m$ elements, then there exist $n \cdot m$ options to pick a pair from $A \times B$
let $A,B$ be finite sets such that $R \subseteq A \times B$
- if there exists a natural number $s$ such that $(\forall a \in A)(\exists b \in B)[|\{(a,b) \in \mathbb{R}\}|=s]$ then $|R| = |A| \cdot s$
- if there exists a natural number $t$ such that $(\forall b \in B)(\exists a \in A)[|\{(a,b) \in \mathbb{R}\}|=t]$ then $|R| = t \cdot |B|$
extended rule of sum
let $A_1,A_2\ldots A_n$ be disjoint finite sets, then $\left|\cup_{i=1}^nA_i\right| = \sum_{i=1}^n|A_i|$
let $A_1,A_2\ldots A_n$ be disjoint finite sets, then $\left|\cup_{i=1}^nA_i\right| = \sum_{i=1}^n|A_i|$
for every 2 finite sets $A,B$, $|A\cup B| = |A|+|B|-|A\cap B|$
extended rule of product
let $A_1,A_2\ldots A_n$ be finite sets, then $|A_1\times A_2\times \cdots A_n|=\prod_{i=1}^n|A_i|$
let $A_1,A_2\ldots A_n$ be finite sets, then $|A_1\times A_2\times \cdots A_n|=\prod_{i=1}^n|A_i|$
for every 2 finite sets $A,B$, $|A\cup B| = |A|+|B|-|A\cap B|$
selection
this refers to selecting an option from a given set of options
order
we say the order of selection matters when the position of the option we pick in the given set of options has an affect on the total number of possible selections, conversely we say the order doesnt matter when it doesnt have such an affect
when the order doesnt matter, the permutations
ABC and BCA of the letters A,B,C is considered the same permutation, because the order doesnt matterrepetition
whether the the process of selection allows selecting a specific item multiple times which means the result would be a multiset
euler's identity
derangement
a permutation of $n$ numbers $1,2,\ldots,n$ is called a derangement if all numbers arent in their right positions
$1 2 3 4 5 6 \to 2 3 4 5 6 1$ is a derangement
pascal's rule
let $n,k \in \mathbb{N}$ such that $0 \leq k \leq n$, then:
pascal's triangle
using pascal's rule we can find a triangle called pascal's triangle which is a tool to find the binomial coefficients in an easy recursive way
- the root of the triangle has the bionimal coefficient $\binom00=1$
- in every row other than the first the leftmost node is a bionimal coefficient $\binom{n}{0}=1$
- the rightmost node is the bionimal coefficient $\binom{n}{n}$
- every other node in the triangle is the sum of both coefficients of row above it
let $n,k \in \mathbb{N}$ such that $0 \leq k \leq n$, then:
let $n,k \in \mathbb{N}$ such that $0 \leq k \leq n$, then:
