組合せ_(数学)
[Wikipedia|▼Menu]
□記事を途中から表示しています
[最初から表示]

E の k-組合せ全体の成す集合を ?k(E) と表す[3][4]とき、?k(E) の位数は有限であり、初等組合せ論においては Combination の頭文字を取って、nCk , Cn
k , nCk , Cn,k または C(n, k) のような記号で表す。ピエール・エリゴン(フランス語版)が1634年の『実用算術』でnCkの記号を定義した[5]。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} と書かれる。特に二項定理 ( 1 + x ) n = ∑ k = 0 n ( n k ) x k {\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}}

に係数として現れることは顕著であり、これにより ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} はふつう二項係数と呼ばれる。二項展開の係数として数 ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} を定義するものと考えれば k = n または k = 0 のとき ( n k ) = 1 {\displaystyle \textstyle {\binom {n}{k}}=1} , k > n のとき ( n k ) = 0 {\displaystyle \textstyle {\binom {n}{k}}=0} と考えるのは自然である。

実用上は個々の係数が具体的に ( n k ) = n × ( n − 1 ) × ⋯ × ( n − k + 1 ) k × ( k − 1 ) × ⋯ × 1 ( = P ( n , k ) k ! ) {\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \dotsb \times (n-k+1)}{k\times (k-1)\times \dotsb \times 1}}\left(={\frac {P(n,k)}{k!}}\right)}

で与えられることを利用するのが簡便である。この式の分子は k-順列(k-個のものを“並べる順番の違いを区別して”並べたもの)を作る総数を表し、分母はそれら k-個の並べ替えの総数が k! であることを表し、並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。
組合せの数え上げ

A は n-元集合で、a は A に属さない元、k は非負整数とする。このとき、A ∪ {a} の k + 1 個の元からなる部分集合は、A の k + 1 個の元からなる部分集合か、さもなくば単集合 {a} に A の k-元部分集合を併せたものであるから、 P k + 1 ( A ∪ { a } ) = P k + 1 ( A ) ∪ { X ∪ { a } ∣ X ∈ P k ( A ) } {\displaystyle {\mathcal {P}}_{k+1}(A\cup \{a\})={\mathcal {P}}_{k+1}(A)\cup \left\{X\cup \{a\}\mid X\in {\mathcal {P}}_{k}(A)\right\}}

と書ける。ただし、k > n のとき ?k(A) = ∅ である。(この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 ( n + 1 k + 1 ) = ( n k + 1 ) + ( n k ) {\displaystyle {\tbinom {n+1}{k+1}}={\tbinom {n}{k+1}}+{\tbinom {n}{k}}} に対応する)。
組合せの数の計算

n-元に対する k-組合せの総数を効率的に計算するために以下の等式が利用できる[6]。0 ? k ? n として: ( n k ) = ( n n − k ) , ( n + 1 k + 1 ) = n + 1 k + 1 ( n k ) , ( n 0 ) = 1. {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},\quad {\binom {n+1}{k+1}}={\frac {n+1}{k+1}}{\binom {n}{k}},\,{\binom {n}{0}}=1.}

最初の式は k ? n/2 なる場合に帰着するのに利用できるし、後の二つは ( n k ) = ( n − k + 1 ) 1 ⋅ ( n − k + 2 ) 2 ⋅ ⋯ ⋅ n k {\displaystyle {\binom {n}{k}}={\frac {(n-k+1)}{1}}\cdot {\frac {(n-k+2)}{2}}\cdot \dotsb \cdot {\frac {n}{k}}}


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:20 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef