Teorema de Pascal para conjuntos não-exclusiva?

Question

de Pascal regra em contar os do subconjunto de um conjunto funciona muito bem, quando o conjunto contém entidades únicas.

Existe uma modificação a esta regra para quando o conjunto contém itens duplicados?

Por exemplo, ao tentar encontrar a contagem das combinações das letras A, B, C, D, é fácil de ver que é 1 + 4 + 6 + 4 + 1 (a partir do triângulo de Pascal) = 16, ou 15 se eu remover o "uso nenhuma das letras" de entrada.

Agora, e se o conjunto de cartas é A, B, B, B, C, C, D? Computação à mão, posso determinar que a soma de subconjuntos é:. 1 + 4 + 8 + 11 + 11 + 8 + 4 + 1 = 48, mas esta não se conforma com o Triângulo I Know

Pergunta: Como você modificar Triângulo de Pascal para levar em conta as entidades duplicadas no conjunto

Answer 1

Parece que você quer saber quantas sub-multi-conjuntos têm, digamos, 3 elementos. A matemática por isso fica muito complicado, muito rapidamente. A idéia é que você deseja adicionar em conjunto todas as combinações de maneiras de chegar lá. Então você tem C (3,4) = 4 maneiras de fazê-lo sem elementos duplicados. B pode ser repetida duas vezes em C (1,3) = 3 maneiras. B pode ser repetida 3 vezes em 1 forma. E C pode ser repetida duas vezes em C (1,3) = 3 maneiras. Para 11 total. (O seu 10 você tem à mão estava errado. Desculpe.)

Em geral tentando fazer que a lógica é muito difícil. A maneira mais simples de manter o controle do que é para escrever um polinômio cujos coeficientes têm os termos que você deseja que você multiplicar fora. Para o triângulo de Pascal isso é fácil, o polinômio é (1 + x) ^ n. (Você pode usar repetida quadratura para calcular isso com mais eficiência.) No seu caso, se um elemento é repetido duas vezes, você teria um (+ + 1 x x ^ 2) fator. 3 vezes seria (1 + x + x + x ^ 2 ^ 3). Portanto, o seu problema específico seria resolvido da seguinte forma:

(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

Se você quiser produzir esses números no código, eu usaria o truque polinomial para organizar seu pensamento e código. (Você estaria trabalhando com matrizes de coeficientes.)

Answer 2

Um conjunto contém apenas itens exclusivos. Se houver duplicatas, então ele não é mais um set.

Answer 3

Sim, se você não considerar conjuntos, considere a idéia de 'fatores'. Como muitos fatores faz:

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

têm se do P1 são primos distintos. Se o ai estão todos 1, então o número é 2 ^ n. Em geral, a resposta é (a1 + 1) (a2 + 1) ... (an + 1) como notas David Nehme.

Oh, e nota que a sua resposta à mão estava errado, que deveria ser 48, ou 47 se você não quer contar o conjunto vazio.

Answer 4

Você não precisa modificar Triângulo de Pascal em tudo. Estudo C (k, n) e você vai descobrir -. Você precisa basicamente para dividir os resultados originais para explicar a permutação de letras equivalentes

por exemplo., A B1 B2 C1 D1 == A B1 B2 C1 D1, portanto, é preciso dividir C (5,5) por C (2,2).

Answer 5

Sem duplicatas (em um conjunto como cartazes anteriores notaram), cada elemento é dentro ou fora do subconjunto. Então você tem 2 ^ n subconjuntos. Com duplicatas, (em um "multi-set") você tem que levar em conta o número o número de vezes que cada elemento está na "sub-multi-set". Se M_1, m_2 ... m_n representam o número de vezes que cada elemento se repete, então o número de sub-malas é (1 + m_1) * (1 + m_2) * ... (1 + m_n).

Answer 6

Apesar de conjuntos matemáticos contêm itens exclusivos, você pode correr para o problema de itens duplicados em 'conjuntos' no mundo real de programação. Consulte este enrosque em sindicatos Lisp para um exemplo.