此条目页介紹的是一个数学概念。
關於音樂表演的編制單位,請見「樂團 」。
關於一種可解釋為「組合」的組織型態,請見「辛迪加 」。
在組合數學 ,一個集 的元素的組合 (英語:Combination )是一個子集 。S 的一個k -組合是S 的一個有k個元素的子集。若兩個子集的元素完全相同並順序相異,它仍視為同一個組合,這是組合和排列 不同之處。
表示方式
从 n 个不同元素中取出 k 个元素的所有不同组合的个数,叫做从 n 个不同元素中取出 k 个元素的组合数,记做:
C
(
n
,
k
)
{\displaystyle C(n,k)}
、
n
C
k
{\displaystyle {}_{n}C_{k}}
、
n
C
k
{\displaystyle {}^{n}C_{k}}
、
C
k
n
{\displaystyle C_{k}^{n}}
(英语)、
C
n
k
{\displaystyle C_{n}^{k}}
(法语、罗马尼亚语、俄语、汉语(中國)[ 1] 、波兰语)。
理論與公式
从
n
{\displaystyle n}
个元素中取出
k
{\displaystyle k}
个元素,
k
{\displaystyle k}
个元素的组合數量为:
C
k
n
=
(
n
k
)
=
P
k
n
k
!
=
n
!
k
!
(
n
− − -->
k
)
!
{\displaystyle C_{k}^{n}={n \choose k}={\frac {P_{k}^{n}}{k!}}={\frac {n!}{k!(n-k)!}}}
以六合彩 為例。在六合彩中从49顆球中取出6顆球的组合數量为:
C
6
49
=
(
49
6
)
=
49
!
6
!
43
!
=
13983816
{\displaystyle C_{6}^{49}={49 \choose 6}={\frac {49!}{6!43!}}=13983816}
在集合中取出k項元素
在有五個元素中的集合中,取出3個元素,形成的子集合
重複組合理論與公式
从
n
{\displaystyle n}
个元素中取出
k
{\displaystyle k}
个元素,
k
{\displaystyle k}
個元素可以重複出現,這组合數量为:
H
k
n
=
C
n
− − -->
1
n
+
k
− − -->
1
{\displaystyle H_{k}^{n}=C_{n-1}^{n+k-1}}
以取色球為例,每種顏色的球有無限多顆,從8種色球中取出5顆球,好比是在5顆球間畫上分隔號 “|”代表球色的分布情形。例如第1種色球取1顆,第2種色球取2顆,第3種色球取2顆可以表示成:
球 |球球 |球球 | | | | |
可以理解为8类球每类取多少个,一起构成5个球。我们把5个球排成一排,用7个分隔线去隔开。如上图,表示含义:第1根线前表示第一类球取的个数,第1根和第2根线表示第二类球取的个数...第6第7根线前表示第七类球的个数,第7根后表示第八类球的个数。亦即問題是從(5+8-1)個位置中挑選出(8-1)個位置擺分隔號,這組合數量為:
H
5
8
=
C
8
− − -->
1
5
+
8
− − -->
1
=
C
7
12
=
12
!
7
!
5
!
=
792
{\displaystyle H_{5}^{8}=C_{8-1}^{5+8-1}=C_{7}^{12}={\frac {12!}{7!5!}}=792}
因為組合數量公式特性,重複組合轉換成組合有另一種公式為:
H
k
n
=
C
n
− − -->
1
n
+
k
− − -->
1
=
(
n
+
k
− − -->
1
)
!
k
!
(
n
− − -->
1
)
!
=
C
k
n
+
k
− − -->
1
{\displaystyle H_{k}^{n}=C_{n-1}^{n+k-1}={\frac {(n+k-1)!}{k!(n-1)!}}=C_{k}^{n+k-1}}
另外
H
k
n
{\displaystyle H_{k}^{n}}
也可以記為
F
k
n
{\displaystyle F_{k}^{n}}
[ 2] 或
(
(
n
k
)
)
{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)}
F
k
n
=
H
k
n
{\displaystyle F_{k}^{n}=H_{k}^{n}}
(
(
n
k
)
)
=
H
k
n
{\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=H_{k}^{n}}
在
C
k
n
{\displaystyle C_{k}^{n}}
的定義中,由於它有意義的範圍必須是滿足條件
n
≥ ≥ -->
k
≥ ≥ -->
1
{\displaystyle n\geq k\geq 1}
,所以其他範圍必須另外定義,我們有:
C
k
n
=
{
1
,
k
=
0
0
,
(
0
≤ ≤ -->
n
<
k
)
∨ ∨ -->
(
k
<
0
≤ ≤ -->
n
)
(
− − -->
1
)
k
C
k
|
n
|
+
k
− − -->
1
,
(
n
<
0
)
∧ ∧ -->
(
k
>
0
)
(
− − -->
1
)
n
+
k
C
|
n
|
− − -->
1
|
k
|
− − -->
1
,
(
n
<
0
)
∧ ∧ -->
(
k
<
0
)
{\displaystyle C_{k}^{n}={\begin{cases}1,&k=0\\0,&(0\leq n<k)\lor (k<0\leq n)\\(-1)^{k}C_{k}^{|n|+k-1},&(n<0)\land (k>0)\\(-1)^{n+k}C_{|n|-1}^{|k|-1},&(n<0)\land (k<0)\end{cases}}}
[ 3]
演算範例
組合 C
迴圈法
/***********************/
/** This is C++ code. **/
/** Comb Example **/
/***********************/
#include <iostream>
using namespace std ;
bool next_comb ( int * comb , const int n , const int k ) {
int i = k - 1 ;
const int e = n - k ;
do
comb [ i ] ++ ;
while ( comb [ i ] > e + i && i -- );
if ( comb [ 0 ] > e )
return 0 ;
while ( ++ i < k )
comb [ i ] = comb [ i - 1 ] + 1 ;
return 1 ;
}
int main () {
int n , k ;
cout << "comb(n,k):" << endl ;
cin >> n >> k ;
if ( n < k || k <= 0 )
return 0 ;
int * comb = new int [ k ];
for ( int i = 0 ; i < k ; i ++ )
comb [ i ] = i ;
do
for ( int i = 0 ; i < k ; cout << (( ++ i < k ) ? ',' : '\n' ))
cout << comb [ i ] + 1 ;
while ( next_comb ( comb , n , k ));
delete [] comb ;
return 0 ;
}
遞迴法
#include <iostream>
#include <cstdio>
using namespace std ;
namespace comb {
int n , k ;
int arr [ 12 ];
int count ;
bool arrsame ( int site ) {
if ( site > 0 && arr [ site - 1 ] >= arr [ site ])
return 0 ;
return 1 ;
}
inline void arrprint () {
for ( int i = 0 ; i < k ; i ++ )
printf ( "%3d" , arr [ i ]);
puts ( "" );
count ++ ;
}
void calculate ( int now ) {
if ( now == k ) {
arrprint ();
return ;
}
for ( int i = 0 ; i < n ; i ++ ) {
arr [ now ] = i ;
if ( arrsame ( now )) {
calculate ( now + 1 );
}
}
}
inline void run ( int nn , int kk ) {
n = nn , k = kk ;
count = 0 ;
if ( k < 12 && n >= k && k > 0 )
calculate ( 0 );
if ( count )
printf ( " \n %d combination. \n\n " , count );
else
puts ( "Input error!" );
}
}
int main () {
int n , k ;
while ( scanf ( "%d%d" , & n , & k ) != EOF ) {
comb :: run ( n , k );
fflush ( stdout );
}
return 0 ;
}
重複組合 H
迴圈法
/***********************/
/** This is C++ code. **/
/** ReComb Example **/
/***********************/
#include <iostream>
using namespace std ;
bool next_re_comb ( int * recomb , const int n , const int k ) {
int i = k - 1 ;
do
recomb [ i ] ++ ;
while ( recomb [ i ] > n - 1 && i -- );
if ( recomb [ 0 ] > n - 1 )
return 0 ;
while ( ++ i < k )
recomb [ i ] = recomb [ i - 1 ];
return 1 ;
}
int main () {
int n , k ;
cout << "recomb(n,k):" << endl ;
cin >> n >> k ;
if ( n <= 0 || k <= 0 )
return 0 ;
int * recomb = new int [ k ];
for ( int i = 0 ; i < k ; i ++ )
recomb [ i ] = 0 ;
do
for ( int i = 0 ; i < k ; cout << (( ++ i < k ) ? ',' : '\n' ))
cout << recomb [ i ] + 1 ;
while ( next_re_comb ( recomb , n , k ));
delete [] recomb ;
return 0 ;
}
遞迴法
#include <iostream>
#include <cstdio>
using namespace std ;
namespace re_comb {
int n , k ;
int arr [ 12 ];
int count ;
bool arrsame ( int site ) {
if ( site > 0 && arr [ site - 1 ] > arr [ site ])
return 0 ;
return 1 ;
}
inline void arrprint () {
for ( int i = 0 ; i < k ; i ++ )
printf ( "%3d" , arr [ i ]);
puts ( "" );
count ++ ;
}
void calculate ( int now ) {
if ( now == k ) {
arrprint ();
return ;
}
for ( int i = 0 ; i < n ; i ++ ) {
arr [ now ] = i ;
if ( arrsame ( now )) {
calculate ( now + 1 );
}
}
}
inline void run ( int nn , int kk ) {
n = nn , k = kk ;
count = 0 ;
if ( k < 12 && k > 0 )
calculate ( 0 );
if ( count )
printf ( " \n %d combination. \n\n " , count );
else
puts ( "Input error!" );
}
}
int main () {
int n , k ;
while ( scanf ( "%d%d" , & n , & k ) != EOF ) {
re_comb :: run ( n , k );
fflush ( stdout );
}
return 0 ;
}
推广
组合数可以推广到多分类的情形 ,我们将n个物品分为m份,每份的个数分别为:
k
1
,
k
2
⋯ ⋯ -->
k
m
{\displaystyle k_{1},k_{2}\cdots k_{m}}
个,那么,总的分类数为
(
n
k
1
,
k
2
,
⋯ ⋯ -->
,
k
m
)
=
n
!
k
1
!
k
2
!
⋯ ⋯ -->
k
m
!
{\displaystyle {\binom {n}{k_{1},k_{2},\cdots ,k_{m}}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{m}!}}}
参见
參考文獻
^ 普通高中教科书 数学 选择性必修第三册(A版) . 北京市海淀区中关村南大街17号院1号楼: 人民教育出版社. : 23 [2024-03-30 ] . ISBN 978-7-107-34598-2 .
^ 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392
^ 3.0 3.1 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392
外部链接