Теорема Паскаля для неуникальных множеств?

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 способами.B можно повторить 3 раза одним способом.И C может быть повторено дважды в C (1,3) = 3 способами.Всего 11 человек.(Ваши 10, которые вы получили от руки, были неправильными.Извини.)

В общем, пытаться следовать этой логике слишком сложно.Самый простой способ отслеживать это - выписать многочлен, коэффициенты которого имеют нужные вам члены, которые вы умножаете.Для треугольника Паскаля это несложно, многочлен равен (1+ x) ^ n.(Вы можете использовать повторное возведение в квадрат, чтобы вычислить это более эффективно.) В вашем случае, если элемент повторяется дважды, у вас будет коэффициент (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.В общем, ответ таков (a1 + 1) (a2 +1)...(an + 1), как отмечает Дэвид Неме.

О, и обратите внимание, что ваш ответ от руки был неправильным, он должен быть 48 или 47, если вы не хотите считать пустой набор.

Answer 4

Вам вообще не нужно изменять треугольник Паскаля.Изучите 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 для примера.