当前位置：网站首页>[combinatorial mathematics] counting model, common combinatorial numbers and combinatorial identities**

[combinatorial mathematics] counting model, common combinatorial numbers and combinatorial identities**

2022-07-03 16:39:00 【Programmer community】

List of articles

One 、 Counting model
Two 、 Common combination count

One 、 Counting model

The counting model currently involved :

1 . Select the question :

$n$ Meta set

$S$ , from

$S$ Select... From the set

$r$ Elements ;

according to Whether the element can be repeated , Whether the selection process is orderly , The selection question is divided into four sub types :

	Elements do not repeat	Elements can be repeated
Orderly selection	Set arrangement $P (n, r)$	Multiset arrangement
Unordered selection	Set combination $C (n, r)$	Combination of multiple sets

Select the question :

Non repeatable elements , Orderly selection , Corresponding Arrangement of sets ; $\dfrac{n!}{(n-r)!}P(n,r)=(n−r)!n!$
Non repeatable elements , Unordered selection , Corresponding A combination of sets ; $\dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}C(n,r)=r!P(n,r)=r!(n−r)!n!$
Repeatable elements , Orderly selection , Corresponding Arrangement of multiple sets ; $\cfrac{n!}{n_1! n_2! \cdots n_k!} whole row Column =n1!n2!⋯nk!n! , Incomplete permutation k r , r ≤ n i k^r , \ \ r\leq n_ikr, r≤ni$
Repeatable elements , Unordered selection , Corresponding Combination of multiple sets ;

2 . Number of nonnegative integer solutions of indefinite equation :

⋯

x_1 + x_2 + \cdots + x_k = r

$x_{1} + x_{2} + \dots + x_{k} = r$

The number of nonnegative integer solutions is :

(

−

)

N= C(k + r - 1, r)

$N = C (k + r - 1, r)$

It is also the combinatorial number of multiple sets ;

3 . Non descending path problem :

Basic model : from

(

)

(0,0)

$(0, 0)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths

(

)

\dbinom{m + n}{m}

$(m m + n)$ ;

Expand the model 1 : from

(

)

(a,b)

$(a, b)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths

(

−

)

\dbinom{m-a + n-b}{m-a}

$(m - a m - a + n - b)$ ;

Expand the model 2 : from

(

)

(a,b)

$(a, b)$ after

(

)

(c, d)

$(c, d)$ To

(

)

(m, n)

$(m, n)$ The number of non descending paths

(

−

)

(

−

)

\dbinom{c-a + c-b}{c-a}\dbinom{m-c + n-d}{m-c}

$(c - a c - a + c - b) (m - c m - c + n - d)$

The number of non descending paths of the constraint : from

(

)

(0,0)

$(0, 0)$ To

(

)

(n,n)

$(n, n)$ Except endpoint , The number of non descending paths that do not touch the diagonal
Reference resources : 【 Combinatorial mathematics 】 Non descending path problem ( The number of non descending paths of the constraint )

Two 、 Common combination count

Common combination count :

I . Binomial coefficient

(

)

∑

(

)

−

(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}

$(x + y)^{n} = k = 0 \sum n (k n) x^{k} y^{n - k}$

(

)

\dbinom{n}{k}

$(k n)$ It's binomial coefficient ;

Binomial coefficient correlation combinatorial identity :

1 . Combinatorial identity ( recursion ) :

( 1 ) recursion 1 :

(

)

(

−

)

\dbinom{n}{k} = \dbinom{n}{n-k}

$(k n) = (n - k n)$ ①

( 2 ) recursion 2 :

(

)

(

−

)

\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}

$(k n) = \frac{n}{k} (k - 1 n - 1)$ ②

( 3 ) recursion 3 ( Pascal / Yang Hui's trigonometric formula ) :

(

)

(

−

)

(

−

)

\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}

$(k n) = (k n - 1) + (k - 1 n - 1)$ ③

2 . Review the combinatorial identities of summation under four variables : The combinatorial identity introduced earlier The number of combinations in

(

)

\dbinom{n}{k}

$(k n)$ , Is the next item

$k$ Have been accumulating changes , have

∑

\sum\limits_{k=0}^{n}

$k = 0 \sum n$ Cumulative property , Previous item

$n$ It is the same. ;

( 1 ) Simple and :

∑

(

)

\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n

$k = 0 \sum n (k n) = 2^{n}$ ④

( 2 ) Staggered and :

∑

(

−

)

(

)

\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0

$k = 0 \sum n (- 1)^{k} (k n) = 0$ ⑤

( 3 ) Change the next term to sum 3 :

∑

(

)

−

\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}

$k = 0 \sum n k (k n) = n 2^{n - 1}$ ⑥

( 4 ) Change the next term to sum 4 :

∑

(

)

(

)

−

\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}

$\sum_{k = 0}^{n} k^{2} (k n) = n (n + 1) 2^{n - 2}$ ⑦

3 . Change the upper term to sum :

∑

(

)

(

)

\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}

$l = 0 \sum n (k l) = (k + 1 n + 1)$ ⑧

4 . product :

∑

(

)

(

)

\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}

$l = 0 \sum n (k l) = (k + 1 n + 1)$ ⑨

5 . Sum of product :

( 1 ) Combinatorial identity ( Sum of product ) 1 :

∑

(

)

(

−

)

(

)

min

⁡

{

}

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}

$k = 0 \sum r (k m) (r - k n) = (r m + n), r = min {m, n}$ ⑩

( 2 ) Combinatorial identity ( Sum of product ) 2 :

∑

(

)

(

)

(

)

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}

$k = 0 \sum r (k m) (k n) = (m m + n)$ ⑪

II . Polynomial coefficients

(

⋯

)

\ \ \ \ (x_1 + x_2 + \cdots + x_t)^n

$(x_{1} + x_{2} + \dots + x_{t})^{n}$

∑

full

foot

⋯

Not

negative

whole

Count

Explain

individual

Count

(

⋯

)

⋯

= \sum\limits_{ Satisfy n_1 + n_2 + \cdots + n_t = n Number of nonnegative integer solutions }\dbinom{n}{n_1 n_2 \cdots n_t}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}

$= full foot n_{1} + n_{2} + \dots + n_{t} = n Not negative whole Count Explain individual Count \sum (n _{1} n _{2} \dots n _{t} n) x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{t}^{n_{t}}$

(

⋯

)

\dbinom{n}{n_1 n_2 \cdots n_t}

$(n _{1} n _{2} \dots n _{t} n)$ Is a polynomial coefficient

Polynomial coefficient correlation combination identity :

1 . Polynomial theorem inference 3 :

∑

(

⋯

)

\sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n

$\sum (n _{1} n _{2} \dots n _{t} n) = t^{n}$

2 . Full Permutation of multiple sets :

(

⋯

)

⋯

\dbinom{n}{n_1 n_2 \cdots n_t} = \cfrac{n!}{n_1! n_2! \cdots n_k!}

$(n _{1} n _{2} \dots n _{t} n) = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$

3 . recursion :

(

⋯

)

(

−

(

−

)

⋯

)

(

−

(

−

)

⋯

)

(

−

⋯

(

−

)

\dbinom{n}{n_1 n_2 \cdots n_t} = \dbinom{n-1}{(n_1-1) n_2 \cdots n_t} + \dbinom{n-1}{n_1 (n_2 - 1) \cdots n_t}+ \dbinom{n-1}{n_1 n_2 \cdots (n_t -1)}

$(n _{1} n _{2} \dots n _{t} n) = (( n _{1} - 1 ) n _{2} \dots n _{t} n - 1) + (n _{1} ( n _{2} - 1 ) \dots n _{t} n - 1) + (n _{1} n _{2} \dots ( n _{t} - 1 ) n - 1)$