Permutation d'éléments identiques

La permutation avec répétition, lorsque l'on part d'un total et des fréquences d'éléments identiques, compte combien d'arrangements ordonnés distincts une collection mixte peut prendre. Si vous détenez n objets et que certains sont des copies indiscernables, le nombre de suites différentes est la factorielle de n divisée par le produit de la factorielle de chaque fréquence listée. Cette calculatrice accepte cette paire — le total n et la liste des fréquences —, évalue l'identité avec une arithmétique BigInt exacte et renvoie le nombre de permutations sous forme de chaîne décimale. Il n'y a ni échantillonnage, ni appel réseau, ni arrondi dépendant de l'horloge : chaque paire valide produit toujours le même entier.

Ce que compte une permutation d'éléments identiques répétés

Une permutation avec répétition d'éléments identiques est le nombre d'arrangements ordonnés distincts d'une collection finie dans laquelle certains membres ne peuvent pas être distingués. Écrivez n pour le nombre total de positions (ou d'objets) et n1, n2, jusqu'à nk pour le nombre d'apparitions de chaque type indiscernable. Comme échanger deux copies du même type ne crée pas un nouvel arrangement, les n factorielle ordonnancements d'une collection entièrement étiquetée surcomptent de n1 factorielle pour le premier type, n2 factorielle pour le second, et ainsi de suite.

L'identité exacte est donc la factorielle de n divisée par le produit de ces factorielles. Les contrôles classiques de classe comprennent les lettres de BANANA : six lettres, trois A, deux N et un B, ce qui donne six factorielle sur trois factorielle fois deux factorielle fois une factorielle, égal à soixante mots distincts, et MISSISSIPPI : onze lettres aux fréquences un, quatre, quatre et deux, ce qui donne onze factorielle sur ces factorielles, égal à trente-quatre mille six cent cinquante.

Ce n'est pas le produit n à la puissance r que certains manuels appellent aussi permutations avec répétition : cet autre dénombrement remplit r cases indépendantes depuis un alphabet de n symboles et vaut n élevé à r. Ici la longueur est déjà n, et l'entrée est la fréquence de chaque groupe identique. Si une fréquence listée est plus grande que n, la collection est impossible et cette calculatrice rejette la requête au lieu de renvoyer zéro ou une extension signée.

Les fréquences dont la somme est inférieure à n laissent des éléments uniques restants ; chaque reste contribue une factorielle de un au dénominateur et ne change pas l'entier, de sorte que la même formule s'applique encore. L'implémentation n'échantillonne jamais, ne dépend jamais de l'horloge et n'arrondit jamais : elle évalue la factorielle de n sur le produit des factorielles listées avec une arithmétique BigInt exacte afin que les grands dénombrements restent des entiers exacts plutôt que de déborder la mantisse d'un flottant.

Anagrammes, places assises et oracles de concours

Les enseignants de langue et les auteurs d'énigmes utilisent ce dénombrement lorsqu'ils demandent combien de mots distincts on peut former en réordonnant une chaîne donnée : les lettres sont les éléments, l'histogramme de chaque lettre est la liste des effectifs de répétition, et la réponse est exactement la factorielle de n sur le produit de ces factorielles. Les problèmes de chimie et de génétique qui disposent des perles, des bases ou des sièges colorés avec des copies indiscernables suivent le même entier.

Les enseignants de statistique l'introduisent lorsqu'ils opposent l'échantillonnage à issues identiques au produit n à la puissance r qui remplit des cases indépendantes, et les programmeurs de concours ont besoin d'un oracle exact afin de ne pas réimplémenter la division factorielle en multiprécision dans chaque harnais de langage.

Les générateurs d'examens peuvent figer le chemin de succès avec n égal à six et repeats égaux à trois, deux et un, ce qui donne soixante, et le chemin de rejet avec toute fréquence plus grande que n, qui doit échouer plutôt que de renvoyer zéro.

Les pages sœurs peuvent viser le produit n à la puissance r des sélections ordonnées avec remise, le coefficient multinomial générique ou les permutations sans répétition ; cette page vise précisément le libellé permutation avec répétition lorsque les entrées sont un total et les effectifs de répétition d'éléments identiques. Associez le dénombrement à votre propre code de listage si vous avez besoin des chaînes distinctes concrètes ; cette capacité ne renvoie que l'entier.