当前位置：网站首页>[combinatorics] summary of combinatorial identities (eleven combinatorial identities | proof methods of combinatorial identities | summation methods)*
[combinatorics] summary of combinatorial identities (eleven combinatorial identities | proof methods of combinatorial identities | summation methods)*
2022-07-03 16:08:00 【Programmer community】
List of articles
- One 、 Eleven combinatorial identities
- Two 、 Combinatorial identity Method of proof
- 3、 ... and 、 Combinatorial number Sum up
∑
\sum
∑ Method
Combinatorial identity reference blog :
- 【 Combinatorial mathematics 】 Binomial theorem and combinatorial identities ( binomial theorem | Three combinatorial identities recursion | recursion 1 | recursion 2 | recursion 3 Pascal / Yang Hui's trigonometric formula | Combination analysis method | Characteristics of recursive combinatorial identities )
- 【 Combinatorial mathematics 】 Combinatorial identity ( Recurrence Combinatorial identity | Change the next term to sum Combinatorial identity Simple and | Change the next term to sum Combinatorial identity Staggered and )
- 【 Combinatorial mathematics 】 Combinatorial identity ( Change the next term to sum 3 Combinatorial identity | Change the next term to sum 4 Combinatorial identity | binomial theorem + Derivation Prove the combinatorial identity | Use known combinatorial identities to prove combinatorial identities )
- 【 Combinatorial mathematics 】 Combinatorial identity ( Review of eight combinatorial identities | Combinatorial identity product 1 | prove | Use scenarios )
- 【 Combinatorial mathematics 】 Combinatorial identity ( Combinatorial identity Sum of product 1 | Sum of product 1 prove | Combinatorial identity Sum of product 2 | Sum of product 2 prove )
One 、 Eleven combinatorial identities
1 . Combinatorial identity ( recursion ) :
( 1 ) recursion 1 :
(
n
k
)
=
(
n
n
−
k
)
\dbinom{n}{k} = \dbinom{n}{n-k}
(kn)=(n−kn)①
( 2 ) recursion 2 :
(
n
k
)
=
n
k
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}
(kn)=kn(k−1n−1)②
( 3 ) recursion 3 ( Pascal / Yang Hui's trigonometric formula ) :
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn)=(kn−1)+(k−1n−1)③
2 . Review the combinatorial identities of summation under four variables : The combinatorial identity introduced earlier The number of combinations in
(
n
k
)
\dbinom{n}{k}
(kn) , Is the next item
k
k
k Have been accumulating changes , have
∑
k
=
0
n
\sum\limits_{k=0}^{n}
k=0∑n Cumulative property , Previous item
n
n
n It is the same. ;
( 1 ) Simple and :
∑
k
=
0
n
(
n
k
)
=
2
n
\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n④
( 2 ) Staggered and :
∑
k
=
0
n
(
−
1
)
k
(
n
k
)
=
0
\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0
k=0∑n(−1)k(kn)=0⑤
( 3 ) Change the next term to sum 3 :
∑
k
=
0
n
k
(
n
k
)
=
n
2
n
−
1
\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}
k=0∑nk(kn)=n2n−1⑥
( 4 ) Change the next term to sum 4 :
∑
k
=
0
n
k
2
(
n
k
)
=
n
(
n
+
1
)
2
n
−
2
\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}
∑k=0nk2(kn)=n(n+1)2n−2⑦
3 . Change the upper term to sum :
∑
l
=
0
n
(
l
k
)
=
(
n
+
1
k
+
1
)
\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}
l=0∑n(kl)=(k+1n+1)⑧
4 . product :
∑
l
=
0
n
(
l
k
)
=
(
n
+
1
k
+
1
)
\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}
l=0∑n(kl)=(k+1n+1)⑨
5 . Sum of product :
( 1 ) Combinatorial identity ( Sum of product ) 1 :
∑
k
=
0
r
(
m
k
)
(
n
r
−
k
)
=
(
m
+
n
r
)
,
r
=
min
{
m
,
n
}
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}
k=0∑r(km)(r−kn)=(rm+n), r=min{ m,n}⑩
( 2 ) Combinatorial identity ( Sum of product ) 2 :
∑
k
=
0
r
(
m
k
)
(
n
k
)
=
(
m
+
n
m
)
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}
k=0∑r(km)(kn)=(mm+n)⑪
Two 、 Combinatorial identity Method of proof
1 . Known combinatorial identities are substituted into : Known
11
11
11 A combinatorial identity is substituted into
2 . binomial theorem
n
n
n It's a positive integer. , For everything
x
x
x and
y
y
y , There are the following theorems :
(
x
+
y
)
n
=
∑
k
=
0
n
(
n
k
)
x
k
y
n
−
k
(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}
(x+y)n=k=0∑n(kn)xkyn−k
(
n
k
)
\dbinom{n}{k}
(kn) Express
n
n
n Yuan centralized retrieval
k
k
k Number of combinations of elements , yes Number of sets
C
(
n
,
k
)
C(n,k)
C(n,k) Another way of writing ;
Another common form (
y
=
1
y = 1
y=1 ) :
(
1
+
x
)
n
=
∑
k
=
0
n
(
n
k
)
x
k
(1 + x)^n = \sum_{k=0}^n \dbinom{n}{k}x^k
(1+x)n=k=0∑n(kn)xk
Basic summation formula (
x
=
y
=
1
x = y =1
x=y=1 ) :
2
n
=
∑
k
=
0
n
(
n
k
)
2^n = \sum_{k=0}^n \dbinom{n}{k}
2n=k=0∑n(kn)
3 . Derivation of power series 、 integral
Derivation of power function : ( Very important )
- Primitive function :
y
=
x
n
y = x^n
y=xn
- Corresponding derivative :
y
′
=
n
x
n
−
1
y' = nx^{n-1}
y′=nxn−1
The derivative of a constant is
0
0
0 ;
Four operations of derivative :
(
u
±
v
)
′
=
u
′
±
v
′
(u \pm v)' = u' \pm v'
(u±v)′=u′±v′
Reference resources :
- derivative - Baidu Encyclopedia
- Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 1 prove ( binomial theorem + Derivation )
4 . Induction
Mathematical induction describe A proposition related to natural numbers
P
(
n
)
P(n)
P(n) ,
According to different questions , Set up
n
n
n The minimum value , Usually from
0
0
0 Start ,
( 1 ) The proof is divided into the following two steps :
① Inductive basis : First prove that Inductive basis , If it is proved that
P
(
0
)
P(0)
P(0) It's true ;
② Induction steps : according to Types of mathematical induction , Prove in different ways , Here you are First, mathematical induction and Second, mathematical induction Two kinds of induction ;
( 1 ) Mathematical induction :
① First, mathematical induction : from
P
(
n
)
P(n)
P(n) deduction
P
(
n
+
1
)
P(n + 1)
P(n+1)
P
(
0
)
P(0)
P(0) It's true
hypothesis
P
(
n
)
P(n)
P(n) It's true , prove
P
(
n
+
1
)
P(n + 1)
P(n+1) It's true
② Second, mathematical induction : All less than
n
n
n Of
P
(
0
)
,
P
(
1
)
,
⋯
,
P
(
n
−
1
)
P(0) , P(1), \cdots , P(n-1)
P(0),P(1),⋯,P(n−1) It's all true , deduction
P
(
n
)
P(n)
P(n) It's true ;
P
(
0
)
P(0)
P(0) It's true
Assume that all are less than
n
n
n The natural number of
k
k
k , proposition
P
(
k
)
P(k)
P(k) It's all true , namely
P
(
0
)
,
P
(
1
)
,
⋯
,
P
(
n
−
1
)
P(0) , P(1), \cdots , P(n-1)
P(0),P(1),⋯,P(n−1) It's all true , deduction
P
(
n
)
P(n)
P(n) It's true ;
Symbolized as :
P
(
0
)
∧
P
(
1
)
∧
⋯
∧
P
(
n
−
1
)
→
P
(
n
)
P(0) \land P(1) \land \cdots \land P(n-1) \to P(n)
P(0)∧P(1)∧⋯∧P(n−1)→P(n)
Reference resources : 【 Combinatorial mathematics 】 Introduction to combinatorics ( Combination thought 2 : Mathematical induction | Generalization of mathematical induction | Multiple inductive thoughts )
5 . Combinatorial analysis
When using the combination analysis method to prove the combination number , Specify the set first , Specify elements , Specify two counting problems , On both sides of the formula are the counts of the same problem ;
( 1 ) Specify the collection : Specify the set in which the count is generated ;
( 2 ) Specify the counting problem : The following two counting problems are the counting of the same problem ;
- ① problem 1 : The left side of the equal sign represents the counting problem ;
- ② problem 2 : The right side of the equal sign represents the counting problem ;
( 3 ) Equivalent description : It shows that the two counting problems are the same ;
Reference resources :
- 【 Combinatorial mathematics 】 Combinatorial identity ( Combinatorial identity Sum of product 1 | Sum of product 1 prove | Combinatorial identity Sum of product 2 | Sum of product 2 prove ) Two 、 Combinatorial identity ( Sum of product ) 1 prove
The above proof method , According to specific certification requirements , Choose the appropriate proof method ;
3、 ... and 、 Combinatorial number Sum up ∑
\sum
∑ Method
For formulas containing combinatorial numbers Sum up
∑
\sum
∑ Method
1 . Use Pascal formula :
recursion 3 ( Pascal / Yang Hui's trigonometric formula ) :
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn)=(kn−1)+(k−1n−1)③
( 1 ) Merge item :
(
n
k
)
\dbinom{n}{k}
(kn) Can be reduced to
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn−1)+(k−1n−1) The sum of the ;
( 2 ) This recursion , Used to split items :
Can be
(
n
k
)
\dbinom{n}{k}
(kn) Split into
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn−1)+(k−1n−1) The sum of the ; In actual use , Often encounter some items listed , Yes
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn−1)+(k−1n−1) The number of combinations of forms , Can be merged into one
(
n
k
)
\dbinom{n}{k}
(kn) ;
( 3 ) It can also be used by deformation , Put one of them , Become the difference between two of them ;
take
(
n
−
1
k
)
\dbinom{n - 1}{k}
(kn−1) Split into
(
n
k
)
−
(
n
−
1
k
−
1
)
\dbinom{n}{k} -\dbinom{n - 1}{k - 1}
(kn)−(k−1n−1) The difference between the ;
take take
(
n
−
1
k
−
1
)
\dbinom{n - 1}{k - 1}
(k−1n−1) Split into
(
n
k
)
−
(
n
−
1
k
)
\dbinom{n}{k} -\dbinom{n - 1}{k}
(kn)−(kn−1) The difference between the ;
In a stack of summation combinatorial numbers , Split into the difference between two numbers , Can offset many combinations ;
It is often used for simplification in large sum formulas ;
2 . Sum of series :
3 . Observations and results , Prove by mathematical induction :
Guess the result of a sum , Then use induction to prove ;
4 . Use the known formula to sum :
边栏推荐
- Three dimensional reconstruction of deep learning
- Colab works with Google cloud disk
- 用通达信炒股开户安全吗？
- Pychart error updating package list: connect timed out
- How can technology managers quickly improve leadership?
- Slam learning notes - build a complete gazebo multi machine simulation slam from scratch (I)
- Go语言自学系列 | golang switch语句
- Mb10m-asemi rectifier bridge mb10m
- [系统安全] 四十三.Powershell恶意代码检测系列 (5)抽象语法树自动提取万字详解
- 切入点表达式
猜你喜欢
"Remake Apple product UI with Android" (3) - elegant statistical chart
Automatic generation of client code from flask server code -- Introduction to flask native stubs Library
Jmeter线程组功能介绍
Famous blackmail software stops operation and releases decryption keys. Most hospital IOT devices have security vulnerabilities ｜ global network security hotspot on February 14
面试官：JVM如何分配和回收堆外内存
How to use AAB to APK and APK to AAB of Google play apps on the shelves
WinDbg analysis dump file
Rk3399 platform development series explanation (WiFi) 5.54. What is WiFi wireless LAN
远程文件包含实操
使用AUR下载并安装常用程序
随机推荐
nifi从入门到实战（保姆级教程）——flow
Batch files: list all files in a directory with relative paths - batch files: list all files in a directory with relative paths
[list to map] collectors Tomap syntax sharing (case practice)
Redis在Windows以及Linux系统下的安装
突破100万，剑指200万！
Slam learning notes - build a complete gazebo multi machine simulation slam from scratch (II)
[combinatorics] combinatorial identities (sum of variable terms 3 combinatorial identities | sum of variable terms 4 combinatorial identities | binomial theorem + derivation to prove combinatorial ide
App mobile terminal test [3] ADB command
How to thicken the brush in the graphical interface
“用Android复刻Apple产品UI”(3)—优雅的数据统计图表
几种常见IO模型的原理
Uploads labs range (with source code analysis) (under update)
Advanced Mathematics (Seventh Edition) Tongji University exercises 2-1 personal solutions
Reading notes of "micro service design" (Part 2)
Chinese translation of Tagore's floating birds (1~10)
Secsha system 1- login function
Remote file contains actual operation
用通达信炒股开户安全吗？
Get the executable path through the process PID (queryfullprocessimagename)
MB10M-ASEMI整流桥MB10M