Korean, Edit

Chapter 2. Number of Cases

Higher category: 【Statistics】 Statistics Overview

1. overview  

2. permutation  

3. combination  

4. Catalan Numbers

a. Example problems for number of cases

1. Overview

⑴ sampling

① with-replacement: re-injecting and extracting something already extracted

② without-replacement: extracting without re-injecting what has already been extracted.

⑵ types of number of cases

Figure 1. type of number of cases

2. Permutation

⑴ Overview

① Definition: The number of ways to arrange k balls out of n distinct balls, considering the order. This is a case of selection without replacement.

② In other words, selecting r items from n distinct elements without repetition and arranging them in a line.

③ Formula: _nP_r = n(n−1)(n−2)⋯(n−r+1) (Note: n!=n(n−1)(n−2)⋯2⋅1)

④ Examples: Forming a line (e.g., people standing in a row), Selecting representatives for distinct roles

⑵ Types

① Permutation with repetition: Order matters; selection with replacement

② Permutation of multisets: Permutations that include identical elements

③ Circular permutation: Number of ways to arrange elements around a circle (e.g., seating around a round table)

3. Combination

⑴ Overview

① definition: number of cases of combination of k balls among n balls. no consideration of order. without-replacement

② That is, choosing r items from n distinct items without considering the order and without repetition.

③ Examples: cases of selection, choosing representatives (roles that are the same).

⑵ binary coefficient may be expressed in a triangule of Pascal

Figure 2. binary coefficient and triangle of Pascal

⑶ combination with repetition

① definition: consideration of order. with-replacement

_nH_k

② equivalent expression

a₁ + ··· + a_n = k, = k, a_i ≥ 0

⇔ A₁ + ··· + A_n = k+n, A_i ≥1

⇔ □ | □ | ··· | □,     # of □ = (k+n) and # of | = (k+n-1)

⇔ _nH_k = _n+k-1C_n-1 = _n+k-1C_k

⑷ Formula 1. The number of ways to choose r items from n items is always the same as the number of ways to choose the n-r items that are not selected.

⑸ Formula 2.

⑹ Formula 3.

⑺ Formal 4.

① Combinatoric interpretation

○ First equation: The number of ways to distribute n stones into 2n positions, divided into n positions on the left and n positions on the right.

○ Second equation: The number of ways to distribute K stones into N+M positions, divided into N positions on the left and M positions on the right.

⑻ Formula 5.

① Algebraic interpretation

② Combinatoric interpretation

○ _nC_k: number of cases in which k numbers are selected out of n numbers

○ _n-1C_k: number of cases in which k numbers are selected excluding a specific number.

○ _n-1C_k-1: number of cases in which k numbers are selected including a specific number 

⑼ Formula 6

① Algebraic interpretation: By marking Formula 5, _nC_k = _n-1C_k + _n-1C_k-1, appropriately on Pascal’s triangle, we can easily prove it.

⑽ Formula 7

① Algebraic interpretation

② Combinatoric interpretation 

○ situation: number of cases in which n+1 numbers are selected from 1 to n+m+1 numbers 

○ _nC_n: number of cases in which n+1 is the largest number of a combination

○ _n+1C_n: number of cases in which n+2 is the largest number of a combination 

○ _n+mC_n: number of cases in which n+m+1 is the largest number of a combination 

⑾ Formula 8

① Algebraic interpretation

② Combinatoric interpretation

○ the probability of tossing a coin until the front or the back comes out n+1 times = 1

○ _nC_n × (½)ⁿ⁺¹ × 2: the probability that the same side as the last side comes out n times, and the different side comes out 0 times 

○ _n+1C_n × (½)ⁿ⁺² × 2: the probability that the same side as the last side will come out n times, and the different side will come out 1 time 

○ _2nC_n × (½)²ⁿ⁺¹ × 2: the probability that the same side as the last side comes out n times, and the different side comes out n times

⑿ Formula 9

① Algebraic Interpretation

② Combinatorial Interpretation

○ Assume that among n stones, there are k black stones and (n-k) white stones. Now, add one special black stone and assume that this special black stone must be the (m+1)-th black stone.

○ For each j ∈ {0, ⋯, k}: There are (j+m) stones in front of this black stone, among which m black stones must be placed. Thus, we consider _j+mC_j. Also, there are (n-m-j) stones behind this black stone, among which (k-j) black stones must be placed. Thus, we consider _n-m-jC_k-j.

○ Since the total number of cases is simply the number of ways to distribute (k+1) black stones and (n-k) white stones, the total count is _n+1C_k.

Here is the clear and faithful English translation:

4. Catalan Numbers

⑴ Catalan Number

① Meaning 1. Number of Dyck paths

Figure 3. Dyck path

○ (Number of Dyck paths) = (Total number of paths) − (Number of bad paths)

○ (Total number of paths) = number of ways to choose n steps out of 2n steps = _2nC_n

○ A bad path is a path that reaches level –1 at some point; if we reflect the remaining part of the path after the first time it reaches –1, every bad path corresponds one-to-one with a path that eventually reaches level –2 → (Number of bad paths) = _2nC_n+1

○ (Number of Dyck paths) = Catalan number C_k

② Meaning 2. Number of permutations π satisfying:

○ π(i) ≠ i

○ For every integer i with 1 ≤ i ≤ 2n: (π○π)(i) = i

○ There do*not exist integers 1 ≤ a < b < c < d ≤ 2n such that π(a) > π(b) > π(c) > π(d).

③ Meaning 3. The number of different ways to correctly match n pairs of parentheses

④ Property 1. 4^k ≥ C_k ≥ 2^2k+1 / (4k² + 6_k + 2)

⑵ Motzkin Number

① Meaning 1. Number of permutations satisfying:

○ For every integer i with 1 ≤ i ≤ 2n: (π○π)(i) = i

○ There do*not exist integers 1 ≤ a < b < c < d ≤ 2n such that π(a) > π(b) > π(c) > π(d).

○ That is, it can be expressed as follows where C_k is the Catalan number:

② Property 1. lim_n→∞ a_n ^1/n = 3 (proof)

Input: 2019.06.27 09:48