记录一道含取整函数的组合恒等式

题目如下：

$$\sum_{k=0}^{n} 2^{k} \binom{n}{k} \binom{n-k}{\lfloor{\frac{n-k}{2}}\rfloor} = \binom{2n+1}{n}$$

起因是同学跑来问我，我想着毕竟比高中时组合数学还是有进步的就想着看看，结果卡了半天。主要一直不知道咋处理这取整函数。翻了翻常见的组合恒等式想着通过类似于$(a+(b+x))^{n}=((a+b)+x)^{n}$这样的展开式去处理结果还是没法处理这个取整函数。组合思路也没想到，后来就干脆搜了，倒是搜到了不少结果。虽然没做出来，但写这篇博客主要想着记录下并帮助自己多理解理解。

先从这题出发，这题是《102 Combinatorial Problems》的Advanced Problems的15题原题，原书给了两种解法，一种代数的，一种组合的，先说说组合的思路，我只能感慨这个思路十分的巧妙。

组合解法

考虑这样一个特殊的情形，一个班有$2n$名学生，其中$n$名女生$n$名男生，不妨设他们一男一女同桌，正好$n$桌。另外还有一名老师，共$2n+1$人。现在有$n$张票——随便什么票，不是票都行，重要的是分发这个行为或者说是挑选$n$个人给他票这种行为。

最显然的做法就是从$2n+1$个人里头挑$n$个人给票，所以是$\binom{2n+1}{n}$，这是一边，然后我们从另一边来做。

考虑这样一种给票的方式，$n$张票，在分发下去后会有这样一种情况，$n$组同桌，一些同桌两人只有一个有票，一些同桌两人都有，最后剩下一些同桌都没有，以及老师可能有或没有。所以可以构造这样一种奇妙的分法：先是从$n$组同桌中挑出$k$组出来，这$k$组每组只给一张，对应同桌两人只有一个有票的情况，此时分法是$\binom{n}{k}$，但要注意每组同桌内部还得分票，每组有$2$种情况，所以一共就是$2^{k}\binom{n}{k}$；然后剩下的$n-k$组，这些组是要么同桌两人都有，即该组两张票；要么同桌两人都没有，即该组零张票。注意我们此时只有$n-k$张票了，两个两个分，只能分给$\lfloor \frac{n-k}{2}\rfloor$组，从$n-k$组中挑出$\lfloor \frac{n-k}{2}\rfloor$组给他们每组两个人发票就有$\binom{n-k}{\lfloor \frac{n-k}{2}\rfloor}$种分发方法，最后剩下的$(n-k) - \lfloor \frac{n-k}{2}\rfloor$组自然就是没票的。最后需要注意的老师的票，很自然的如果$n-k$能被$2$整除，老师就拿不到票，如果不能，剩下那张票自然就是归老师的。所以根据这样的分法，我们知道我们一共有$\binom{n}{k}\binom{n-k}{\lfloor\frac{n-k}{2}\rfloor}$种分法。最后，这里的$k$是可以从$0$取到$n$，所以根据分类加法原理，我们需要做个求和。即总共的分法是$\sum_{k=0}^{n} 2^{k}\binom{n}{k}\binom{n-k}{\lfloor\frac{n-k}{2}\rfloor}$。

综上，我们用两种方法得到了同样的分法结果，数量相等，自然也就证明了该恒等式。

代数解法

这个解法倒是从构造二项式展开出发的，但相较于组合的做法显得没那么显然？

先是引入个记号方便描述，用$[x^{n}](p(x))$来简记多项式$p(x)$中的$x^{n}$项的系数。

然后就是构造二项式展开，但是这里的构造绕了一下，一般的是直接考虑多项式$(x+1)^{2n+1}$去找$n$次项系数，但是这里的解法却是去构造$p(x)=(x+1)^{2n}$，然后去找$n-1$次项和$n$次项这两项的系数，也就是

$$[x^{n-1}](p(x))+[x^{n}](p(x))=\binom{2n}{n-1}+\binom{2n}{n}=\binom{2n+1}{n}$$

这是一边，然后考虑另一边。

$$p(x)=(x+1)^{2n}=(x^2+2x+1)^{n}=\sum_{i+j+k=n}\frac{n!}{i!j!k!}(x^2)^{i}(2x)^{j}$$

然后就去做变形 $$\begin{aligned} p(x) &= \sum_{0 \leq i+j \leq n }\frac{n!}{i!j!(n-i-j)!} (x^2)^{i}(2x)^{j} \\\ &= \sum_{0 \leq i+j \leq n }\frac{n!}{i!j!(n-i-j)!} 2^{j}x^{2i+j} \\\ \end{aligned}$$

现在系数已经很明朗了，就去考虑同样的两项系数，去化简即可 $$ \begin{align*} [x^{n-1}](p(x)) + [x^n](p(x)) &= \sum_{\substack{0\leq i+j \leq n \\\ 2i+j=n-1}}\frac{n!}{i!j!(n-i-j)!}2^{j} + \sum_{\substack{0\leq i+j \leq n \\\ 2i+j=n}}\frac{n!}{i!j!(n-i-j)!}2^{j} \\\ &= \sum_{\substack{0\leq i+(n-2i)\leq n \\\ 0 \leq i,n-2i}}\frac{n!}{i!(n-2i)!i!}2^{n-2i} + \sum_{\substack{0\leq i+(n-2i-1)\leq n \\\ 0\leq i,n-2i-1}}\frac{n!}{i!(n-2i-1)!(i+1)!}2^{n-2i-1} \\\ &= \sum_{i=0}^{\lfloor \frac{n}{2}\rfloor}\binom{n}{2i}\binom{2i}{i}2^{n-2i}+\sum_{i=0}^{\lfloor \frac{n-1}{2}\rfloor}\binom{n}{2i+1}\binom{2i+1}{i}2^{n-2i-1} \end{align*} $$

这一步转换成带取整符号的组合数计数可谓是十分巧妙了，以及这里原书答案的求和下标起始计数应该错了？应该是从$0$开始而不是从$1$开始？接下来就是观察到$2i$和$2i+1$形如奇偶表示的形式，所以可以想到转换到奇偶求和

$$ \begin{align*} 原式 &= \sum_{\substack{s=0 \\\ s为偶数}}^{n}\binom{n}{s}\binom{s}{\lfloor \frac{s}{2}\rfloor}2^{n-s} + \sum_{\substack{s=0 \\\ s为奇数}}^{n}\binom{n}{s}\binom{s}{lfloor \frac{s}{2}\rfloor}2^{n-s} \\\ &= \sum_{s=0}^{n}\binom{n}{s}\binom{s}{\lfloor \frac{s}{2}\rfloor}2^{n-s} \end{align*} $$

到这一步就基本上出来了，那个莫名其妙的取整函数终于有了解释与归宿。最后只需要令$n-s=k$就可以得到

$$ \begin{align*} \binom{2n+1}{n} =[x^{n-1}](p(x))+[x^{n}](p(x))&=\sum_{k=0}^{n}\binom{n}{n-k}\binom{n-k}{\lfloor\frac{n-k}{2}\rfloor}2^{k} \\\ &= \sum_{k=0}{n}\binom{n}{k}\binom{n-k}{\lfloor\frac{n-k}{2}\rfloor}2^{k} \end{align*} $$

至此，原式得证。其实真把这个方法过一遍之后反而觉得这样做比组合方法来的简洁清晰了。不过两种方法无一例外的共性都是，很难想到这么去做。

更多

在搜这题的时候发现了更多一些内容，譬如说这道题其实有更强的形式在的，一是知乎上这篇专栏——组合恒等式方法——不过他的证明我目前没看懂，姑且先放一边吧。

然后在用英文搜索的时候找到了更多信息，先是找到了这个——A combinatorial identity with binomial coefficients and floor function.同样是更强的形式，但其中一个证明疑似用到了复分析？反正也没看懂，但靠着他我连接到了Prove using combinatorics $\sum_{k=0}^{n}2^{k}\binom{n}{k}\binom{n-k}{\lfloor \frac{n-k}{2}\rfloor}=\binom{2n+1}{n}$，这无疑就是原题了，接着在评论区导到了aops上的帖子Combinatorical Quality，在评论区末尾有人指出了这道题的出处，自此豁然开朗，接着有了这篇博客。

按理说到此还不算完，但更强形式的证明我暂且没动力去看了，留待下次吧。

说起来这是我第一篇数学相关的博客，可喜可贺。