2022.6.4 组合数学 $\text{Combinatorial mathematics}$

\(\text{Content: Stirling I & II, the Catalans}\)

\(\rm I-\) \(\rm Stirling\;I\)

\(\text{Definition}:S_1(n,m)=\text{The total ways to divide }n\text{ elements into }m\text{ Circular arrays.(arrays aren't empty)}\)

\(\text{Solution(dp):}S_1(n,m)=\begin{cases}S_1(n-1,m-1)\to\text{Open up a new array}\\S_1(n-1,m)\cdot(n-1)\to\text{insert an element in one of the previous arrays}\end{cases}\)
\(\Rightarrow S_1(n,m)=S_1(n-1,m-1)+(n-1)\cdot S_1(n-1,m)\)

\(\text{Ex. Stirling I & Generating function:}\)
\(F_n(x)=\prod_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!}=\sum_{i=0}^na_ix^i\)
\(\Rightarrow S_1(n,i)=a_i\)

\(\text{(Some problems with Circular array}\Rightarrow\text{Stirling I)}\)

\(\rm II-\) \(\rm Stirling\;II\)

\(\text{Definition}:S_2(n,m)=\text{The total ways to put }n\text{ SAME balls into }m\text{ SAME boxes.(boxes aren't empty)}\)

\(O(n^2)\text{ Solution(dp):}S_2(n,m)=\begin{cases}S_2(n-1,m-1)\to\text{Occupy a new box}\\S_2(n-1,m)\cdot m\to\text{randomly put a ball into one of the previous boxes}\end{cases}\)
\(\Rightarrow S_2(n,m)=S_2(n-1,m-1)+m\cdot S_2(n-1,m)\)

\(O(m\log m)\text{ Solution:}S_2=\dfrac{1}{m!}\sum_{k=0}^m(-1)^kC_m^k(m-k)^n\)

\(\text{Some basic conclusion:}S_2(n,1)=1,\;S_2(n-1,2)=2^{n-1}-1,\;S_2(n,n-1)=C_n^2(?????)\)

\(\text{Ex. The Bells }\{B\}:B_n=\sum_{i=0}^{n}S(n,i)\)
\(\Rightarrow B=\{1,1,2,5,15,52,...\}\)

\(\text{The Bell Triangle (I call it }P\rm)\)
\(B_i=P_{i,i}\)
\(P_{i,1}=P_{i-1,i-1}=B_{i-1}\)
\(P_{i,j}=P_{i,j-1}+P_{i-1,j-1}\)

\(\rm III-\) \(\text{The Catalans }\{H\}\)

\(\text{Indication/sign: }cnt_{\rm type\;1}(k)
\(\text{Definition: }H_n=\dfrac{C_{2n}^n}{n+1}(=\dfrac{H_{n-1}(4n-2)}{n+1})\)
\(\text{property:}H_n=\sum_{i=1}^nH_{i-1}\cdot H_{n-i}\qquad(n\ge2),H_0=H_1=1\)
\(\text{Classical Catalan Problems: Stack IN & OUT, 5\$ & 10\$ money exchange,Binary tree counting,...}\)

\(\text{Ex. Ascending/Descending power polynomial}\)

\(\text{The Descending One: }\)\(x^{\underline{m}}=\prod_{i=0}^{m-1}(x-i)\)
\(\text{The Ascending One: }\;\;\)\(x^{\overline{m}}=\prod_{i=0}^{m-1}(x-i)\)

\(\text{Common Polynomial}\Leftrightarrow\text{Descending Power Polynomial:}\)
\(f(x)=\sum_{i=0}^na_ix^i=\sum_{i=0}^nb_ix^{\underline i}\)
\(\Rightarrow x^n=\sum_{i=1}^nS_2(n,i)x^{\underline i}\)