由1到n有多少個組合

問：
由1到n有多少個組合
假如有n個數字由1, 2, 3, 4..., n-2, n-1 至n，那麼由1個數字到n個數字的組合總共有多少個？
註：每個組合中同一個數字只可出現一次；1和2的組合及2和1的組合只作一個組合計算。

答：
組合總共有　Tn = nC1 + nC2 + ... + nCn-1 + nCn　
當 n = 1 時　 T1 = 1 = 1
當 n = 2 時　 T2 = 3 = 2 + 1
當 n = 3 時　 T3 = 7 = 3 + 3 + 1
當 n = 4 時　 T4 = 15 = 4 + 6 + 4 + 1
當 n = 5 時　 T5 = 31 = 5 + 10 + 10 + 5 + 1
到了這裡，你應該發現另一個數列變化的規律，就是　Tn = 2n - 1　
當 n = 1 時　 T1 = 1 = 21 - 1
當 n = 2 時　 T2 = 3 = 22 - 1
當 n = 3 時　 T3 = 7 = 23 - 1
當 n = 4 時　 T4 = 15 = 24 - 1
當 n = 5 時　 T5 = 31 = 25 - 1
所以n個數字的組合總共有　2n - 1　個
圖片參考：http://myweb.hinet.net/home14/fugar/webimg/uploads/smil3dbd4daabd491.gif


註：這種數型組合，在生活上最常出現在賽馬，當你買過關時，常聽到 3 串 7 ，4 串 15 ，5 串 31 ，6 串 63 等，都與這種組合有關。

http://popeyefu.3forum.hk/redirect.php?tid=1959&goto=lastpost#lastpost
由andrew發表:
沒有證明的回答也成最佳回答?

有n咁多個

這問題可看作是由n個元素組成的集合,其子集個數有多少
子集個數有:2^n(包括nC0=1,即一個元素都不取所組成的集合(空集))
非空子集個數有:2^n-1(空集除外的所有子集,即你所發問的問題答案)
真子集個數有:2^n-1(本身除外的所有子集,即不包括nCn=1)
非空真子集個數有:2^n-2(本身及空集除外的所有子集)

YuK 和 FFU 都有正確的答案。

YuK 只是說出了答案，並沒有解釋，而FFU則用了比較Algebraic的方式，對於不熟悉nCr的人，這個答案就比較難理解。

這裏，我想用一個比較易懂的方式說明一下。

想像這個表就是那 7 個組合, x 和 o 分別表示要和不要

1 2 3
o x x (1)
x o x (2)
x x o (3)
o o x (1, 2)
o x o (1, 3)
x o o (2, 3)
o o o (1, 2, 3)

把 x 和 o 分別變 0 和 1, 這個表就變了

1 2 3
1 0 0 (1)
0 1 0 (2)
0 0 1 (3)
1 1 0 (1, 2)
1 0 1 (1, 3)
0 1 1 (2, 3)
1 1 1 (1, 2, 3)

有甚麼發現？很像二進數吧，排序一下：

1 2 3
0 0 1 (3)
0 1 0 (2)
0 1 1 (2, 3)
1 0 0 (1)
1 0 1 (1, 3)
1 1 0 (1, 2)
1 1 1 (1, 2, 3)

這個如果把二進數變成了十進數，就是 1 ~ 7 了。想想看，如果 n = 4 呢？這個情況裏就是由 0 0 0 1 一直數到 1 1 1 1, 十進數來說就是1 ~ 15了。這就可以很圖像化地解釋到2^n - 1。如果不明白為何2進制裏n 個 1就是2^n - 1，可以想像n 個1是 1 0 .. 0(n 個) - 1

example 1 1 1 1 = 1 0 0 0 0 - 1

FFU也沒有做錯。但它沒有簡化他的答案。因為他給出來的公式和2^n - 1是一模一樣的。要明白他的公式為何一樣，要用到他提及的binomial theorem。

(1 + x)^n = nC0 + nC1x + nC2x^2 + ... + nCn x^n

在上式: sub x = 1

(1 + 1)^n = nC0 + nC1 + nC2 + ... + nCn

所以 2^n = nC0 + nC1 + nC2 + ... + nCn
= 1 + nC1 + nC2 + ... + nCn

nC1 + nC2 + ... + nCn = 2^n - 1

無疑沒錯，但是一個複雜的答案。

2007-06-30 23:12:11 補充：
沒有證明哦～！
用Binomial Theorem這個應該不難吧。

首先你例題錯了, 還有一個組合是1,3
即是共有7個組合

我們設有數字n個, 數值我們不用理會, 可以把組合的數字組合成一條公式為
nC1 + nC2 + ... + nC(n-1) + nCn
這條公式的總和便是這n個數字的組合數.
例如有數4個, 我們利用公式, 求出
4C1 + 4C2 + 4C3 + 4C4 = 4 + 6 + 4 + 1 = 15個組合.
故此我們得出有4個數字便有15個組合.
証明
1, 2, 3, 4, 1+2,
1+3, 1+4, 2+3, 3+4, 2+4,
1+2+3, 1+2+4, 1+3+4, 2+3+4, 1+2+3+4

我覺得係n咁多個@@