繰り返しとの組み合わせ – 定義

最初のアプローチ

数学では、 n 個の識別可能なオブジェクトからk 個のオブジェクトを選択し、各オブジェクトが繰り返し可能 (最大k回) である場合、繰り返される可能性のあるk 個のオブジェクトの順序付けされていないグループが得られます。しかし、このようなグループ化は集合ではないため、このように繰り返しを伴うk の組み合わせを定義することは数学では受け入れられません (実際、集合の拡張定義は要素の繰り返しを妨げるため、例: {1, 1, 2、2、2、3}={1、2、3})。

意味 ：

基数nの有限集合Eの繰り返しを伴うk組み合わせは、{0, 1, …, k } におけるEの写像fであり、次のようになります。

$$ {\sum_{x\in E}f(x)=k} $$

。

より正確には、 E ={ x ₁ , x ₂ , …, x _n } の場合、 f は次の条件を満たします。

$$ {f(x_1)+f(x_2)+\ldots+f(x_n)=k} $$

。

f は、 kからkまでのn個の要素の組み合わせとも呼ばれます。

気づいた：

このアプリケーションは、 Eの各要素について、それが選択された回数を示します。アプリケーションが値 0 をEの要素に関連付けた場合、その要素は選択されません。さらに、正確にk 個のオブジェクトを繰り返したい場合は、繰り返し回数の合計がkに等しくなければなりません。

例：

ドミノ ゲームでは、ドミノは集合E ={白、1、2、3、4、5、6} を繰り返す 2 つの組み合わせです。各ドミノは、 Eの各要素とその要素がドミノ上に出現する回数を関連付ける {0, 1, 2} のEのマップによって表すことができます。
したがって、白いドミノは次のように定義されるマップfによって表されます。

f (白)=2、 f (1)=0、 f (2)=0、 f (3)=0、 f (4)=0、 f (5)=0、 f (6)=0

そして白いドミノ、1 はアプリケーションfによって定義されます。

f (白)=1、 f (1)=1、 f (2)=0、 f (3)=0、 f (4)=0、 f (5)=0、 f (6)=0

繰り返しのある組み合わせの数

定理:

E を基数nの有限集合とします (

）。この場合、 Eの繰り返しによるk 個の組み合わせの集合K _k ( E ) は有限であり、そのカーディナリティは次と等しくなります。

$$ {\Gamma_n^k=C_{n+k-1}^k} $$

、

これは、 n + k -1 個の要素のk 個の組み合わせの数です。

$$ {\Gamma_n^k} $$

「ガンマnk」と読みます。

デモンストレーション:

繰り返しを伴う組み合わせは、有限集合を別の有限集合に写像するため、 K _k ( E ) は有限になります。 E ={ x ₁ , x ₂ , …, x _n } と仮定します。集合K _k ( E ) は、 x ₁を 0 に送信する組み合わせの集合K ‘ ( x _{1 が}現れない増加するkタプルで表されます) と集合

x _{1 を}ゼロ以外の自然数に送信する組み合わせ ( x _{1 が}少なくとも 1 回出現する増加するkタプルで表されます)。 K ‘の組み合わせをF = E \{ x ₁ } に制限することにより (これは、 Fの要素の増加するkタプルとみなすことになります)、 K ‘には、 n -1 個の要素がkからkに取得されるため、 。次の組み合わせのx ₁の値から 1 を引くことによって、 (これは、( k -1) タプルを取得するために、対応するkタプルから「 x ₁を削除する」ことに相当します)、この組み合わせを、 k -1 からk -1 までのn個の要素の繰り返しを含む組み合わせに変換します。 。逆に、 k -1 からk -1 までのn個の要素の組み合わせのx ₁の値に 1 を加算すると、次の要素が得られます。 。
したがって、要素は同じだけあります。 したがって、 n個の要素が繰り返される組み合わせのみがk -1 からk -1 までとられます。 。
書くことで

$$ {\rm{card}(K_k(E))=\rm{card}\left(\overline{K’}\cup K’\right)=\rm{card}(\overline{K’})+\rm{card}(K’)} $$

、

漸化式が得られます

$$ {\Gamma_n^k=\Gamma_n^{k-1}+\Gamma_{n-1}^k} $$

さらに、すべての自然数に対してゼロ以外のn があり、すべての自然数に対してk が存在します。

そして 、そして結果を推測します。

別のデモンストレーション:

集合Eの繰り返しを伴うk 個の組み合わせの集合と、 EにおけるF ={1, 2, …, k } の増加する適用の集合との間に全単射があることがわかりました。したがって、この最後の集合の基数を決定するだけで十分です。これについては後述します。

。

定理:

nとk を2 つの非ゼロの自然整数、 E を基数nの有限全順序集合、 F ={1, 2, …, k } とします。それで全体が

EにおけるFの増加する適用は有限であり、そのカーディナリティはEの繰り返しによるk 個の組み合わせの数であり、次と等しい。 。そしてこの枢機卿は注目されています 。

デモンストレーション:

一般性を失うことなく、 E ={1, 2, …, n }と仮定できます。マップx ↦ x – 1 を追加することにより、 EにおけるFの増加マップを、別の集合GにおけるFの厳密に増加するマップに変換します。
G ={1, 2, …, n + k -1} とすると、次のようになります。

FからGまで厳密に増加するマップのセット。 FからEへの増加するマップfに、次のように定義されるFからGへのマップg を関連付けましょう。

∀x∈F 、 g ( x )= f ( x ) + x -1

アプリケーションであることを確認するのは簡単です

$$ {\begin{matrix}\varphi : & \mathcal A_{c}(F, E) & \longrightarrow & \mathcal A_{sc}(F, G)\\& f & \longmapsto & (g: x\mapsto f(x)+x-1)\end{matrix}} $$

は明確に定義されています。そしてアプリ

$$ {\begin{matrix}\psi : & \mathcal A_{sc}(F, G) & \longrightarrow & \mathcal A_{c}(F, E)\\& f & \longmapsto & (g: x\mapsto f(x)-x+1)\end{matrix}} $$

はϕの逆写像です。

したがって、

。