推 pikahacker:Out of the blue... 太可怕了 128.12.47.33 02/09
※ 引述《pikahacker (Beat Cal)》之銘言：
: Start with a row containing all positive integers. Then delete every mth
: column. Then replace the remaining entries by partial sums. Delete every
: (m-1)st column. Then replace with partial sums again, and so on. Show that
: the final result is a sequence of mth powers.
: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
: 1 3 6 10 16 23 31 40 51 63 76 90
: 1 4 10 26 49 80 131 194 270
: 1 5 31 80 211 405
: 1 32 243
對任意正整數w, 設袋子A中有w種顏色的球各無限多個, 且其中一種是白球, 沒有黑球,
則定義
D(w,x,y,z)=所有排序的m個球中, 滿足下列三個條件的可能數
1. 從A袋中拿m-z個球, 另外再拿z個黑球來排列
2. 其中白球和黑球以外的球不多於x個
3. 每一個黑球前面至少有y個白球
那麼討論可得
D(w,1,m-z-1,z)=wm+z+1
D(w,x,y,z)=D(w,x-1,y+1,z)+D(w,x,y+1,z-1) if x+y+z=m
D(w,x,y,0)=D(w,x-1,y+1,0)+D(w-1,x,0,m-x) if x+y=m
D(w,m,0,0)=w^m
於是用D()和上面的數列對應即得證
例如上面的 6 7
16 23
26 49
中, 6=D(2,1,4,0), 7=D(2,1,3,1), 16=D(2,2,3,0), 23=D(2,2,2,1),
26=D(2,3,2,0), 49=D(2,3,1,1)
其實我一開始是用類似生成函數的樣子想的, 不知道那樣是不是想起來比較方便一點
不過用生成函數的model很難描述...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.175.176.148
※ 編輯: darkseer 來自: 218.175.176.148 (02/06 21:40)