作者oyasmy (oyasmy)
看板Math
标题[机统] 排容原理的证明?
时间Thu Jun 26 19:39:04 2025
我认为我已经完成排容原理的证明 但是GTP说我不算完成证明
所以我不确定我是否完成了证明
我要证明的是
n
Σ(-1)^kC(n,k)(n-k)^m=投掷一个n面骰子m次 每一面都至少出现一次的总方法数(式1)
k=0
但是我没有学过集合论和组合数学 所以WIKI上的证明我看不懂
我只好用土法炼钢的土炮方法自己证
我的方法是这样 上面那个Σ式子每经过一个k 它的值就会成为
n
Σ(纯j个数字所能构成的方法数)*系数
j=1
以n=5 m=5为例(m不用等於n 我取一样只是方便)
当k=0 就是+5^5=
+(纯1个数字所能构成的方法数)*1+(纯2个数字所能构成的方法数)*1
+(纯3个数字所能构成的方法数)*1+(纯4个数字所能构成的方法数)*1
+(纯5个数字所能构成的方法数)*1
然後对於每个给定的n,k,j我们有系数公式:C(n-j,k)(-1)^k
(这个公式的证明後面再补 现在先用)
所以对於上面(式1)的k=0------>n
我们的任一个j 它的系数会是
n-j
ΣC(n-j,k)(-1)^k
k=0
当j=n 上面这个式子的值是1
当1<=j<n 上面这个式子的值是0(二项式展开系数)
(我举n=5 j=1为例 系数会是+1-4+6-4+1=0)
也就是说 最後只有(纯n个数字所能构成的方法数)*1会留下来 其它全归0
证明完毕 请问我这样算是完成了证明吗?
-----
系数公式的证明:
观察(式1)我们发现k=我们每次操作会缺少的数字的数量
(例如n=5 k=1 (式1)做了-5*4^5 也就是我们这次会一次对4个数字进行操作 而k=5-4=1)
然後我们每次要选取包含那j个数字然後又少k个数字的排列数
那缺少的k个数字 我们是不是只能在剩下的n-j个数字里面找
所以系数公式:C(n-j,k)(-1)^k
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.61.28.165 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1750937946.A.61A.html
1F：→ R2003 : 你要不要重新回一篇，把证明过程写清楚? 06/27 06:01
2F：→ R2003 : 不然单靠叙述，没办法回答啊 06/27 06:01
3F：→ oyasmy : 啊 那可能要再多花时间 我再想一想 06/27 07:50
4F：→ yhliu : 你这不是在证明排容原理，而是试图直接证明你原先的 06/30 06:44
5F：→ yhliu : 问题。排容原理是关於 n 个事件联集机率的一个计算 06/30 06:46
6F：→ yhliu : 式，以 n=2 来说就是 P(A联B)=P(A)+P(B)-P(AB), 06/30 06:48
7F：→ yhliu : 以 m=3 来说是 P(A联B联C) = P(A)+P(B)+P(C)- 06/30 06:49
8F：→ yhliu : P(AB)-P(BC)-P(AC)+P(ABC)。而你原本的问题套用排容 06/30 06:51
9F：→ yhliu : 公式就是 1 - P(至少一面不出现) = 06/30 06:53
10F：→ yhliu : 1 - C(n,1)(1-1/n)^m + C(n,2)(1-2/n)^m - ... 06/30 06:54
11F：→ yhliu : 至於排容原理一般式证明，可以上述 n = 2 情形为基 06/30 06:56
12F：→ yhliu : 楚用数学归纳法进行，或利用指示函数(indicator)。 06/30 06:57