Théorème de Pascal pour les ensembles non-uniques?

Question

Pascal's rule lors du comptage du sous-ensemble d'un ensemble fonctionne très bien, lorsque l'ensemble contient des entités uniques.

Y a-t-il une modification à cette règle lorsque l'ensemble contient des éléments en double? Par exemple, lorsque j'essaie de trouver le nombre de combinaisons des lettres A, B, C, D, il est facile de voir que c'est 1 + 4 + 6 + 4 + 1 (du triangle de Pascal) = 16 , ou 15 si je supprime l'entrée "Utiliser aucune des lettres".

Maintenant, que se passe-t-il si l'ensemble des lettres est A, B, B, B, C, C, D? En calculant à la main, je peux déterminer que la somme des sous-ensembles est: 1 + 4 + 8 + 11 + 11 + 8 + 4 + 1 = 48, mais cela ne correspond pas au Triangle que je connais. Question: Comment modifier le triangle de Pascal pour prendre en compte les entités dupliquées dans l'ensemble?

Answer 1

Il semble que vous vouliez savoir combien de sous-ensembles ont, disons, 3 éléments. Le calcul pour cela devient très difficile, très rapidement. L'idée est que vous voulez ajouter ensemble toutes les combinaisons de façons d'y arriver. Donc vous avez C (3,4) = 4 façons de le faire sans éléments dupliqués. B peut être répété deux fois en C (1,3) = 3 façons. B peut être répété 3 fois de 1 manière. Et C peut être répété deux fois en C (1,3) = 3 façons. Pour 11 au total. (Votre 10 que vous avez obtenu à la main était faux, désolé.)

En général, essayer de faire cela est trop difficile. La façon la plus simple d'en garder trace est d'écrire un polynôme dont les coefficients ont les termes que vous voulez que vous multipliez. Pour le triangle de Pascal, c'est facile, le polynôme est (1 + x)^n. (Vous pouvez utiliser la quadrature répétée pour calculer ceci plus efficacement.) Dans votre cas, si un élément est répété deux fois, vous aurez un facteur (1 + x + x^2). 3 fois serait (1 + x + x^2 + x^3).Donc, votre problème sera résolu comme suit:

(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 

Si vous voulez produire ces chiffres dans le code, j'utiliser l'astuce polynomiale pour organiser votre pensée et code. (Vous travaillez avec des tableaux de coefficients.)

Answer 2

Un ensemble contient uniquement des éléments uniques. S'il y a des doublons, alors ce n'est plus un ensemble.

Answer 3

Même si les ensembles mathématiques contiennent des éléments uniques, vous pouvez rencontrer le problème des éléments dupliqués dans les 'ensembles' dans le monde réel de la programmation. Voir this thread sur les unions Lisp pour un exemple.

Answer 4

Vous n'avez pas du tout besoin de modifier le triangle de Pascal. Etude C (k, n) et vous découvrirez - vous devez essentiellement diviser les résultats originaux pour tenir compte de la permutation des lettres équivalentes. Par exemple, A B1 B2 C1 D1 == A B2 B1 C1 D1, vous devez donc diviser C (5,5) par C (2,2).

Answer 5

Sans doublons (dans un ensemble comme noté précédemment), chaque élément est dans ou hors du sous-ensemble. Donc vous avez 2^n sous-ensembles. Avec les doublons, (dans un "multi-set") vous devez prendre en compte le nombre de fois que chaque élément est dans le "sous-multi-set". Si m_1, m_2 ... m_n représente le nombre de fois que chaque élément se répète, alors le nombre de sous-sacs est (1 + m_1) * (1 + m_2) * ... (1 + m_n).

Answer 6

Oui, si vous ne voulez pas considérer les ensembles, tenez compte de l'idée de 'facteurs'. Combien de facteurs:

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

avoir si p1 sont des nombres premiers distincts. Si les ai sont tous 1, alors le nombre est 2^n. En général, la réponse est (a1 + 1) (a2 + 1) ... (an + 1) comme le note David Nehme.

Oh, et notez que votre réponse à la main était erronée, elle devrait être 48, ou 47 si vous ne voulez pas compter l'ensemble vide.