当前位置：网站首页>[combinatorics] combinatorial identities (sum of variable terms 3 combinatorial identities | sum of variable terms 4 combinatorial identities | binomial theorem + derivation to prove combinatorial ide
[combinatorics] combinatorial identities (sum of variable terms 3 combinatorial identities | sum of variable terms 4 combinatorial identities | binomial theorem + derivation to prove combinatorial ide
2022-07-03 15:57:00 【Programmer community】
List of articles
- One 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 1
- Two 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 1 prove ( binomial theorem + Derivation )
- 3、 ... and 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 2
- Four 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 2 prove ( Use known identities to prove )
One 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 1
Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients :
∑
k
=
0
n
k
(
n
k
)
=
n
2
n
−
1
\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}
k=0∑nk(kn)=n2n−1
k
k
k As the sum term changes , The range of change
0
0
0 ~
n
n
n ;
1. Method of proof :
- binomial theorem : Use binomial theorem + Derivation It can be proved that the combinatorial identity ;
- The combinatorial identity is substituted into : Use Known combinatorial identities are substituted into , Elimination coefficient ; That is, before using
3
3
3 Recursion , Simple and , Staggered and ,
5
5
5 Combinatorial identities Plug in ;
Two 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 1 prove ( binomial theorem + Derivation )
Use binomial theorem + The derivation method proves the following identity :
∑
k
=
0
n
k
(
n
k
)
=
n
2
n
−
1
\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}
k=0∑nk(kn)=n2n−1
binomial theorem :
(
x
+
y
)
n
=
∑
k
=
0
n
(
n
k
)
x
k
y
n
−
k
(x + y)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k y^{n-k}
(x+y)n=k=0∑n(kn)xkyn−k
1.
y
=
1
y = 1
y=1 Sometimes this happens :
(
x
+
1
)
n
=
∑
k
=
0
n
(
n
k
)
x
k
(x +1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k
(x+1)n=k=0∑n(kn)xk , In the above formula , Let the constant term
k
=
0
k= 0
k=0 The situation is calculated separately ,
(
n
0
)
x
0
=
1
\dbinom{n}{0}x^0 = 1
(0n)x0=1 , The calculation process is as follows :
(
x
+
1
)
n
=
∑
k
=
0
n
(
n
k
)
x
k
=
(
n
0
)
x
0
+
∑
k
=
1
n
(
n
k
)
x
k
=
1
+
∑
k
=
1
n
(
n
k
)
x
k
(x +1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k = \dbinom{n}{0}x^0 + \sum\limits_{k=1}^n \dbinom{n}{k}x^k = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k
(x+1)n=k=0∑n(kn)xk=(0n)x0+k=1∑n(kn)xk=1+k=1∑n(kn)xk
2. Introduce derivation : In addition to the summation
∑
k
=
1
n
(
n
k
)
x
k
\sum\limits_{k=1}^n \dbinom{n}{k}x^k
k=1∑n(kn)xk It appears that
k
k
k Number of changes , Need to be right
x
x
x To find the derivative ;
It's directly to
(
x
+
1
)
n
=
1
+
∑
k
=
1
n
(
n
k
)
x
k
(x +1)^n = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k
(x+1)n=1+k=1∑n(kn)xk Take derivatives on both sides of the equation ;
( 1 ) Left combined ( According to the following power function derivative formula Calculation ) :
(
x
+
1
)
n
(x +1)^n
(x+1)n Derivative is
n
(
x
+
1
)
n
−
1
n(x+1)^{n-1}
n(x+1)n−1
( 2 ) Right combination ( According to the following Derivative operation rules and Power function derivative formula Calculation ) :
1
+
∑
k
=
1
n
(
n
k
)
x
k
1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k
1+k=1∑n(kn)xk Derivative is ,
1
1
1 The derivative of by
0
0
0 , add
∑
k
=
1
n
(
n
k
)
x
k
\sum\limits_{k=1}^n \dbinom{n}{k}x^k
k=1∑n(kn)xk The derivative of
∑
k
=
1
n
k
(
n
k
)
x
k
−
1
\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}
k=1∑nk(kn)xk−1 , The end result is
∑
k
=
1
n
k
(
n
k
)
x
k
−
1
\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}
k=1∑nk(kn)xk−1
( 3 ) The left and right derivatives are equal :
n
(
x
+
1
)
n
−
1
=
∑
k
=
1
n
k
(
n
k
)
x
k
−
1
n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}
n(x+1)n−1=k=1∑nk(kn)xk−1
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 is0
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
3. The result of derivation is as follows :
n
(
x
+
1
)
n
−
1
=
∑
k
=
1
n
k
(
n
k
)
x
k
−
1
n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}
n(x+1)n−1=k=1∑nk(kn)xk−1
Suppose... In the result of derivation
x
=
1
x = 1
x=1 , The results are as follows :
n
2
n
−
1
=
∑
k
=
1
n
k
(
n
k
)
n2^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}
n2n−1=k=1∑nk(kn)
When
k
=
0
k = 0
k=0 when , Yes
k
(
n
k
)
=
0
×
(
n
0
)
=
0
k \dbinom{n}{k} = 0 \times \dbinom{n}{0} = 0
k(kn)=0×(0n)=0 ,
So add
k
=
0
k=0
k=0 The situation of , namely
k
k
k from
0
0
0 Start accumulating , Nor does it affect the above results :
n
2
n
−
1
=
∑
k
=
0
n
k
(
n
k
)
n2^{n-1} = \sum\limits_{k=0}^n k \dbinom{n}{k}
n2n−1=k=0∑nk(kn)
3、 ... and 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 2
Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients :
∑
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=0∑nk2(kn)=n(n+1)2n−2
k
k
k As the sum term changes , The range of change
0
0
0 ~
n
n
n ;
Method of proof :
- binomial theorem : Use binomial theorem + Derivation It can be proved that the combinatorial identity ;
- The combinatorial identity is substituted into : Use Known combinatorial identities are substituted into , Elimination coefficient ; That is, before using
3
3
3 Recursion , Simple and , Staggered and ,
5
5
5 Combinatorial identities Plug in ;
Four 、 Combinatorial identity ( Change the next term to sum ) Sum of variable coefficients 2 prove ( Use known identities to prove )
Use Known identities Prove the following identity :
∑
k
=
0
n
k
2
(
n
k
)
=
n
(
n
+
1
)
2
n
−
2
\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}
k=0∑nk2(kn)=n(n+1)2n−2
1. Enumeration of known identities :
- ① recursion
1
1
(
n
k
)
=
(
n
n
−
k
)
\dbinom{n}{k} = \dbinom{n}{n-k}
(kn)=(n−kn)
1 :
- ② recursion
2
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)
2 :
- ③ recursion
3
3
(
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)
3 Pascal / Yang Hui's trigonometric formula :
- ④ Change the next term to sum 1 Simple and :
∑
k
=
0
n
(
n
k
)
=
2
n
\sum_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n
- ⑤ Change the next term to sum 2 Staggered and :
∑
k
=
0
n
(
−
1
)
k
(
n
k
)
=
0
\sum_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0
k=0∑n(−1)k(kn)=0
2. Variable lower limit : from
∑
k
=
0
n
k
2
(
n
k
)
\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k}
k=0∑nk2(kn) Start deducing ,
k
=
0
k=0
k=0 when ,
k
2
(
n
k
)
=
0
k^2 \dbinom{n}{k} = 0
k2(kn)=0 , You can ignore , Here you can go from
1
1
1 Start accumulating ;
∑
k
=
0
n
k
2
(
n
k
)
=
∑
k
=
1
n
k
2
(
n
k
)
\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = \sum\limits_{k=1}^{n} k^2 \dbinom{n}{k}
k=0∑nk2(kn)=k=1∑nk2(kn)
Use
(
n
k
)
=
n
k
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}
(kn)=kn(k−1n−1) Identity replaces one of
(
n
k
)
\dbinom{n}{k}
(kn) :
=
∑
k
=
1
n
k
2
n
k
(
n
−
1
k
−
1
)
= \sum\limits_{k=1}^{n} k^2 \dfrac{n}{k} \dbinom{n - 1}{k - 1}
=k=1∑nk2kn(k−1n−1)
3. Elimination coefficient : Eliminate one
k
k
k after , It becomes the following formula :
=
∑
k
=
1
n
k
n
(
n
−
1
k
−
1
)
=\sum\limits_{k=1}^{n} k n \dbinom{n - 1}{k - 1}
=k=1∑nkn(k−1n−1)
4. Constant mention : Among them
n
n
n Compared with summation , Is a constant , It can be mentioned beyond the summation symbol :
=
n
∑
k
=
1
n
k
(
n
−
1
k
−
1
)
=n\sum\limits_{k=1}^{n} k \dbinom{n - 1}{k - 1}
=nk=1∑nk(k−1n−1)
5. Deformation and disassembly : There are
(
n
−
1
k
−
1
)
\dbinom{n - 1}{k - 1}
(k−1n−1) , In order to
k
−
1
k-1
k−1 Match , There will be
k
k
k To deform ,
k
=
(
k
−
1
)
+
1
k = (k - 1) + 1
k=(k−1)+1 , Can come up with a
k
−
1
k-1
k−1 Come on ;
=
n
∑
k
=
1
n
[
(
k
−
1
)
+
1
]
(
n
−
1
k
−
1
)
=n\sum\limits_{k=1}^{n} [( k - 1 ) +1] \dbinom{n - 1}{k - 1}
=nk=1∑n[(k−1)+1](k−1n−1)
Using the summation formula , Disassemble the above formula into two sums ,
=
n
∑
k
=
1
n
(
k
−
1
)
(
n
−
1
k
−
1
)
+
n
∑
k
=
1
n
(
n
−
1
k
−
1
)
=n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}
=nk=1∑n(k−1)(k−1n−1)+nk=1∑n(k−1n−1)
6. The first combinatorial transformation :
n
∑
k
=
1
n
(
k
−
1
)
(
n
−
1
k
−
1
)
n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1}
nk=1∑n(k−1)(k−1n−1) Sum up ,
k
=
1
k=1
k=1 when , Next item of combinatorial number , The coefficient in the summation
k
−
1
=
0
k-1=0
k−1=0 , take
k
k
k Transform the lower bound ,
k
k
k The value is
1
1
1 ~
n
n
n , be
k
−
1
k-1
k−1 The value is
0
0
0 ~
(
n
−
1
)
(n-1)
(n−1) ,
It is equivalent to using
k
′
=
k
−
1
k' = k-1
k′=k−1 Replace the previous one
k
k
k ,
k
′
k'
k′ Value range
0
0
0 ~
(
n
−
1
)
(n-1)
(n−1) ,
So it can finally become
n
∑
k
′
=
0
n
−
1
(
k
′
)
(
n
−
1
k
′
)
n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'}
nk′=0∑n−1(k′)(k′n−1)
Use
∑
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 Combinatorial identity ,
Above
∑
k
′
=
0
n
−
1
(
k
′
)
(
n
−
1
k
′
)
\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'}
k′=0∑n−1(k′)(k′n−1) The result is
(
n
−
1
)
2
n
−
2
(n-1)2^{n-2}
(n−1)2n−2 ,
Front times
n
n
n , The final
n
∑
k
′
=
0
n
−
1
(
k
′
)
(
n
−
1
k
′
)
=
n
(
n
−
1
)
2
n
−
2
n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} = n(n-1)2^{n-2}
nk′=0∑n−1(k′)(k′n−1)=n(n−1)2n−2
7. The second combinatorial transformation :
n
∑
k
=
1
n
(
n
−
1
k
−
1
)
n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}
nk=1∑n(k−1n−1) In this combination
k
k
k The value is
1
1
1 ~
n
n
n , take
k
k
k Change from
0
0
0 Start , That is to use
k
′
=
k
−
1
k' = k-1
k′=k−1 replace
k
k
k ,
Then there are
n
∑
k
′
=
0
n
−
1
(
n
−
1
k
′
)
n\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'}
nk′=0∑n−1(k′n−1) , This summation can be transformed into a basic summation ,
Use Simple and Combinatorial identity
∑
k
=
0
n
(
n
k
)
=
2
n
\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n ,
∑
k
′
=
0
n
−
1
(
n
−
1
k
′
)
\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'}
k′=0∑n−1(k′n−1) Namely
2
n
−
1
2^{n-1}
2n−1 , Front times
n
n
n ,
n
∑
k
=
1
n
(
n
−
1
k
−
1
)
n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}
nk=1∑n(k−1n−1) Namely
n
2
n
−
1
n2^{n-1}
n2n−1
=
n
∑
k
=
1
n
(
k
−
1
)
(
n
−
1
k
−
1
)
+
n
∑
k
=
1
n
(
n
−
1
k
−
1
)
=n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}
=nk=1∑n(k−1)(k−1n−1)+nk=1∑n(k−1n−1)
=
n
(
n
−
1
)
2
n
−
2
+
n
2
n
−
1
=n(n-1)2^{n-2} + n2^{n-1}
=n(n−1)2n−2+n2n−1
=
n
(
n
−
1
)
2
n
−
2
+
n
2
×
2
n
−
2
=n(n-1)2^{n-2} + n 2 \times2^{n-2}
=n(n−1)2n−2+n2×2n−2
=
n
(
n
+
1
)
2
n
−
2
=n(n+1)2^{n-2}
=n(n+1)2n−2
summary :
First use of recursion , Eliminate the coefficient of variation
k
k
k ,
Add up each formula of the sum to the basic sum formula , or Known summation formula ,
Then sum and change the limit , That is to use
k
′
=
k
−
1
k' = k-1
k′=k−1 Replace
k
k
k ,
Through the above skills , Certificate of completion ;
边栏推荐
- Visual host system design and development (Halcon WinForm)
- 驱动与应用程序通信
- Baidu AI Cloud helps Shizuishan upgrade the smart health care model of "Internet + elderly care services"
- Approval process design
- VC下Unicode和ANSI互转，CStringW和std::string互转
- Visual upper system design and development (Halcon WinForm) -4 Communication management
- How idea starts run dashboard
- Distributed task scheduling XXL job
- 请求头不同国家和语言的表示
- Automatic generation of client code from flask server code -- Introduction to flask native stubs Library
猜你喜欢
The difference between calling by value and simulating calling by reference
Visual host system design and development (Halcon WinForm)
WinDbg分析dump文件
Visual upper system design and development (Halcon WinForm) -4 Communication management
"Remake Apple product UI with Android" (3) - elegant statistical chart
Digital image processing -- popular understanding of corrosion and expansion
Q2 encryption market investment and financing report in 2022: gamefi becomes an investment keyword
【Proteus仿真】74HC595+74LS154驱动显示16X16点阵
Unity function - unity offline document download and use
App移动端测试【3】ADB命令
随机推荐
Microservice API gateway zuul
C language brush questions ~leetcode and simple questions of niuke.com
Low level version of drawing interface (explain each step in detail)
【OpenCV 例程200篇】217. 鼠标交互获取多边形区域（ROI）
June to - -------
Pandora IOT development board learning (HAL Library) - Experiment 5 external interrupt experiment (learning notes)
秒杀系统2-Redis解决分布式Session问题
Digital image processing -- popular Canny edge detection
The difference between RAR and zip files
[combinatorics] combinatorial identities (recursive combinatorial identities | sum of variable terms | simple combinatorial identities and | sum of variable terms | staggered sums of combinatorial ide
Microservices - load balancing ribbon
QT use qzxing to generate QR code
软件安装信息、系统服务在注册表中的位置
App移动端测试【3】ADB命令
自定义注解
Three dimensional reconstruction of deep learning
CString getbuffer and releasebuffer instructions
pyinstaller不是内部或外部命令，也不是可运行的程序 或批处理文件
"Remake Apple product UI with Android" (3) - elegant statistical chart
Download and install common programs using AUR