作者LimSinE (r=e^theta)
看板IMO_Taiwan
标题[问题] 提供一道「类竞赛题」的题目
时间Tue Jan 4 18:43:20 2005
可能有见多识广的强者看过这一题，或是没看过但是能秒杀。
总之，请不吝赐教。这是别人问我的。
n为自然数，设有A(n;x1,x2,..,xn)种方法将1,2,3...,n，排成楼梯形，
每列各有x1,x2,...,xn个
即满足 x1>=x2>=...>=xn>=0，x1+x2+...+xn=n ---(*)
条件是右边的数比左面大，下面的数比上面大。
试证对所有n，Sigma((*)) A(n;x1,x2,...,xn)^2 = n!
以n=4为例：
x1=4，x2=x3=x4=0，只有1 2 3 4 一种排法，所以A(4;4,0,0,0)=1
x1=3、x2=1，x3=x4=0，有 1 2 3、1 3 4、2 3 4 三种排法故A(4;3,1,0,0)=3
4 2 3
x1=2、x2=2，x3=x4=0，有 1 2、1 3 两种排法，故A(4;2,2,0,0)=2
3 4 2 4
x1=2、x2=1、x3=1，x4=0，有 1 2、1 3、1 4 三种排法，故A(4;2,1,1,0)=3
3 2 2
4 4 3
x1=x2=x3=x4=1，只有1 一种排法，故A(4;1,1,1,1)=1
2
3
4
然後结论是 1^2 + 3^2 + 2^2 + 3^2 + 1^2 = 24 = 4!
--
r=e^theta
即使有改变，我始终如一。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.70.211.116