combinatorics.theory.txt

                                  ┏━━━━━━━━━━━━━━━━━━━┓
                                  ┃   COMBINATORICS   ┃
                                  ┗━━━━━━━━━━━━━━━━━━━┛

Combination:
  - subset with unique elements
     - including 0 or all elements
     - insignificant positions
  - k-combination: when size k

K-permutation:
  - also named partial permutations
  - combination where positions are significant (tuples)

Permutation:
  - k-permutation with same size
  - f: S -> S that is:
     - bijective
     - with significant positions
  - symmetric group: set of all permutations of another set

Combinatorial principles:
  - any basic combinatorics rule
  - includes: rule of sum, rule of product

Rule of sum:
  - if sets are disjoint, |S| + |T| + ... = |S ∪ T ∪ ...|
  - i.e. choosing between either m elements and n elements = between m + n elements

Rule of product:
  - |S| * |T| * ... = |S * T * ...|
  - i.e. choosing between m elements, then n elements = between m * n elements
  - if k sets with same size: |S|^k

Falling factorials:
  - pronunced: n to the k falling
  - notation:
     - (n)ₖ
     - nᵏ̲
     - P(n,k)
     - ₙPₖ
  - number of k-permutations in a n-set
     - i.e. rule of product, with an ever decreasing set after each element selection
  - ∏(i=n-k;n) i
     - k∈ N
     - k <= n
  - special value:
     - P(0,k) = 1 (empty product)

Rising factorials:
  - also named Pochhammer symbol
  - pronunced: n to the k rising
  - notations:
     - n⁽ᵏ⁾
     - nᵏ̅
     - R(n,k) (in my docs)
  - R(n,k) is same as P(n+k-1, k)
     - P(n,k) is same as R(n-k+1,k)
  - ∏(i=n;n+k) i
     - k∈ N

Factorial:
  - noted n!
  - number of permutations in a n-set
  - same as P(n,n-1) or R(1,n)
  - formulas:
     - P(n,n-k)  = n!/k!
        - P(n,k) = n!/(n-k)!

Binomial coefficient:
  - pronunced "n choose k"
  - notation:
     - (n k) (stacked vertically)
     - (n¦k)
  - number of k-combinations in a n-set
  - P(n,k) / k!
     - where k∈ N and k <= n
     - reason: 1 k-combination <=> k! k-permutations
  - using rising factorials:
     - (n¦k)     = R(n-k+1,k)/k!
     - (n+k-1¦k) = R(n,k)/k!
  - using factorials:
     - (n¦k) = (n!/(n-k)!) / k!
     - (n¦k) = n!/((n-k)! * k!)
  - formulas:
     - (n¦k) = (n¦n-k)
        - reason: n!/((n-k)! * k!) = n!/(k! * (n-k)!)
     - (n+1¦k+1) = (n¦k) + (n¦k+1)

Partial multinomial coefficient:
  - notation:
     - (n k₁,...) (stacked vertically)
     - (n¦k₁,...)
  - number of combinations of k-combinations in a n-set
     - k₁,... is the size of each k-combination
     - where ∑kᵢ <= n
  - generalization of binomial coefficient
  - ∏ (mᵢ¦kᵢ)
     - where mᵢ = {n, n-k₁, n-k₁-k₂,...}
  - <=> n! / ((n-∑kᵢ)! * ∏ kᵢ!)
     - reason:
        - (mᵢ¦kᵢ)
            <=> mᵢ! / (mᵢ-kᵢ)! / kᵢ!
            <=> mᵢ! / mᵢ₊₁! / kᵢ!
        - each coefficient's mᵢ! cancels previous coefficient's mᵢ₊₁!
        - only leaves m₀!, last mᵢ₊₁! and ∏ kᵢ!
  - total multinomial:
     - when ∑kᵢ = n
     - <=> n! / ∏ kᵢ!

Binomial theorem:
  - (a + b)^n = ∑(k=0;n) (n¦k) * a^(n-k) * b^k
  - ex :
    - (a + b)^3 = a^3 + 3a^2*b + 3a*b^2   + b^3
    - (a + b)^4 = a^4 + 4a^3*b + 6a^2*b^2  + 4a*b^3 + b^4
    - (a + b)^5 = a^5 + 5a^4*b + 10a^3*b^2 + 10a^2*b^3 + 5a*b^4 + b^5

Pascal triangle:
  - visualization of binomial theorem
  - n = row number, et k = element number (indexs commencent à 0)
     ⁰       1
     ¹      1 1
     ²     1 2 1
     ³    1 3 3 1
     ⁴   1 4 6 4 1
           etc.
  - (a - b)^n : pareil sauf que - au lieu de b dans les termes ayant un b^n où n est impair

Binomial theorem:
  - (n¦k) * p^n * (1-p)^(n-k)
    - parmi (n¦k) subsets de taille k, prob. de n succès p^n suivi de n-k échecs

Multinomial theorem:
  - (∑xᵢ)^n = ...

Multinomial distribution :
  - Si pop. contient k sous-groupes de proportions/prob. p₁,...,pₖ (∑pₖ = 1)
  - prob. qu'un sample de taille n contienne x₁ individus du groupe 1,... xₖ individus du groupe k suit Multinomial(n,p₁,...,pₖ)
  - distribution multivariate donc (x₁,...,xₖ)
  - = (n¦x₁,...,xₖ) * ∏pₖ^xₖ
  - Si n = 1, categorical dist. (équivalent multinomial de Bernoulli)
  - si sans remplacement -> multivariate hypergeometric dist.

Gamma function :
  - function permettant de simuler factorial pour R (et aussi complex numbers) et non seulement N
    - noté Γ(x), où Γ(x+1) = x!
    - x*Γ(x) = Γ(x+1)
    - P(x,n) = Γ(x+1)/Γ(x+1-n)
  - pour les nombres négatifs :
    - indéfini pour nombres entiers
    - négatif pour nombres pairs, positifs pour impairs
    - proche d'infini si proche d'un entier

Beta function :
  - B(x,y) = B(y,x) Γ(x)*Γ(y)/Γ(x+y)

Birthday paradox :
  - Si n events suivent Disc.Unif(1,k)
    - par ex. n personnes ayant même anniversaire (k = 365)
    - prob. qu'au moins deux events ait même valeur = 1 - P(k,n)/k^n
      - car par exemple pour anniversaire de 3 personnes :
        - 365 chances sur 365, puis 364 sur 365, puis 363 sur 365
        - donc 365/365 * 364/365 * 363/365 = P(365,n)/365^n, où n == 3
    - si n >= k, prob. == 1 (pigeonhole principle)
  - Birthday Distribution :
    - nb d'events avant que deux events coincident
    - Birthday(k)
    - pdf = P(k,x) / k^x * k/((k-x+1)-1)
    - cdf = 1 - P(k,x)/k^x
    - possible aussi d'avoir prob. qu'au moins m events coincident, et non seulement 2

Hypergeometric dist. :
  - avec amounts m et n :
    - pop.size m+n dont deux sous-groupes de taille m et n
    - prob. que sample de taille k ait x individus de ce groupe est :
        (m¦x) * (n¦k-x) / (n+m¦k)
    - raisons :
      - nombre de samples de taille k ayant x individus de ce groupe est (m¦x) * (n¦k-x)
        - raison :
          - on divise le sample en deux :
            - les x individus du groupe, ont (m¦x) combinaisons possibles
            - les k-x non-individus du groupe, ont (n¦k-x) combinaisons possibles
      - nombre de sample de taille k est (n+m¦k)
      - donc prob. est division des deux
    - suit Hypergeometric(m,n,k)
    - quand k == x :
      - premier essai, prob. est m/(m+n), second (m-1)/(m+n-1), etc. avec k essais, qui doivent tous être bons
      - soit P(m,k)/P(m+n,k)
  - avec probabilités :
    - ̅p  = m/(m+n)
    - p₁ = k/x
  - par rapport à Binomial dist. :
    - tous deux compte nb de succès de prendre individu d'un groupe de proportion p
    - mais Binomial est sans remplacement, p reste le même à chaque essai, tandis qu'Hypergeometric non
    - B(k,m/(m+n)) = Hypergeometric(m,n,k) :
      - approximation lorsque sample.size / pop.size (k/(m+n)) est petit (prendre un sample de taille k change très peu p)
      - approx. reste mauvaise pour les x avec une P(x) très faible, mais ce sont en général pas ceux qui intéressent
      - notamment utile si pop.size m+n est inconnue
      - pour k/(m+n) :
        - 1/50  : 99% d'approx.
        - 1/100 : 95% d'approx.

Logarithm scale :
  - factorial et dérivés (binomial coefficients, etc.) donnent des nombres très grands
  - il est donc parfois plus simple de les manipuler sous logarithm scale : ln(factorial()), puis à la fin ℮^(resultat)
  - avec les calculateurs comme R, cela permet de dépasser la limite des double floats