セットのサブセットのカウントに関するパスカルのルールは、セットに一意のエンティティが含まれている場合にうまく機能します。
セットに重複したアイテムが含まれている場合、このルールに変更はありますか?
たとえば、文字 A、B、C、D の組み合わせの数を見つけようとすると、1 + 4 + 6 + 4 + 1 (パスカルの三角形から) = 16、または 15 であることが簡単にわかります。 「文字を使用しない」エントリを削除します。
では、文字のセットが A、B、B、B、C、C、D の場合はどうなるでしょうか。手で計算すると、サブセットの合計は 1 + 4 + 8 + 11 + 11 + 8 + 4 + 1 = 48 であると判断できますが、これは私が知っている三角形には適合しません。
質問: セット内のエンティティの重複を考慮して、パスカルの三角形をどのように変更しますか?
セットにはユニークなアイテムのみが含まれます。重複がある場合、それはもはやセットではありません。
はい、セットを考慮したくない場合は、「要因」のアイデアを検討してください。要因数は次のとおりです。
p1^a1.p2^a2....pn^an
p1 が異なる素数である場合。AI がすべて 1 の場合、その数は 2^n です。一般に、答えは (a1+1)(a2+1)...(an+1) で、David Nehme が指摘しています。
ああ、手で答えたのは間違っていたことに注意してください。空のセットを数えたくない場合は、48 または 47 にする必要があります。
たとえば、3 つの要素を持つサブマルチセットの数を知りたいようです。これを計算するのは非常に難しく、すぐに難しくなります。アイデアは、そこにたどり着く方法のすべての組み合わせを合計したいということです。したがって、重複要素なしでそれを行う C(3,4) = 4 つの方法があります。B は、C(1,3) = 3 つの方法で 2 回繰り返すことができます。B は 1 つの方法で 3 回繰り返すことができます。また、C は C(1,3) = 3 つの方法で 2 回繰り返すことができます。合計11個。（あなたが手に入れた10は間違っていました。ごめんなさい。）
一般に、そのロジックを実行しようとするのは難しすぎます。それを追跡するより簡単な方法は、係数が必要な項を持ち、それを乗算する多項式を書き出すことです。パスカルの三角形の場合、これは簡単です。多項式は (1+x)^n です。（これをより効率的に計算するには、繰り返し二乗を使用できます。）あなたの場合、要素が2回繰り返される場合、（1 + x + x ^ 2）係数が得られます。3 回は (1+x+x^2+x^3) になります。したがって、特定の問題は次のように解決されます。
(1 + x) (1 + x + x^2 + x^3) (1 + x + x^2) (1 + x)
= (1 + 2x + 2x^2 + 2x^3 + x^4)(1 + 2x + 2x^2 + x^3)
= 1 + 2x + 2x^2 + x^3 +
2x + 4x^2 + 4x^3 + 2x^4 +
2x^2 + 4x^3 + 4x^4 + 2x^5 +
2x^3 + 4x^4 + 4x^5 + 2x^6 +
x^4 + 2x^5 + 2x^6 + x^7
= 1 + 4x + 8x^2 + 11x^3 + 11x^4 + 8x^5 + 4x^6 + x^7
これらの数値をコードで生成したい場合は、多項式のトリックを使用して思考とコードを整理します。(係数の配列を操作することになります。)
パスカルの三角形を変更する必要はまったくありません。C(k,n) を調べればわかります。基本的には、元の結果を分割して、同等の文字の順列を説明する必要があります。
たとえば、A B1 B2 C1 D1 == A B2 B1 C1 D1 の場合、C(5,5) を C(2,2) で割る必要があります。
重複がなければ (以前の投稿者が指摘したようにセット内に)、各要素はサブセット内またはサブセット外のいずれかです。したがって、2^n 個のサブセットがあります。重複の場合、(「マルチセット」で) 各要素が「サブマルチセット」に含まれる回数を考慮する必要があります。m_1,m_2...m_n が各要素の繰り返し回数を表す場合、サブバッグの数は (1+m_1) * (1+m_2) * ... (1+m_n) になります。
数学的集合には一意の項目が含まれていますが、実際のプログラミングの世界では、「集合」内の項目が重複するという問題に遭遇する可能性があります。例については、Lisp ユニオンに関するこのスレッドを参照してください。