Camille prépare quatre cartes fictives, nommées A, B, C et D, devant quatre places portant les mêmes noms. Nora doit construire une distribution de papier où chaque place reçoit une seule carte. La première demande interdit qu’une carte rejoigne la place de son propre nom. Aucun destinataire réel, préférence personnelle ou envoi n’est observé. Nous étudions ce modèle classique de permutations sans point fixe, avec des décisions créées sur le comptage des distributions et sur une procédure de tirage explicitement définie.
Trois sites identifient des carnets. Les distributions, les noms et les règles de tirage ci-dessous ne viennent d’aucune méthode de ces fabricants.
BRUNNEN présente des carnets.
Bindewerk présente des carnets.
Rössler présente des carnets.
Retirer les destinations interdites compte aussi leurs intersections
Sans l’interdiction, Camille peut choisir quatre places pour A, puis trois pour B, deux pour C et une pour D. Elle obtient vingt-quatre distributions complètes. Ce calcul compte des listes d’associations nommées, pas des motifs réunis selon une rotation : changer les noms de place change la distribution. Pour construire la nouvelle liste, Nora doit retirer toutes celles où au moins une carte rejoint son propre nom. Retirer seulement l’identité A–A, B–B, C–C, D–D ne suffirait pas ; une distribution peut garder un seul nom ou deux tout en changeant les autres.
Camille compte d’abord six distributions avec A à sa place : les trois autres cartes peuvent parcourir les trois places restantes. Il y en a six également pour chacun des trois autres noms. Soustraire quatre fois six aux vingt-quatre donnerait pourtant zéro. Nora montre la distribution A–A, B–B, C–D, D–C : elle a été retirée une fois pour A et une fois pour B. La suppression directe l’a donc comptée deux fois, alors qu’elle ne représentait qu’une seule liste interdite. Il faut tenir compte des intersections entre les interdictions, plutôt que rendre ces quatre retraits indépendants.
Pour une paire de noms gardés à leurs places, les deux cartes restantes disposent de deux distributions. Il y a six paires de noms, donc douze ajouts après les retraits doubles. Pour trois noms gardés, la quatrième carte doit également rester à sa place : chacune des quatre sélections de trois noms décrit la même identité, et exige un retrait. Enfin, garder les quatre noms donne une seule distribution à ajouter. Nora obtient vingt-quatre moins vingt-quatre, plus douze, moins quatre, plus un : neuf. Les listes partiellement inchangées ne sont pas autorisées par ces ajouts ; les signes compensent les comptes répétés avant de laisser seulement les distributions où aucun nom n’est gardé.
Nora vérifie pourquoi ces signes ferment le contrôle. Une distribution possédant exactement r noms inchangés intervient dans autant de retraits ou d’ajouts que de sous-ensembles choisis parmi ces r noms. Son coefficient total vaut un moins r, plus le nombre de paires, puis les termes suivants avec leurs signes alternés. Pour r positif, cette somme est celle du développement de un moins un à la puissance r, donc zéro. Pour r nul, seul le premier terme subsiste, avec coefficient un. Le calcul ne s’appuie ainsi pas sur la seule coïncidence du nombre neuf avec quelques listes que Camille aurait trouvées.
La liste remise peut aussi être contrôlée directement. En indiquant, dans l’ordre A, B, C, D, les places reçues, Nora trouve BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB et DCBA. Chacune contient les quatre noms une fois et aucune lettre n’occupe sa propre position. Camille garde cette liste comme réalisation du neuf, sans la raccourcir aux distributions constituées de deux échanges. Trois des neuf se décomposent en deux échanges de paires ; les six autres font parcourir les quatre noms dans un même cycle. L’interdiction initiale n’avait demandé ni l’une ni l’autre forme séparément.
Retirer une carte ne produit pas toujours le même problème
Pour préparer un nombre différent de cartes sans relister toutes les permutations, Nora nomme D de n le nombre de distributions admissibles sur n noms. Elle fixe la place reçue par une carte particulière, la dernière : cette place porte un autre nom j, choisi parmi n moins un noms. Elle distingue ensuite deux cas qui ne peuvent être fusionnés dans le même retrait de carte. Soit j reçoit la dernière place, soit cette dernière place est reçue par une autre carte. Ces cas décrivent des associations, sans ajouter une permission d’échange matériel dans un dîner réel.
Dans le premier cas, la dernière carte et j forment un échange de deux noms. Les retirer laisse n moins deux cartes sur leurs places correspondantes, avec la même interdiction de garder son propre nom. Chaque distribution admissible restante peut être complétée par cet échange fixé, et une seule fois. Pour un j donné, ce cas apporte donc D de n moins deux. Nora ne le compte pas comme un problème à n moins un cartes : j a quitté la liste avec la dernière, et les deux places ont été consommées ensemble.
Dans le second cas, une carte i différente de j reçoit la dernière place, tandis que la dernière carte reçoit j. Nora retire la dernière carte et remplace les deux associations successives par i vers j. Il ne crée aucun nom inchangé, puisque i et j sont différents. Il reste une distribution admissible sur n moins un noms. Réciproquement, dans une telle distribution, la carte qui reçoit j est différente de j ; insérer la dernière carte entre elle et j reconstruit exactement ce second cas. Cette correspondance conserve les associations utiles à la reconstruction, au lieu de supprimer une ligne et de perdre le nom de la place qu’elle reliait.
Pour chaque choix de j, les deux cas apportent donc D de n moins deux et D de n moins un. Nora obtient D de n égal à n moins un fois leur somme. La liste vide possède une distribution, tandis qu’une seule carte ne peut changer de nom. Ces deux départs donnent successivement un, deux, neuf et quarante-quatre pour deux, trois, quatre et cinq cartes. Camille utilise cette règle pour passer à cinq sans prétendre que les quarante-quatre sont les neuf anciennes listes auxquelles on aurait simplement ajouté une cinquième carte. L’insertion peut changer un cycle et le retrait par paire peut créer une autre branche.
Une moyenne d’un nom inchangé ne promet pas un nom dans chaque liste
Une commande séparée tire uniformément l’une des vingt-quatre distributions complètes, avant toute interdiction. Chaque nom a une chance d’un quart de rester à sa place. Additionner ces quatre probabilités donne un comme nombre moyen de noms inchangés. Camille avait traduit ce calcul par « un nom reste toujours ». Nora compare l’identité, qui en garde quatre, et BADC, qui n’en garde aucun. La moyenne porte sur les distributions équiprobables, pas sur une propriété obligatoire de chacune. Ce rappel ne fournit pas à lui seul une nouvelle méthode de tirage admissible.
Nora remplit la répartition entière. Zéro nom inchangé correspond aux neuf listes déjà comptées. Pour en garder exactement un, elle choisit son nom de quatre manières, puis utilise sur les trois autres noms l’une des deux distributions sans point fixe : huit listes. Pour en garder exactement deux, elle choisit la paire de six manières, et les deux autres doivent s’échanger : six listes. Trois noms exactement sont impossibles, puisque la quatrième place est alors forcément celle de la dernière carte. Quatre noms donne l’identité seule. Neuf, huit, six, zéro et un totalisent vingt-quatre, avec une moyenne de un et non un seul résultat possible.
Cette impossibilité de trois permet une décision concrète. Camille demande une fiche gardant A, B et C, mais faisant changer D. Nora refuse de l’ajouter comme vingt-cinquième distribution : A, B et C occupent leurs places, laissant seulement D à la dernière carte. Camille accepte de changer également C ; elle reçoit alors ABCD révisée en ABDC, où A et B restent tandis que C et D s’échangent. Nora inscrit deux noms gardés dans cette fiche, sans conserver trois dans la légende. Le problème venait de la dernière place disponible, pas du manque d’une permutation que le comptage aurait oublié.
Les événements « A reste » et « B reste » ne sont pas indépendants dans le tirage complet. En imposant A à sa place, il reste trois places équiprobables pour B ; sa chance de rester devient un tiers, au lieu du quart sans cette information. Leur probabilité commune vaut un douzième, pas un seizième. Camille retire donc la proposition qui multipliait quatre fois trois quarts pour obtenir la chance que personne ne reste. Cette multiplication aurait donné quatre-vingt-un sur deux cent cinquante-six ; le compte exact neuf sur vingt-quatre donne trois huitièmes. Les destinations distinctes relient les événements, même lorsque la règle d’interdiction est écrite séparément pour chaque nom.
Écarter une permutation entière diffère de choisir chaque ligne au hasard
Nora veut maintenant un tirage uniforme parmi les neuf listes admissibles. Une première procédure tire uniformément une permutation complète parmi les vingt-quatre ; si elle garde au moins un nom, elle recommence avec un nouveau tirage indépendant. Chaque liste admissible possède la même chance un sur vingt-quatre à chaque essai. Conditionner un essai par sa réussite donne donc à chacune la chance un sur neuf. Le nombre d’essais a une moyenne de huit tiers, puisque la probabilité de réussite vaut trois huitièmes. Nora peut accepter cette procédure dans le modèle, sans annoncer un nombre d’essais maximal : une suite de refus reste possible.
Camille préfère éviter les associations interdites dès leur préparation. Elle traite A, puis B, C et D ; pour chaque carte, elle choisit uniformément parmi les places encore libres dont le nom diffère du sien. Si aucune place n’est possible, elle abandonne l’essai et repart. Nora examine l’essai A vers B, B vers C, C vers A. Il laisse seulement D pour D, donc échoue. Trois choix localement autorisés n’ont pas donné une distribution complète. La possibilité de recommencer fait partie de cette procédure, mais ne garantit pas encore qu’elle produise la même loi que le rejet d’une permutation uniforme entière.
Deux réponses réussies révèlent la différence. Pour BADC, A reçoit B avec une chance d’un tiers ; B reçoit A parmi les trois places A, C et D, encore avec un tiers. C doit alors recevoir D, et D reçoit C. La probabilité de cette réponse à un essai est un neuvième. Pour BCDA, les deux premiers choix ont les mêmes chances, mais C choisit D parmi A et D ; il apporte un facteur un demi supplémentaire. Cette seconde réponse possède une probabilité un dix-huitième, moitié de la première. Répéter les essais échoués ne peut égaliser ces deux probabilités relatives : conditionner les deux par la même réussite conserve leur rapport deux.
L’énumération des embranchements donne cinq trente-sixièmes d’échec. Après répétition jusqu’à une réussite, BADC a donc une probabilité quatre trente et unièmes, tandis que BCDA a deux trente et unièmes. Nora refuse « neuf réponses également probables » pour cette procédure locale. Elle ne refuse pas les deux réponses comme distributions admissibles : leurs associations respectent l’interdiction. Camille choisit de revenir au rejet uniforme de la liste entière lorsqu’elle souhaite l’équiprobabilité, et conserve la procédure locale comme autre loi explicitement différente. La conformité d’une réponse et la loi qui la sélectionne reçoivent ainsi deux contrôles distincts.
Une seconde réparation permet de garder une construction par lignes. Avant chaque choix, Nora compte les complétions admissibles de la liste partielle. Elle attribue à une place possible une probabilité proportionnelle au nombre de complétions après ce choix. Une place ne laissant aucune complétion reçoit zéro, même si son nom est localement autorisé. Les nombres de complétions des choix possibles totalisent ceux de la liste partielle, puisque chaque complétion possède exactement un prochain choix. Cette règle répartit donc réellement une probabilité entière, sans confondre le nombre de places libres avec le nombre de listes encore réalisables.
Pour une liste complète choisie, les facteurs de cette procédure se simplifient : nombre de complétions après la première ligne sur neuf, puis nombre après la deuxième sur celui après la première, et ainsi de suite jusqu’à un sur le dernier nombre. Il reste un sur neuf. Nora a fermé l’équiprobabilité par ce produit, pas par l’expression « choix équilibrés » inscrite sur les lignes. Après A vers B et B vers C, elle interdit C vers A, qui laisserait D vers D, et choisit C vers D. La réparation ne garde donc pas la chance un demi de la procédure précédente à cette étape ; elle a changé la règle de choix pour répondre à la demande uniforme.
Deux associations interdites peuvent se croiser ou ne jamais coexister
Camille ajoute maintenant une interdiction à la liste des neuf : A ne doit pas recevoir B, en plus de ne pas garder A. Parmi les neuf réponses, BADC, BCDA et BDAC donnaient B à A. Nora les retire et garde six listes. Elle ne refait pas le premier calcul sur toutes les vingt-quatre comme si la nouvelle interdiction remplaçait les quatre anciennes. La base active est déjà le groupe des neuf sans point fixe ; la condition supplémentaire y sélectionne un sous-groupe de réponses effectivement défini.
Une autre commande interdit à la fois A vers B et B vers A. Chacun de ces événements apparaît dans trois des neuf listes. Ils coexistent cependant dans BADC, où C et D s’échangent. Retirer trois puis trois supprimerait cette liste deux fois. Nora la réintroduit une fois et compte neuf moins trois moins trois plus un, soit quatre réponses. Elle choisit par exemple CDAB, qui ne garde aucun nom et respecte les deux interdictions supplémentaires. Le retour du un dans le calcul ne rend pas BADC admissible ; il annule seulement le retrait répété avant de remettre le compte des listes restantes.
Camille compare ce résultat à la demande interdisant A vers B et A vers C. Les deux événements apparaissent encore chacun trois fois, mais ils ne peuvent coexister dans une seule distribution : A reçoit une seule place. Leur intersection est vide. Nora garde donc trois listes, toutes avec A vers D : DABC, DCAB et DCBA. Camille retire la proposition quatre recopiée depuis la commande précédente. Deux interdictions de même taille ne donnaient pas la même intersection. La correction a changé les associations supplémentaires, et le compte suit ce changement au lieu de dépendre seulement du nombre de phrases d’interdiction.
Nora conserve les neuf distributions initiales, les six sous une interdiction supplémentaire, puis les quatre ou trois sous les deux commandes comparées. Chaque liste garde ses noms, ses conditions et la procédure de tirage éventuellement choisie. Les carnets consultés n’ont fourni ni les probabilités ni une règle de distribution. La remise de papier distingue le nombre de réponses admissibles, les rencontres entre événements interdits et la chance donnée à chaque réponse, sans attribuer à une permutation valide la garantie d’avoir été tirée uniformément.
Une contrainte de parité change encore la chance de tout déplacer
Une préparation séparée autorise seulement les permutations paires. Cette condition porte sur la permutation complète des quatre noms, pas sur un nombre pair de cartes distribuées. Un échange de deux noms est impair ; deux échanges successifs donnent une permutation paire. Nous pouvons déterminer la parité à partir des cycles : un cycle de longueur l peut être réalisé par l moins un échanges de deux noms. La demande fixe cette propriété mathématique du résultat ; elle ne décrit pas une manipulation réelle des cartes ni une préférence des destinataires.
Parmi les neuf distributions sans point fixe, trois sont deux échanges disjoints : BADC, CDAB et DCBA. Elles sont paires, puisqu’elles utilisent deux échanges. Les six autres sont des cycles de longueur quatre : elles sont impaires, avec trois échanges chacune. Nora garde donc exactement trois réponses lorsque Camille demande une distribution sans point fixe et paire. Elle lui remet CDAB, dont les échanges sont A avec C et B avec D. Camille retire BCDA de cette remise : ses quatre noms changent bien de place, mais son cycle exige trois échanges et manque la nouvelle condition. La correction n’a pas ajouté une destination interdite ; elle a filtré une propriété de la liste entière, que les seules interdictions de ligne ne pouvaient exprimer.
Si la préparation tire uniformément parmi toutes les permutations paires avant de vérifier les noms inchangés, elle possède douze réponses possibles. L’identité est paire. Les huit permutations gardant exactement un nom sont aussi paires : leurs trois autres noms forment un cycle de longueur trois, réalisable par deux échanges. Les six gardant exactement deux noms sont impaires, puisqu’un seul échange relie les deux autres. Avec les trois distributions paires sans point fixe, Nora retrouve douze, et la chance de tout déplacer vaut un quart. Parmi les douze permutations impaires, six déplacent tout et six gardent deux noms : la chance de tout déplacer vaut un demi. Les deux préparations conservent pourtant un nom inchangé en moyenne, puisque huit plus quatre sur douze vaut un dans la première, et douze sur douze dans la seconde. Nora conserve les probabilités un quart et un demi, sans employer leur moyenne commune pour promettre le même risque d’échec au contrôle.