非一意集合に対するパスカルの定理?

Question

パスカルの法則 セットに固有のエンティティが含まれている場合、セットのサブセットを数えることはうまく機能します。

セットに重複したアイテムが含まれている場合に備えて、このルールに変更はありますか?

たとえば、文字 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 しかし、これは私の知っている三角形に合致しません。

質問：セット内の重複エンティティを考慮に入れるためにパスカルの三角形を変更するにはどうすればよいでしょうか?

Answer 1

たとえば 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

これらの数値をコードで生成したい場合は、多項式トリックを使用して思考とコードを整理します。(係数の配列を操作することになります。)

Answer 2

セットには固有のアイテムのみが含まれます。重複がある場合、それはセットではなくなります。

Answer 3

はい、セットを検討したくない場合は、「要因」のアイデアを検討してください。いくつの要因があります：

p1^a1.p2^a2....pn^an

p1 が別個の素数である場合に持ちます。ai がすべて 1 の場合、その数は 2^n になります。David Nehme が指摘しているように、一般に、答えは (a1+1)(a2+1)...(an+1) です。

ああ、手書きの答えが間違っていたことに注意してください。空集合を数えたくない場合は 48 か、47 にする必要があります。

Answer 4

Pascal の Triangle を変更する必要はまったくありません。C(k,n) を調べれば分かるでしょう。基本的に、同等の文字の順列を考慮して元の結果を除算する必要があります。

たとえば、A B1 B2 C1 D1 == A B2 B1 C1 D1 であるため、C(5,5) を C(2,2) で割る必要があります。

Answer 5

重複がなければ (以前の投稿者が指摘したようにセット内で)、各要素はサブセット内またはサブセット外にあります。したがって、2^n 個のサブセットがあります。重複の場合、(「マルチセット」内で) 各要素が「サブマルチセット」内に存在する回数を考慮する必要があります。m_1,m_2...m_n が各要素の繰り返し回数を表す場合、サブバッグの数は (1+m_1) * (1+m_2) * ... となります。(1+m_n)。

Answer 6

数学的セットには一意の項目が含まれていますが、実際のプログラミングの世界では、「セット」内の項目が重複するという問題に遭遇する可能性があります。見る このスレッド Lisp ユニオンの例について説明します。