因为上一篇像是讲故事不像是证明 有热心板友建议我再发一篇证明 我发现把想法转译成数学语言真的很困难 也更加敬佩板上那些很会写证明文的高手 证明目标:投掷n面骰子一个m次 每个面都至少出现一次的排列数为 Σ(k=0 to n)(-1)^k*C(n,k)(n-k)^m(原式) 令A(n,m,j)代表恰好使用j种点数的排列总数 其中(-1)^k*C(n,k)(n-k)^m=Σ(j=1 to n-k)C(n-j,k)(-1)^k*A(n,m,j) (这个等式後面再证明 现在先用) 原式=Σ(k=0 to n)(-1)^k*C(n,k)(n-k)^m=Σ(k=0 to n)Σ(j=1 to n-k)C(n-j,k)(-1)^k*A(n,m,j)=Σ(j=1 to n)Σ(k=0 to n-j)C(n-j,k)(-1)^k*A(n,m,j)=A(n,m,n) 也就是只剩下"恰好使用n种点数的排列总数"会保留下来 证明完成# 不知道这个证明是否算是一个完整有效的证明? 如果有错误或不足还请板上高手不吝指教 ----- 补充说明 1.Σ(k=0 to n-j)C(n-j,k)(-1)^k展开就会变成(1-1)^(n-j)=0(当j<n) 2.(-1)^k*C(n,k)(n-k)^m=Σ(j=1 to n-k)C(n-j,k)(-1)^k*A(n,m,j)的证明 这个等式虽然直觉可以想到 但是我不知道怎麽证明(要证明它比想到它要困难很多) 所以我学习了一种叫"双重计数法"的知识 首先 左右边的(-1)^k都拿掉 我们就只要证明 C(n,k)(n-k)^m=Σ(j=1 to n-k)C(n-j,k)A(n,m,j) 我们要数的东西是 一个配对(K,P)的数量 其中 K=一个恰好包含k个点数的集合 我们称为"禁止出现组" P=一个避开"禁止出现组" 且长度为m的排列 先看等式左边 先选K 从n中选取k的方法为C(n,k) 再选P 从剩下的n-k个点数中 选取长度为m的排列数为(n-k)^m 所以(K,P)的数量=C(n,k)(n-k)^m 再看等式右边 我们这次先选P 再选K A(n,m,j)代表恰好使用j种点数的排列总数 对於这样一个P 它可以跟多少个K 进行配对呢?答案当然是C(n-j,k) (K,P)的数量就是我们把它们全部加起来 Σ(j=1 to n-k)C(n-j,k)A(n,m,j) j的范围可以从1到n-k(因为P至少要留下k个空位给K） 因为左右二边数的都是一样的数字(K,P) 所以左右二边相等 得证 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.61.28.165 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1751087105.A.950.html 啊抱歉我没有写得很清楚 A(n,m,j) 代表的是：「投掷n面骰m次，其排列结果中，『恰好』只出现 j 种不同数字」 的方法总数。 例如:A(5,5,4) 是投掷一个5面骰子5次 所有恰好出现4种数字的排列总数 （例如 1,1,2,3,4 这种）。 A(5,5,1) 是所有只出现1种数字的排列总数（例如 1,1,1,1,1，总共有5种） 至於Σ(j=1 to n)Σ(k=0 to n-j)C(n-j,k)(-1)^k*A(n,m,j)=A(n,m,n) 假设我们n=5 m=5 外层j=1 那麽内层就是Σ(k=0 to 4)C(4,k)(-1)^k*A(5,5,1) =(1-4+6-4+1)A(5,5,1)=0 事实上 因为二项式定理 对於所有的1<=j<n 内层的求和式Σ(k=0 to n-j) C(n-j,k)(-1)^k 就等於(1-1)^(n-j) 结果永远是0 只有当外层的j=n的时候 内层Σ(k=0 to n-n)C(0,k)(-1)^k*A(n,m,n)=C(0,0)(-1)^0*A(n,m,n)=A(n,m,n) 希望这样的解释有比较清楚 感谢R大的提醒 我之前写得太简略了 ※ 编辑: oyasmy (61.61.28.165 台湾), 06/28/2025 17:19:17