作者ckchi (飘)
看板Math
标题Re: 高中排列组合
时间Wed Mar 23 16:01:54 2011
※ 引述《me5119 (the end~~~)》之铭言：
: x+2y+3z=13
: 的非负整数解
: 可以用H来算吗?
: THX
因为 x 前面系数是 1
这题可以想成：2y+3z≦13的非负整数解
所以 z≦4
z=0 : y≦6 ,7种
z=1 : y≦5 ,6种
z=2 : y≦3 ,4种
z=3 : y≦2 ,3种
z=4 : y≦0 ,1种
因此共有 21 种
=========================================
虽然看起来好像只比土法练钢快一点，
没什麽大不了的。
但当 n 大了以後呢?
例如 x+2y+3z=100 的非负整数解有几种?
一样的，我们想成 2y+3z≦100
因此 z≦33
z=0 : 2y≦100, y≦50，有51种
z=1 : 2y≦ 97, y≦48，有49种
z=2 : 2y≦ 94, y≦47，有48种
z=3 : 2y≦ 91, y≦45，有46种
z=4 : 2y≦ 88, y≦44，有45种
z=5 : 2y≦ 85, y≦42，有43种
．
．
．
z=32: 2y≦ 4, y≦ 2，有 3种
z=33: 2y≦ 1, y≦ 0，有 1种
发现了吗?
其实可以拆成2个等差数列，
而且两个数列的公差都是3，
把两个数列的级数值算出来并相加就是答案。
结论：
x+py+qz=n 的非整数解的数量，
(p,q,n 皆为自然数，且 p < q)
可以想成 py+qz≦n 的非整数解的数量，
并进一步化成 p 个公差为 q 的级数和相加。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.116.89.133
1F：→ ckchi :如果有兴趣的话，可以试试下面两个例子： 03/23 16:07
2F：→ ckchi :x+2y+5z=40, x+3y+4z=40 03/23 16:08
3F：→ ckchi :应该能够帮助了解 03/23 16:08
4F：推 jameschou :cool 03/23 18:01
5F：推 attomahawk :推，有创意！ 03/23 23:23
6F：推 eqcolouring :好棒的想法! 03/24 00:17