Combinatorics

Table of Contents

1. Binomial Coefficient

  • Combination

1.1. Definition

  • \[ \binom{\alpha}{k} := \frac{\alpha^{\underline{k}}}{k!} \]

1.2. Properties

1.2.1. Derivative

  • Using the logarithmic derivative, \[ \frac{d}{dx}\binom{x}{k} = \binom{x}{k}\sum_{r=0}^{k-1}\frac{1}{k-r}. \]

1.3. Binomial Theorem

1.3.1. Corollary

  • \[ \frac{1}{\displaystyle\sum_{k=0}^n\binom{n}{k}x^k} = \sum_{k=0}^\infty \binom{-n}{k}x^k. \]

1.4. Pascal's Triangle

1.4.1. Definition

  • It is numbers arranged in a triangular shape such that the sum of the two adjacent number is the number below the two.

1.4.2. Viks' Pyramid

Extension of the Pascal's triangle

2. Permutation

3. Combination with Repetition

  • Multicombination, Multisubset, 중복조합

Number of possible way of choosing \( k \) elements from \( n \) distinct elements allowing repetition. \[ \left(\!\!\binom{n}{k}\!\!\right) = \binom{n+k-1}{k} \]

The proof is given by the Stars and bars.

4. Combination of a Multiset

There is no general formula for it.

One possible way to express it is using the generating function. Given a multiset with \( n \) distinct element with \( m_r \) multiplicity for the \( r \)th distinct element, the number of possible way of choosing \( k \) elements is the coefficient of \( x^k \) in the following generating function: \[ f(x) = \prod_{r = 1}^n \left( \sum_{s = 0}^{m_r} x^s \right). \]

For example, the number of choosing \( 2 \) elements from multiset \( \{1,1,2,3 \} \) is the coefficient of \( x^2 \) in \[ (1+x+x^2)(1+x)(1+x) = 1 + 3x + 4x^2 + 3x^3 + x^4. \]

5. Permutation with Repetition

Number of arrangements of any of the \( n \) elements into a sequence of length \( k \) with repetition allowed. \[ | [n]^{[k]} | = n^k. \]

6. Circular Permutation

  • 원순열

Number of arrangements of \( n \) distinct elements into a circle where rotated arrangements are considered identical. \[ (n-1)! \]

7. Circular Permutation with Repetition

Number of arrangements of any of \( n \) elements into a circle of length \( k \), with repetition allowed, and rotation as the equivalence relation.

\[ \frac{1}{k} \sum_{l | k} \varphi(k/l) n^l \] where \( \varphi \) is the Euler's totient function.

Here, \( l \) represent the number of equivalence classes of positions within the circle under corresponding group elements \( g \in C_k \). The same number of equivalence classes are generated by \( \varphi(k/l) \) group elements, and there are \( n^l \) possibilities of assigning elements to each of those equivalence classes.

In particular, when \( k \) is prime, the formula reduces to \[ \frac{n^k - n}{k} + n \] which can be used to prove the Fermat's little theorem.

The use of \( \varphi \) can be understood by a table. For example, in \( C_6 \):

rotation by 2π/6 * i gcd(i, 6)      
1 1      
2   2    
3     3  
4   2    
5 1      
6 (=0)       6
#(group element) ϕ(6) ϕ(3) ϕ(2) ϕ(1)

So, the formula is counting the fixes for each group action, but in different way. Additionally, this procedure can be generalized: \[ \sum_{l = 1}^k f(\gcd(l,k)) = \sum_{l | k}\varphi(k/l) f(l). \]

See necklace polynomials for generalization.

8. Permutation of a Multiset

  • Permutation by Bins, Multinomial Coefficient
  • 같은 것이 있는 순열

\[ \begin{pmatrix} n\\ k_1, k_2,\dots , k_m\end{pmatrix} := \frac{n!}{k_1!k_2!\dots k_m!} \]

When \(\sum_i k_i \neq n\), it is defined to be 0.

9. Circular Permutation of a Multiset

Number of arrangements of any of size \( n \) multiset with \( p, q, r,\dots \) number of elements for each distinct elements, into a circle up to rotation, \[ \frac{1}{n}\sum_{l|\mathrm{gcd}(p, q, r, \dots)}\varphi(l)\frac{(n/l)!}{(p/l)!(q/l)!(r/l)!\cdots} \] where \(\varphi\) is the Euler's totient function.

Here, \( l \) represent the size of a equivalence class of positions within the circle under some \( g \in C_n\). The division by \( l \) is reflecting that each assignment to an equivalence class consumes \( l \) elements.

It is derived from Burnside's lemma, by noticing that it is the quotient set of all possible permutation of given multiset under the cyclic group \( C_n \). The summands counts the number of fixed elements by the rotation by the multiple of \(l\) units, excluding the overlapping rotations, which is naturally accounted in the \(\varphi(l)\) which counts the number of generators of \(C_l\).

The factorial part only counts the permutation within \(1/l\) of the entire sequence.

Quick note that it is obvious that \(l|\gcd(p,q,r) \implies l|n\) since \( n = p + q + r + \cdots. \)

10. Non-Consecutive Ordering

  • Permutation with no adjacent consecutive element

\[ \sum_{k=0}^{n-1}(-1)^k(n-k)!\sum_{r=1}^k2^r\binom{n-k}{r}\binom{k-1}{r-1}. \] where \( n \) represent the numbers of elements, \( k \) the number of forbidden pairs, \( r \) the number of clusters of forbidden pairs, called parts.

This is done by excluding all the permutation containing forbidden pairs, from all possible permutations, using the inclusion-exclusion.

A Lifelong Mathematical Obsession - YouTube

11. Bell Numbers

  • \(B_n\)

11.1. Partition of a Set

11.1.1. Definition

Set of disjoint nonempty subsets of a set that covers the set.

11.1.2. Properties

  • Every equivalence relation on a set defines a partition of the set

11.1.3. Mesh

  • \( \| P \| \)
  • Norm

The length of the longest subset.

11.2. Definition

Number of partitions of a set.

It is different from the integer partition in that each element is distinct from another.

12. Stirling Numbers

12.1. Unsigned First Kind

  • \[ \left[\vphantom{1}n \atop k\right] \]

12.1.1. Properties

Recurrence relation \[ \left[n+1 \atop k\right] = n\left[\vphantom{0}n \atop k\right] + \left[n \atop k-1\right] \]

12.2. Second Kind

  • \[ \left\{\vphantom{1}n \atop k\right\} \]

12.2.1. Definition

The number of ways to cover the set \( [n] \) with \( k \) disjoint subsets, with the understanding that:

\begin{align*} \left\{\vphantom{1}n \atop k\right\} := \begin{cases} 0 & \text{if $n< k$}, \\ 1 & \text{if $n=k$ or $k=1$ with $n \ge 1$}, \\ 1 & \text{if $n=k=0$}, \\ \text{\#($k$ disjoint cover)} & \text{otherwise}. \end{cases} \end{align*}

\( k!\left\{\vphantom{1}n \atop k\right\} \) counts the number of surjective functions of the form \( f: [n] \to [k] \). The number can also be given by: \[ \left\{\vphantom{1}n \atop k\right\} = \frac{1}{k!} \sum_{j=0}^k(-1)^j\binom{k}{j}(k-j)^n = \sum_{j=0}^k(-1)^j \frac{(k-j)^n}{j!(k-j)!}. \] This formulation is equivalent to the one before since a subset correspond to an image of an element in the codomain.

12.2.2. Properties

Recurrence relation \[ \left\{\vphantom{1}n \atop k\right\} = k\left\{n-1 \atop k\right\} + \left\{n-1 \atop k-1\right\} \] Include the element as parts of other sets, or exclude an element as a singleton set.

Relation to Bell numbers \( B_n \) \[ B_n = \sum_{k=0}^n\left\{\vphantom{1}n \atop k\right\}. \]

Special Cases \[ \left\{\vphantom{1}n \atop n-1\right\} = \binom{n}{2} \] \[ \left\{\vphantom{1}n \atop 2\right\} = 2^{n-1} - 1 \]

13. Pair Partition

13.1. Definition

The number of ways to divide a set into disjoint subsets of size two.

\[ \mathrm{PairPartition}(n) = \begin{cases} n!! & \text{if $n$ is even,}\\ 0 & \text{if $n$ is odd.} \end{cases} \]

14. Integer Partition

14.1. Definition

  • Way of writing \(n\) as a sum of positive integers, without distinguishing different orders.

14.2. Partition Function

  • \(p(n)\)
  • Partition function \(p(n)\) is the number of partitions of a non-negative integer \(n\).

14.3. Properties

  • \[ \sum_{n=0}^\infty p(n)q^n = \prod_{j=1}^\infty \sum_{i=0}^\infty q^{ji} = \prod_{j=1}^\infty \frac{1}{1-q^j} \]
  • Ramanujan noticed:
    • \(5\mid p(5k + 4)\), \(7\mid p(7k+5)\), \(11\mid p(11k+6)\)
  • \[ p(n) \sim \frac{1}{4n\sqrt{3}}\exp\left(\pi\sqrt{\frac{2n}{3}}\right) \]

14.4. Young Diagram

  • Ferrers Diagram

Ferrer_partitioning_diagrams.svg

Figure 1: partition

14.5. Composition

  • The order is also taken into account, unlike partitions.
  • Positive integer has \(2^{n-1}\) distinct compositions.

15. Necklace Polynomial

15.1. Definition

\(M(\alpha, n)\) is the number of distinct aperiodic necklaces of \(n\) beads chosen out of \(\alpha\) available colors.

\[ \alpha^n = \sum_{d|n} d\cdot M(\alpha, d) \]

15.2. General Necklace Polynomial

  • General Necklace-Counting Function
  • It includes the periodic ones as well.

\[ N(\alpha, n) = \sum_{d|n}M(\alpha,d) = \frac{1}{n}\sum_{d|n}\varphi\left(\frac{n}{d}\right)\alpha^d \] where \(\varphi\) is the Euler's totient function.

16. Pólya Enumeration Theorem

  • Redfield-Pólya Theorem, Pólya Counting
  • Generalization of the Burnside's lemma for the coloring case.

16.1. Statement

  • Let \(X\) be a finite set, \(G\) be the group of permutations of \(X\), and \(Y\) be a possibly infinite weighted set with the numbers \(f_{w_i}\) of scalar- or vector-valued weight \(w_i\in \mathbb{N}_0^{k\le \infty}\) elements are given by the generating function: \[ f(t_1, t_2,\dots) = f_{(0,0,\dots)} + f_{(1,0,\dots)}t_1 + f_{(0,1,\dots)}t_2 + \cdots + f_{(1,1,\dots)}t_1t_2 + \cdots + f_{(2,0,\dots)}t_1^2 + \dots. \]
    • The exponent is the weight, and the subscript is the position of the weight.
  • Let \(Z_G\) be the multivariate generating function cycle index: \[ Z_G(t_1, t_2, \dots, t_n) = \frac{1}{|G|}\sum_{g\in G}t_1^{c_1(g)}t_2^{c_2(g)}\cdots t_n^{c_n(g)} \]
    • where \(n = |X|\) and \(c_k(g)\) is the number of \(k\)-cycles of the group element \(g\) as a permutation of \(X\).
  • The generating function \(F(t_1, t_2, \dots)\) of the number \(F_{w_i}\) of arrangements \(\varphi\in Y^X\) with weight \(w_i = \sum_{x\in X}w(\varphi(x))\) is given by:
    • \[ F(t_1, t_2, \dots) = Z_G(f(t_1, t_2, \dots), f(t_1^2, t_2^2, \dots), f(t_1^3, t_2^3, \dots), \dots, f(t_1^n, t_2^n, \dots)). \]

16.2. Cycle Index

  • For a group \(G\) as the permutations (often by a natural action), the cycle index is
  • \[ Z(G) = \frac{1}{|G|}\sum_{g\in G}\prod_{k=1}^n a_k^{j_k(g)} \]
    • where \( j_k(g) \) is the number of cycles of \( g \) of length \( k \).
  • It is well defined, since every permutation \( g \) in \(G\) has a unique decomposition into disjoint cycles: \[ \prod_{c\ \text{cycle}\in g}a_{|c|} = \prod_{k=1}^na_k^{j_k(g)} \]
    • \( |c| \) is the length of the cycle \(c\).
  • The group \(G\) consists of coefficient number of elements containing the exponent number of cycles of length given by the subscript.

16.3. Special Case

  • For the special case, that there are \(m\) elements (colors) in \(Y\) with wight 0, \(f(t) = m\).
  • \[ F(0) = Z_G(m,m,\dots,m) \]
  • which simplifies to \[ |Y^X/G| = \frac{1}{|G|}\sum_{g\in G}m^{c(g)}. \]

17. Parity of Permutation

  • Sign of Permutation, Signature of Permutation
  • \(\mathrm{sgn}\)

17.1. Definition

  • Parity of the number of inversions: \[ \operatorname{sgn}(\sigma) = (-1)^{N(\sigma)} \]
  • The number of transpositions equivalent. Although there's many possible decompositions, the parity remains the same, which means the parity is well-defined.

17.2. Inversion

  • A pair of elements that are out of order with respect to the initial position.

18. DIE Method

  • Describe, Involution, Exception

It is the method for finding the value of alternating sum.

18.1. Method

  • Describe: Describe the term
  • Involution: Find the parity involution
  • Exception: The exception to the parity involution will be left behind as the result of the sum.

19. References

Author: Jeemin Kim

Created: 2026-07-12 Sun 14:29