Question

排列组合难题！

将7个相同的小球 任意装入编号分别为1~7的7个盒子中，共有几种不同的分装方法？
提示：7个小球可以全装入一个盒子，有的盒子可以为空。
有请高手指点。。。
我给自己提出这个问题，但没有想出解法！也许没那么简单。。。

Answer 1

由于小球是相同的，这里采用一种特殊的方法进行分组，成为“隔板法”。
具体意思如下，我们的目标是将7个小球分成最多7组，例如：
o |o o o||| o o ||o
算是一种方案（这种方案中有3个桶为空）。
那么这相当于是在8个缝隙中插入6个隔板（包括首尾处）
方法有8^6种。
这种方法只在小球无区别的情况下用。

追问

速度挺快的。。。

追答

比如1个球放入2个桶，那么有2个缝隙1个隔板，按上面有2^1=2种对的
2个球放入2个桶，那么有3个缝隙1个隔板，那么有3^1=3种也是对的啊？

我做过的…要点就是小球一样，不能按乘法原理

追问

O(∩_∩)O哈哈~我刚才是针对7^7说的。。。
另，隔板法貌似也不行，隔板法必须满足条件之一“所分成的每一组至少分得一个元素”！

追答

这样行不行呢，1个球放入2个桶允许空 转化成3个球2个桶每桶至少一个，
即2缝（去除首尾）1隔板不允许重复，共2C1=2种

2个球放入2个桶允许空 -> 4个球放入2个桶每桶至少一个，
即3缝1隔板不允许重复，共3C1=3种

楼主看看这个吧
例2. 求方程X+Y+Z=10的非负整数解的个数。

［分析］
注意到x、y、z可以为零，故上题解法中的限定“每空至多插一块隔板”就不成立了，怎么办呢？只要添加三个球，给x、y、z各一个球。这样原问题就转化为求X+Y+Z=13的正整数解的个数了，故解的个数为C122=66（个）。

［点评］
本例通过添加球数，将问题转化为如例1中的典型隔板法问题。

参考资料： http://hi.baidu.com/fenglinquan/blog/item/bdcf333b42e847e115cecbd9.html

追问

很有道理。。。正解就是C（13,6）=1716（种）。

Answer 2

1-7个盒子
1个满盒:7
1个盒子6个,余1个1盒:7!/6!*6 *7
1个盒子5个, 余2个1盒:7!/(5!2!)*6 *7
1个1盒:7!/(5!2!)*6!/(4!2!) *7
1个盒子4个,余3个1盒:7!/(3!4!)*6 *7
2个1盒:7!/(3!4!)*6*5 *7
1个盒子3个,余4个1盒(重复)
3个1盒:7!/(3!4!)*[4!/3! *6!/(2!4!)] *7
2个1盒7!/(3!4!)*[4!/(2!2!)*(6!/2!4!)] *7
1个盒子2个,余5个1盒(重复)
4个1盒(重复)
3个1盒(重复)
1个盒子1个,余6个1盒(重复)
5个1盒(重复)
4个1盒(重复)
3个1盒(重复)
共计:7!/6!*6*7+7!/(5!2!)*[6+6!/(4!2!)]*7+7!/(3!4!)[6+6*5+4!/3!*6!/(2!4!)+4!/(2!2!)*6!/(2!4!)]*7
=49*6+21*(6+15)*7+35*(6+30+4*15+6*15)*7
=294+3087+35*(36+90+60)*7=294+3087+45570=48951

追问

3Q 虽然看不懂。偶也这么想过，头大。。。
ps：“1个盒子6个,余1个1盒”应是42种吧？
“1个盒子1个,余6个1盒”----“1个盒子1个”不就是1种装法吗？

追答

6个空盒:7!/6!
5个空盒:(6,1) 7!/(5!2!)*2! (5,2)7!/(5!2!)*2! (4,3)7!/(5!2!) *2!
4个空盒 :(331)7!/(4!3!)*3!/2! (421)7!/(4!3!)*3!
3个空盒:(2221)7!/(3!4!)*4!/3!
2个空盒:(12211)7!/(2!5!)*5!/3!
1个空盒 (121111)7!/6! *6!/5!
合计：7!/6!+3*[7!/(5!2!)*2!]+*[7!/(4!3!)*3!/2!+7!/(4!3!)*3!]+7!/(3!4!)*4!/3!+7!/(2!5!)*5!/3!+7!/6!*6!/5!

=7+126+420+420+2520+42=3535

追问

请再仔细点O(∩_∩)O哈！如：
0个空盒；
4个空盒 :(331) (421) 外，还有 (223) （115）

追答

0个空盒:1
6个空盒:7!/6!
5个空盒:(6,1) 7!/(5!2!)*2! (5,2)7!/(5!2!)*2! (4,3)7!/(5!2!) *2!
4个空盒 :(331)7!/(4!3!)*3!/2! (421)7!/(4!3!)*3! (223)7!/(4!3!)*3!/2! (115)7!/(4!3!)*3!/2!
3个空盒:(2221)7!/(3!4!)*4!/3! (2131)7!/(3!4!)*4!/3!
2个空盒:(12211)7!/(2!5!)*5!/3!
1个空盒 (121111)7!/6! *6!/5!
合计：1+7!/6!+3*[7!/(5!2!)*2!]+*[7!/(4!3!)*3!/2!+7!/(4!3!)*3!+7!/(4!3!)*3!/2!+7!/(4!3!)*3!/2!]+7!/(3!4!)*4!/3!+7!/(3!4!)*4!/3! +7!/(2!5!)*5!/3!+7!/6!*6!/5!

追问

请再……仔细点O(∩_∩)O哈！再如：
3个空盒 ::(2221)（1123） 外，还有 （1114）

追答

笑纳!
0个空盒:1
6个空盒:7!/6!
5个空盒:(6,1) 7!/(5!2!)*2! (5,2)7!/(5!2!)*2! (4,3)7!/(5!2!) *2!
4个空盒 :(331)7!/(4!3!)*3!/2! (421)7!/(4!3!)*3! (223)7!/(4!3!)*3!/2! (115)7!/(4!3!)*3!/2!
3个空盒:(2221)7!/(3!4!)*4!/3! (2131)7!/(3!4!)*4!/2 (1114) 7!/(3!4!)*4!/3!
2个空盒:(12211)7!/(2!5!)*5!/3! (11311) 7!/(2!5!)*5!/4!
1个空盒 (121111)7!/6! *6!/5!
合计：1+7!/6!+3*[7!/(5!2!)*2!]+*[7!/(4!3!)*3!/2!+7!/(4!3!)*3!+7!/(4!3!)*3!/2!+7!/(4!3!)*3!/2!]+7!/(3!4!)*4!/3!+7!/(3!4!)*4!/2 +7!/(3!4!)*4!/3! +7!/(2!5!)*5!/3!+7!/(2!5!)*5!/4!+7!/6!*6!/5!

Answer 3

8^7
分析：
第一个盒子可以装入0--7个球；
第二个盒子可以装入0--7个球；
…
第七个盒子可以装入0--7个球；
由乘法原理，有8*8*...*8=8^7种方法。

追问

谢谢！貌似没这么多吧？8^7=2097152 ！

追答

1个盒子装7个球，余者为0：C(1,7)=7；
2个盒子装7个球，组合数（16，25，34）余者为0：3*p2*C(2,7)=126；
3个盒子装7个球，组合数（115，124，133，223）余者为0：
115,133,223的排列数分别为：C(1,3)+P2
124的排列数分别为：P3
从7个合盒中任选3个盒放这三组数的球：C(3,7)
{p3+3[C(1,3)+P2]}*C(3,7)=(6+15)35=735；

4个盒子装7个球，组合数（1114，1123，1222）余者为0：
1114,1222的排列数分别为：C(1,4)+C(1,2)
1123的排列数分别为：P2*C(1,3)+P2+2P2
从7个合盒中任选4个盒放这四组数的球：C(4,7)
{2[C(1,4)+C(1,2)]+[ P2*C(1,3)+P2+2P2]}*C(4,7)=(12+12)35=840；

5个盒子装7个球，组合数（11113，11122）余者为0：
11113的排列数分别为：C(1,5)
11122的排列数分别为：C(1,4)+C(1,2)
从7个合盒中任选5个盒放这四组数的球：C(5,7)
[C(1,5)+C(1,4)+C(1,2)]*C(5,7)=11*21=231；

6个盒子装7个球，组合数（111112）余者为0：
111112的排列数分别为：C(1,6)+C(1,2)
从7个合盒中任选6个盒放这四组数的球：C(6,7)
[C(1,6)+C(1,2)]*C(6,7)=56；

7个盒子装7个球，组合数（1111111）1；

综上共计7+126+735+840+231+56+1=1996

追问

“6个盒子装7个球”----可以理解为把 0 和 2 分配到7个盒子中吗？是p（7,2）=42种？

追答

你说的对，应将C(1,2)去掉
1个盒子装7个球，余者为0：C(1,7)=7；
2个盒子装7个球，组合数（16，25，34）余者为0：3*p2*C(2,7)=126；
3个盒子装7个球，组合数（115，124，133，223）余者为0：
115,133,223的排列数分别为：C(1,3)+P2
124的排列数分别为：P3
从7个合盒中任选3个盒放这三组数的球：C(3,7)
{p3+3[C(1,3)+P2]}*C(3,7)=(6+15)35=735；

4个盒子装7个球，组合数（1114，1123，1222）余者为0：
1114,1222的排列数分别为：C(1,4)
1123的排列数分别为：P2*C(1,3)+P2+2P2
从7个合盒中任选4个盒放这四组数的球：C(4,7)
{2[C(1,4)]+[ P2*C(1,3)+P2+2P2]}*C(4,7)=(8+12)35=700；

5个盒子装7个球，组合数（11113，11122）余者为0：
11113的排列数分别为：C(1,5)
11122的排列数分别为：C(1,4)
从7个合盒中任选5个盒放这四组数的球：C(5,7)
[C(1,5)+C(1,4)]*C(5,7)=9*21=189；

6个盒子装7个球，组合数（111112）余者为0：
111112的排列数分别为：C(1,6)
从7个合盒中任选6个盒放这四组数的球：C(6,7)
[C(1,6)]*C(6,7)=42；

7个盒子装7个球，组合数（1111111）1；

综上共计7+126+735+700+189+42+1=1800