Combinatorics For CP

 i. Rule of Product & Sum :

 - If there are N ways  of doing something and M ways of doing another thing after that, then there are (N * M) ways to perform both of these actions. (Product rule)

- If there are N choices for one action and M choices for another action and two actions can not be done at the same time, then there are (N + M) ways to choose one of these actions. If the question can be rephased with word "OR" this indicates that the rule of sum applies. (Sum rule)

ii. Permutation : 

- The number of permutations of N distinct objects is N! .

- From N distinct objects permutation of R objects is N! / (N-R)! . (_nP_r)

- The permutation of N objects with n₁ are of type one, n₂ are of type two, ..., n_k are of type k is 

N! / (n₁! n₂!...n_k!) . (Permutation with Repetition)

 - The number of circular permutation of N distinct objects is (N-1)! . (Circular Permutation)

iii. Combination : 

- From N distinct objects choose R objects N! / (R! * (N-R)!) . (_nC_r)

- We can write, _nC_r = _(n-1)C_(r-1) + _(n-1)C_r . (Pascal's Rule)

- We can write, _nC_r = _nC_(n-r) . 

- We can write, (Hockey-stick Identity)

- We can write, (Vandermonde's Identity)

- If we have N objects out of which we want to choose K objects and it is allowed to choose one object more than once, then number of ways are, _(N+K-1)C_(K) or, _(N+K-1)C_(N-1) . (Combination with Repetition)

- Number of K-combination for all K, _nC₀ + _nC₁ + _nC₂ + _nC₃ + ... + _nC_k = 2ⁿ .

iv. Binomial Theorem : 

- It is, (a+b)ⁿ = _nC₀ aⁿ b⁰ + _nC₁ a^(n-1) b¹ + ... + _nC_(n-1) a¹ b^(n-1) + _nC_n a⁰ bⁿ . (General Form: _nC_k a^(n-k) b^k)

v. The Pigeonhole Principle : 

- If more than N objects are distributed in N boxes, then at least one box will contain at least two objects. (Naive Form)

- For any positive integer N and K, if (NK+1) or more objects are placed in N boxes, then one box will contain more than K objects. (Second Form)

- If q₁, q₂, ..., q_n be positive integers and (q₁ + q₂ + ... + q_n - n + 1) objects are put into n boxes, then either the 1^st box contains at least q₁ objects, or the 2^nd box contains at least q₂ objects, ..., the n^th box contains at least q_n objects. (Strong Form)

vi. Rectangular Grid Walk : 

- Using only up and right move, we can go bottom-left corner to top-right corner in a (N * M) grid in _(N+M)C_N or _(N+M)C_M ways. (No Restrictions)

- Having one restricted point (a, b), the number of ways is, _(N+M)C_N - ( _(a+b)C_a * _{((N+M)-(a+b))}C_(N-a) ) . (Using PIE)

- What should we do if restricted points are 50 or more???

- For King's Move ((0,0) to (n,n)), 

vii. Catalan Number : 

- A sequence of positive integers, where,  C(n) = (1 / (n+1)) * _2nC_n .

- Applications, Link

viii. Stars & Bars : 

- To place N indistinguishable objects in K groups we need (K-1) dividers, the number of ways is, _(N+K-1)C_N or _(N+K-1)C_(K-1) .

 - To Learn more about Lower/Upper Bound of each partition read this.

ix. Stirling Number : 

- The number of permutation of [n] with exactly k cycles is, S(n, k) = S(n-1, k-1) + (n-1) * S(n-1, k) . Where, S(n, 1) = (n-1)! & S(n, n) = 1. (First Kind)

                                                 Fig. : S(4, 2) = 11

 - If self-cycle is not possible, S(n, k) = (n-1) * S(n-2, k-1) + (n-1) * S(n-1, k) . Where, S(n, 1) = (n-1)!

- S(n, k) be total number of partitions of n objects into k non-empty sets, S(n, k) = k * S(n-1, k) + S(n-1, k-1) . Where, S(n, 1) = S(n, n) = 1. (Second Kind)

x. Bell Number : 

- Given a set of n numbers, the ways of partitioning it is,

Here, S(n, k) is second kind starling number.

xi. Burnside's Lemma : 

- ( Under Construction :3 )

*** Proofs are available in google. So, interested people can search to learn more! :)

*** To Practice them https://brilliant.org is a good source.