一个与组合数、cf 653G(Move By Prime)相关的小定理

有$n$个物品，两两不相同。它们被分成两堆，左边那堆$x$个，右边那堆$n-x$个。从左边那堆拿出$p$个物品，从右边拿出$q$个物品，要求$p>q$。

求证：方案数为$\sum_{i=0}^{x-1}\binom{n}{i}$。

一定有人按了Ctrl+A

证明：

考虑一个长度为$n$的01串。

我们称它满足性质1，当且仅当其前$x$个字符中1的个数多于后面$n-x$个1的个数。

我们称它满足性质2，当且仅当其1的个数小于$x$。

我们在满足性质1的字符串$s_1$和满足性质2的字符串$s_2$之间建立一个一一映射，这样就可以证明满足性质1的字符串个数等于满足性质2的字符串个数，就可以证明本题啦。

怎么建立该映射呢?很简单，把$s_1$的前$x$个字符反转，即0变成1，1变成0，就可以对应到$s_2$；同理$s_2\to s_1$也是这个映射。

如果$s_1$的前$x$个字符有$a$个1，后面字符中有$b$个1，那么$a>b$，映射后$s_2$中$1$的个数为$x-a+b<x$。故$s_1$满足性质1$\Rightarrow s_2$满足性质2。

如果$s_2$的前$x$个字符有$a$个1，后面字符中有$b$个1，那么$a+b<x$，映射后$s_1$的前$x$个字符中有$x-a$个1，后面字符中有$b$个1，而$x-a>b$。故$s_2$满足性质2$\Rightarrow s_1$满足性质1。

Q.E.D