r_64
分类
最新评论
最新留言
链接
RSS
功能
公告
计数器
111570
一个与组合数、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