コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

重複組合せ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
重複組み合わせから転送)

数学の一分野である組合せ論における重複組合せ(ちょうふくくみあわせ、じゅうふくくみあわせ、: combination with repetition, multi-choose; 重複選択、"Stars and bars")とは、取り出した並びは考慮しないが、(通常の(非重複)組合せと異なり)同じ元を複数取り出すことが許される「組合せ」を言う。例えば、(通常の)サイコロを10回投げるとき、各出目が何回目に振ったときに出たものか考えなければ、サイコロの出目の「組合せ」となるが、各面のうちには複数回現れるものが存在することになる(たとえば、出目 2 が1回、4 が3回、5 が2回、6 が4回であるときがその一例である)。

解釈と表示

[編集]

区別可能な n個の元からなる集合 E = {x1, x2, …, xn} から重複を許して k-元を選ぶ組合せ(k-重複組合せ)とは、E から連続して k 個の元を選ぶ方法であって、選んだ k 個の元の順番は考慮せず、かつ複数回同じ元を選ぶことが許されるというものである。これにより、重複する元をも含めて k 個の元からなる非順序組が得られる(この非順序組は、重複する元を持たないという集合の定義に反するから集合ではないが、その定義を拡張した多重集合となる)。そこで元 xi を選ぶ回数(零回でもいい)を f(xi) と書けば、k 個の元を選ぶことは制約条件 f(x1) + f(x2) + … + f(xn) = k で表せるから、

定義 ― 位数(濃度)n の有限集合 E に関する k-重複組合せとは、E から {0, 1, …, k} への写像 f: E → {0, 1, …, k} で条件

を満たすものを言う。

集合 E = {x1, x2, …, xn}全順序関係 x1 < x2 < … < xn を入れて考えるとき、E に関する k-重複組合せは、以下のような非減少(つまり広義の増大) k-順序組

に対応付けられる。逆に、E の元からなる非減少 k-組 (a1, a2, …, ak), つまり

a1a2 ≤ … ≤ ak

を満たすものは、E の各元に対してそれがこの k-組に現れる回数を割り当てることにより、写像 f: E → {0, 1, …, k} を定める。これが

f(x1) + f(x2) + … + f(xn) = k

を満たすことは明らかであり、従って fE に関する k-重複組合せである。

従って、E に関する k-重複組合せ全体の成す集合と {1, 2, …, k} から E への広義単調増大写像全体の成す集合との間に全単射が存在する。

重複組合せの総数

[編集]

定理[1] ― 正整数 n に対して n個の元からなる集合に関する k-重複組合せの総数を Hn
k
と書けば、

(すなわち、n + k − 1 個の元に関する k-組合せの総数)に等しい。

重複組合せの総数を計算する最も効果的で単純な方法は、非重複組合せの総数を計算する方法を用いることである(組合せ (数学)を参照)。実際、上で述べたように n個の元から重複を許して k個の元を選ぶ組合せの総数は、n + k − 1 個の元から k個の元を重複を許さずに選ぶ組合せの総数に等しい。

上昇階乗冪による表現
重複組合せの総数は、区別のある n個の箱に”区別のない” k枚のカードを入れる(1つの箱に複数枚入れてもよい)ときの場合の数である。まず、区別のある n個の箱に”区別のある” k枚のカードを入れる場合の数を求める。ただし箱の中のカードの相対的な位置も区別して数える。1枚目のカードの入れ方は n 通り、2枚目は1枚目のカードの上下どちらに入れるかの選択肢も増えるので入れ方は n + 1 通り、3枚目はさらに選択肢が増え n + 2 通り。結局 k 枚の入れ方の総数は上昇階乗冪 である。これは重複組合せの総数に k 枚のカードの順列の総数 k! をかけたものに等しいので、重複組合せの総数は である。(組合せの総数が下降階乗冪を用いて となるのと対をなしている。)

その他の重複組合せに同値な数え上げ

[編集]

Hn
k
多変数多項式に関する全次数 k の単位単項式(つまり係数 1 の単項式)の総数に等しい。

同様に Hn
k
シュヴァルツの定理(偏微分は微分する変数の順番に依らず等しい)の成立する Ck級の n変数函数に対する k階偏導函数の総数に等しい(順番を考慮する必要があるときには nk 通りである)。

出典

[編集]
  1. ^ Weisstein, Eric W. "Multichoose". mathworld.wolfram.com (英語).
  2. ^ a b De Boeck, ed (2010). Mathématique pour économistes et gestionnaires. https://books.google.co.jp/books?id=do0OLK5v-L8C&pg=PA21 
  3. ^ A. Bégyn; G. Connan; R. Leroy (2013). Dunod. ed. Mathématiques Méthodes et Exercices BCPST 1re année. 2. p. 226. https://books.google.co.jp/books?id=bXyoAAAAQBAJ&pg=226 
  4. ^ Démonstration tirée de Louquet, P.; Vogt, A. (1971). Armand Colin. ed. Probabilités, Combinatoire, Statistiques 
  5. ^ Dany-Jack Mercier (2004). Publibook. ed. L'épreuve d'exposé au CAPES mathématiques. p. 65. https://books.google.co.jp/books?id=3gZkWHnhOZoC&pg=PA65 

関連項目

[編集]

外部リンク

[編集]