Skip to content

离散数学基础:排列组合计数问题

思维导图

排列组合计数问题

P(n,r)=n!(nr)!
nr
nr

nr
nr
nr

C(n,r)=n!r!(nr)!
nr
rn
nr1(0)
nr

C(n1+r,r)=(n1+r)!r!(n1)!
nr
rn
x1+x2+...+xn=r

i=1n(rj=1i1mjmi)=(rm1)(rm1m2)...(rm1m2...mn1mn)=r!m1!m2!...m3!
m1,m2,...,mnnm1+m2+...+mn=r
rn
m1+m2+...+mn=rn使imi

x1+x2+...+xn=rximini(x1min1)+(x2min2)+...+(xnminn)=ri=1nminix1+x2+...+xn=ri=1nmini

x1+x2+...+xn=rmaxiximini:Ux1+x2+...+xn=ri=1nminiN=|U|Piximaxi,N(Pi)UPi=NN(P1P2...Pn)=N(P1P2...Pn)