哪里网站海报做的比较好/推广普通话绘画
卡特兰数
给定nnn个000和nnn个111，它们将按照某种排序成长度为2n2n2n的序列，求它们能排列成的所有序列中，满足任意前缀序列中000的个数都不少于111的序列有多少个？
（即从X走到Y路线不穿越，y=x的方案数）
|~~~~~~~~~~~~~~~~~~~.Y(n,n)
|
|
|
|
|
|.X(0,0)
|--------------------------------------------------------------->
Answer=C2nn−C2nn−1=C2nnn+1Answer=C_{2n}^{n}-C_{2n}^{n-1}=\frac{C_{2n}^{n}}{n+1}Answer=C2nn−C2nn−1=n+1C2nn
斯特林数
n个不同元素构成m个圆排列的数目n 个不同元素构成 m 个圆排列的数目n个不同元素构成m个圆排列的数目
S1(n,m)=(n−1)∗S1(n−1,m)+S1(n−1,m−1)S_1(n,m)=(n-1)*S_1(n-1,m)+S_1(n-1,m-1)S1(n,m)=(n−1)∗S1(n−1,m)+S1(n−1,m−1)S1(n,m)=1,S1(n,0)=0S_1(n,m)=1,S_1(n,0)=0S1(n,m)=1,S1(n,0)=0
n个不同元素划分到m个集合的方案数n个不同元素划分到 m 个集合的方案数n个不同元素划分到m个集合的方案数
S2(n,m)=m∗S2(n−1,m)+S2(n−1,m−1)S_2(n,m)=m*S_2(n-1,m)+S_2(n-1,m-1)S2(n,m)=m∗S2(n−1,m)+S2(n−1,m−1)S2(n,m)=1,S2(n,0)=0S_2(n,m)=1,S_2(n,0)=0S2(n,m)=1,S2(n,0)=0
小球问题
| 序号 | 小球(n) | 盒子(m) | 条件 | 公式 |
|---|---|---|---|---|
| 1 | 不同 | 不同 | 允许空 | mnm^nmn |
| 2 | 不同 | 不同 | 不允许空 | ∑i=0mCmi(−1)i(m−i)n\sum\limits_{i=0}^{m}C_{m}^{i}(-1)^i(m-i)^ni=0∑mCmi(−1)i(m−i)nm!S2(n,m)m!S_2(n,m)m!S2(n,m) |
| 3 | 不同 | 相同 | 不允许空 | ∑i=0mCmi(−1)i(m−i)nm!\frac{\sum\limits_{i=0}^{m}C_{m}^{i}(-1)^i(m-i)^n}{m!}m!i=0∑mCmi(−1)i(m−i)n S2(n,m)S_2(n,m)S2(n,m) |
| 4 | 不同 | 相同 | 允许空 | ∑i=0min(n,m)S2(n,i)\sum\limits_{i=0}^{min(n,m)}S_2(n,i)i=0∑min(n,m)S2(n,i) |
| 5 | 相同 | 不同 | 不允许空 | Cn−1m−1C_{n-1}^{m-1}Cn−1m−1 |
| 6 | 相同 | 不同 | 允许空 | Cn+m−1m−1C_{n+m-1}^{m-1}Cn+m−1m−1 |
| 7 | 相同 | 相同 | 不允许空 | G(x)=(x+x2+..)(x2+x4+..)..(xm+x2m+..)G(x)=(x+x^2+..)(x^2+x^4+..)..(x^m+x^{2m}+..)G(x)=(x+x2+..)(x2+x4+..)..(xm+x2m+..)G(x)的xn的系数G(x)的x^n的系数G(x)的xn的系数 |
| 8 | 相同 | 相同 | 允许空 | G(x)=1(1−x)(1−x2)..(1−xm)G(x)=\frac{1}{(1-x)(1-x^2)..(1-x^m)}G(x)=(1−x)(1−x2)..(1−xm)1G(x)的xn的系数G(x)的x^n的系数G(x)的xn的系数 |
赌徒破产模型
AAA有nnn元，BBB有mmm元，每局AAA赢的概率为ppp，BBB赢的概率为1−p1-p1−p，输方给赢方1元，求最终AAA或BBB赢得对方全部钱的概率。
其模型也等价于随机游走，坐标轴上AAA起初站在MMM点，有ppp的概率往右走一格，1−p1-p1−p的概率往左走一格 ，问其走到n+mn+mn+m（A赢）或者0（B赌徒赢）的概率 。
f0=0,fn+m=1f_0=0,f_{n+m}=1f0=0,fn+m=1
fi=(1−p)fi−1+pfi+1f_i=(1-p)f_{i-1}+pf_{i+1}fi=(1−p)fi−1+pfi+1
=>fi+1−fi=fi−fi−1=>f_{i+1}-f_i=f_i-f_{i-1}=>fi+1−fi=fi−fi−1
令fi=gifi+1=>gi=p1−(1−p)gi−1令f_i=g_if_{i+1}=>g_i=\frac{p}{1-(1-p)g_{i-1}}令fi=gifi+1=>gi=1−(1−p)gi−1p
=>fn=∏i=mn+m−1gi=>f_n=\prod\limits_{i=m}^{n+m-1}g_i=>fn=i=m∏n+m−1gi