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

Question

Правило Паскаля при подсчете подмножеств набора прекрасно работает, когда набор содержит уникальные сущности.

Есть ли изменение в этом правиле для случаев, когда набор содержит повторяющиеся элементы?

Например, когда я пытаюсь найти количество комбинаций букв A, B, C, D, легко увидеть, что это 1 + 4 + 6 + 4 + 1 (из треугольника Паскаля) = 16, или 15, если я удалю запись "не использовать ни одну из букв".

Теперь, что если набор букв А, В, В, В, С, С, D? Вычисляя вручную, я могу определить, что сумма подмножеств равна: 1 + 4 + 8 + 11 + 11 + 8 + 4 + 1 = 48, но это не соответствует Треугольнику, который я знаю.

Вопрос: Как вы модифицируете треугольник Паскаля, чтобы учесть дублирующиеся объекты в наборе?

Answer 1

Похоже, вы хотите знать, сколько подмножественных множеств имеет, скажем, 3 элемента. Математика для этого становится очень сложной, очень быстро. Идея заключается в том, что вы хотите сложить все комбинации способов добраться туда. Таким образом, у вас есть C (3,4) = 4 способа сделать это без дублированных элементов. B можно повторить дважды в C (1,3) = 3 способа. B можно повторить 3 раза в 1 способ. И С можно повторить дважды С (1,3) = 3 способами. Всего 11. (Ваша 10, которую вы получили вручную, была неправильной. Извините.)

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

Да, если вы не хотите рассматривать наборы, рассмотрите идею «факторов». Сколько факторов влияет:

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

имеет, если p1 являются различными простыми числами. Если все ai равны 1, то число равно 2 ^ n. В общем случае, ответ (a1 + 1) (a2 + 1) ... (an + 1), как отмечает Дэвид Неем.

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

Answer 3

Набор содержит только уникальные предметы. Если есть дубликаты, то это больше не набор.

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 для примера.