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

r_64 posted @ 2016年5月11日 10:25 in 未分类 with tags 数学 , 917 阅读

有$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

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter