nCr, nPr, H

nCr 總是記不入腦
所以寫一寫



先由 nPr 開始

nPr 就是 n個排r個出來
例: 10個東西選3個,有幾種排法?
(1,2,3) 和 (3,2,1) 視為不同排法

10個先選1個
9個裏選1個
8個裏選1個

= 720

nPr = n! / (n-r)!
上面的例子中 7! 的部分就對消掉了

之後就是 nCr

nCr n個 choose(選)r個,求不同數量的排法
nCr 的假設和 nPr 相反, (1,2,3)和(2,3,1)為相同排法
計算上只要把 r! 種排法除去就可以

nCr = nPr / r!

10C3 = 720 / 3!
= 120

留意一下 10C3 和 10C7 是一樣的,也就是說 nCr = nC(n-r)

5C2 = 20 / 2! = 10
5C3 = 60 / 3! = 10


最後就是 H 的部分
H 和 nCr,nPr 好像有一點關係

有6件相同物件,把它們分成3批,1批中可以沒有物件,但6個都要分配好
那麼有幾種分法?

把6件物件叫 aaaaaa
分批付號用 | , 分3批就有2個 ||

分法1: aaa|a|aa
這樣就分了 (3,1,2)

分法2: ||aaaaaa
這是 (0,0,6)

問題就簡化成有8格 (6個a和2個|), 2個|有多少種排法 (或者是有8個a, 隨便換2個做|,有多少個排法)
這就是 8C2 = 28
留意 nHr 是指出有多少項分配, 如(3,1,2),(1,2,3)等

nHr = (n+r-1)Cr
別忘了 -1, 因為分3堆只要2個|就好, 分r個也只是要 r-1 個 |

例題: a + b + c + d = 13
假設全部數字皆為正數, (a,b,c,d)有幾種排法?

這個問題可以簡化為有13個東西 (@), 要分4批 (+號作分隔)

@@@@@@@@@@@@@+++
答案為 16C3 = 560

如果全部數字都要 >= 2, 就乾脆把題目改成 a + b + c + d = 5就好
更奇怪的要求: 只有d 必須 >= 5, 看來只有算 a + b + c = 0, a + b + c = 1, ... , a + b + c = 8 的總和了 (2C2, 3C2, 4C2, ... ,10C2) Orz

另一計法
d >= 5 可以視為固定了 +@@@@@
把這串東西當作☆
題目又變成
@@@@@@@@++☆ 了 (8個@)
☆的條件是必須出現在最後一個+後

最後一個+能出現在...第2至第10格

+在第2格的話(++...,前1格為 1C1),☆能插在第3至第11格,共9格 (= 9 * 1)
+在第3格的話(前2格為 2C1),☆能插在第4至第11格,共8格 (= 8 * 2)
...
+在第10格的話(...+☆,前9格為 9C1),☆能插在第11格,共1格 (= 1 * 9)

9+16+21+24+25+24+21+16+9 = 165

結果是165
這條變成了三角形數題

另一題目
a + b + c = 7
假設全部數字皆為正數,其中一數必須 >= 4, (a,b,c)有幾種排法?
人手計算後發現答案是30

同樣做法

☆ = @@@@ , 留意沒有+
全部就是 @@@++☆,共6格

要算的是 ++及☆ 的排列

先算++☆的可能排列
3C2 = 3
++☆
+☆+
☆++

之後就要在6格內塞任意3格@
要留意的是@@☆+ , @☆@+, 等都是一樣, ☆在不同的+之間才算是不同排列
所以現在只算 @@@++ 的排列
5C2 = 10

互乘後得30


留意此做法只適合 >=4,5,6,7
如果是>=0,1,2,3 ... 時,組合會重複而出錯
例 >=3
@@@@++中會有　6C2 = 15個組合
(4,0,0),(0,4,0),(0,0,4), ... ,(1,3,0), ...
每個☆可以插入其中一個位
(☆,,) (,☆,) (,,☆)

某15個都在第1個數字 +3
這15個就變成 (7,0,0),(3,4,0),(3,0,4), ... ,(4,3,0), ...

某15個在第2個數字 +3
糟糕了
(4,3,0),(0,7,0),(0,3,4)
組合開始重複
只有每次+4或以上才能確保每次加入☆時都是獨特的