關於nCr的問題

設有n個物件, 隨機抽出r個物件

我們定義有nPr種排列及nCr種組合



設有如下r個空位:

_ _ _ _ _ ...... _

抽出第1個物件, 共有n個機會, 餘下(n-1)個物件

抽出第2個物件, 共有(n-1)個機會, 餘下(n-2)個物件

抽出第3個物件, 共有(n-2)個機會, 餘下(n-3)個物件

...如此類推, 直到:

抽出第r個(最後一個)物件, 共有[n-(r+1)]個機會, 餘下(n-r)個物件

所以共有n(n-1)(n-2)...[n-(r+1)]=n!/(n-r)!種排列

即nPr=n!/(n-r)!

所以若把r個物件全部作排列, 則會有rPr=r!種排列

而n個物件隨機抽出r個物件的所以排列, 當中已包含所有可能的排列

其中也包含r個一樣物件不同排列的情況, 其排列數剛好為rPr=r!

所以組合數nCr = nPr/r! = n! / [r!(n-r)!]

2007-01-13 20:39:30 補充：
有點難明, 舉例說明一下:有3個物件1,2,3, 隨機抽出2個物件作排列即有3P2=3!/(3-2)!=6種排列:12,13,21,23,31,32根據排列數的公式, 把2個物件全部作排列, 有2P2=2種排列而上述1,2,3的排列中：12,2113,3123,32即為2個一樣物件不同排列的情況, 其排列數剛好為2所以組合數3C2=6/2=3

Have to use something called permutation number, which is denoted by nPr.
It involves arranging lining up objects. For example, if you want to put 2 objects in order, there are 2 ways. (AB, BA) If you want to put 3 objects in order, you can do it with 6 different ways (ABC, ACB, BAC, BCA, CAB, CBA). We deduce by expermenting:
2 objects =2 ways
3 objects =6 ways
4 objects= 24 ways
5 objects = 120 ways
...
It is not difficult to spot that
n objects =n! ways
Now, if there is 3 objects, and you are going to pick 2 and put then in order, you can pick AB (2 ways to arrange), pick BC (another 2 ways to arrange) or pick AC (another 2 ways to arrange). There are 6 ways in total, that is 3P2 (in 3 objects, picking two and line them up). But for bigger numbers: If you choose all n objects and line them up, then there are n! ways, if you choose (n-1) objects from n objects, there are (n-1)! ways and so on. Until after r times, you pick (n-r+1) objects and line them up.
Therefore, formula of nPr=n(n-1)(n-2).... (n-r+1) with r factors= [n(n-1)(n-2).... (n-r+1)(n-r)(n-r-1)...1]/[n-r)(n-r-1)...1]=n!/(n-r)!
= choosing among r objects among n objects and arrange them in order.
Now, consider the relationship between permutation no.s (nPr) and combination no.s. (nCr). Permutation involves choosing objects and lining them up, whereas combinaion just involve choosing. Bear in mind that arranging can be number of ways to arrage r objects can be denoted by r!. Meaning nCr *r! =nPr, nCr= nPr/r! = [n!/(n-r)!]/r!= n!/[(n-r)!r!]