Three Competitions(One One Four Five One Four)

0.PreSpeak

This week,I went to Gensokyo to make bands with many many people.And we have held three bands competitions.And we played 《BanG Dream！Girls Band Party》 together.And Aya said that Bangbang would update Touhou Project,it's very good.

1.CorrectArticle

Let \(f(x)\) be the Bell Numbers.Let \(g(x)\) be the numbers of dividing a set \(\{1,2,\cdots,x\}\) into some sets that satisfies every set's size \(\geq 2\)。

这个怎么做？有结论 \(g(x)+g(x+1)=f(x)\)。考虑其组合意义。这其实是在证明 \(f(x)-g(x)=g(x+1)\)。即大小为 \(x\) 的集合的划分方案中含有大小为 \(1\) 的划分集合的划分方案数等于大小为 \(x+1\) 的集合的划分方案中不含有大小为 \(1\) 的划分集合的划分方案数。考虑建立一个双射。设 \(S\) 是一个划分方案，其中有大小为 \(1\) 的划分集合，并且总元素个数是 \(x\)。那么可以将其中所有的大小为 \(1\) 的划分集合合并，再在其中加上 \(x+1\)，得到 \(S'\)。发现 \(S'\) 中没有大小为 \(1\) 的划分集合，并且总元素个数是 \(x+1\)。这是一个单射。另一边的映射是简单的，不再赘述。（证明由 DeepSeek 提供。）

展开一下得到：

\(g(n)=\sum\limits_{i=1}^n f(n-i)(-1)^{i-1}+(-1)^n\)。

\(\begin{aligned}g(4) &= f(3)-g(3) \\&= f(3)-(f(2)-g(2)) \\&= f(3)-(f(2)-(f(1)-g(1)))\\&=f(3)-(f(2)-(f(1)-(f(0)-g(0))))\end{aligned}\)

有没有最后那一项修正取决于展不展开到 \(f(0)\)。

因为 \(f(0)\) 有系数 \((-1)^{n-1}\)，并且 \(f(0)=1\)，所以会直接和 \((-1)^n\) 消掉。

直接做。

2.Summary