[理工] [離散]組合-93交大

[Austin9 (奧斯丁)]

Use a combinatorial argument to prove that (3n) = n^3 + 6n(n) + 3(n)
                                            3              2      3

解答是
考慮3n個相異物取3個物品有(3n取3)種，將這3n分成三堆每堆有n個物品
由這三堆中取3個有下列幾種情況
1.每堆各取一個:有(n取1)^3 =n^3種
2.一堆取2個，一堆取一堆，一堆不取，有6(n取2)(n取1)=6n(n取2)種
      ^^^^^        ^^^^    ^^^^^
        (n取2)      n       這個不知道怎麼來？
3.一堆取3個，另一堆不取...有3(n取3)
     ^^^^         ^^^
    (n取3)    不知道怎麼來的？

問題如上，謝謝各位解惑。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 27.105.35.9
→ qwerty9876c:6n(cn取2)看成3!*(cn取1)*(cn取2)
→ qwerty9876c:有三堆 其中一堆取2個(cn取2) 其中一堆取1個(cn取1)
→ qwerty9876c:另外一堆不取 的情形有3!種 所以乘上6
→ qwerty9876c:第三個 :是指 有三堆 其中一堆取3個(cn取3)
→ qwerty9876c:另外2堆不取  總共的方法數有3種 所以乘上3
→ Austin9:了解了，謝謝！