Jadis on cryptait l'information par substitution: on codait tout "a" par un "m", tout "b" par un "t"... Puis, si on connaissait la combinaison, on trouvait aussi l'original par substitution. Sans blancs (ils sont courants: 99 ici), sans ponctuation, sans aucun invariant, il y a alors 148362637348470135821287825 choix distincts pour la combinaison, trop pour un importun ayant surpris la communication. Mais un individu sournois s'appuya sur la proportion d'apparition standard du "a", du "b"... trouvant ainsi la combinaison. Donc il fallut obscurcir plus l'information avant sa transmission, modifiant tout au moins la proportion d'apparition standard (mais pas aussi mal qu'ici).
Démontrons qu'il y a bien 148362637348470135821287825 combinaisons sans invariant. Commençons par donner un exemple: avec les 3 lettres ABC, il y a 3!=6 combinaisons possibles qui sont: ABC, ACB, BAC, BCA, CAB et CBA. Parmi celles-ci il y a 4 combinaisons avec une ou plusieurs lettres invariantes (qui restent à la même place), et 2 sans aucun invariant (en gras, aucune lettre ne conserve la même place).
Appelons NCI(n) le nombre de combinaisons de n lettres
possédant au moins une lettre invariante, et f(n) le nombre
de combinaisons de n lettres dont la première lettre n'est
pas invariante mais possédant au moins une lettre invariante.
Alors on a pour tout n>2: et f(n) = (n-1) x [ NCI(n-2) + f(n-1) ] |
Avec n lettres, pour qu'une combinaison possède au moins un invariant, soit la première lettre est invariante, auquel cas la disposition des n-1 autres lettres n'a pas d'importance et on a alors (n-1)! possibilités pour que la combinaison possède au moins un invariant, soit la première lettre n'est pas invariante et on a cette fois f(n) possibilités. Autrement dit NCI(n) = (n-1)! + f(n).
Pour trouver f(n) supposons que la combinaison possède au moins un invariant, mais que la première lettre ne soit pas invariante, alors celle-ci est envoyée à la place d'une des n-1 autres lettres. Supposons qu'elle soit envoyée sur la deuxième lettre (on notera A->B), alors on a deux cas possibles:
On vérifie aisément que f(2) = 0 puisque les combinaisons pour deux lettres sont: AB et BA. On voit que si la première lettre n'est pas invariante (c'est BA), alors la combinaison ne possède aucune lettre invariante.
A partir de ces formules, et à l'aide d'un cours programme (voir plus loin), on peut calculer f(n), NCI(n) et en déduire NCS(n) = n! - NCI(n) le nombre de combinaisons de n lettres sans aucun invariant:
n | f(n) | NCI(n) | NCS(n) |
2 | 0 | 1 | 1 |
3 | 2 | 4 | 2 |
4 | 9 | 15 | 9 |
5 | 52 | 76 | 44 |
6 | 335 | 455 | 265 |
7 | 2466 | 3186 | 1854 |
8 | 20447 | 25487 | 14833 |
9 | 189064 | 229384 | 133496 |
10 | 1930959 | 2293839 | 1334961 |
11 | 21603430 | 25232230 | 14684570 |
12 | 262869959 | 302786759 | 176214841 |
13 | 3457226268 | 3936227868 | 2290792932 |
14 | 48880169351 | 55107190151 | 32071101049 |
15 | 739429561066 | 826607852266 | 481066515734 |
16 | 11918051268255 | 13225725636255 | 7697064251745 |
17 | 203914545928336 | 224837335816336 | 130850092279664 |
18 | 3691384616598047 | 4047072044694047 | 2355301661033953 |
19 | 70491995143458894 | 76894368849186894 | 44750731559645106 |
20 | 1416242276574905879 | 1537887376983737879 | 895014631192902121 |
21 | 29862732908481855460 | 32295634916658495460 | 18795307255050944540 |
22 | 659413025994777460119 | 710503968166486900119 | 413496759611120779881 |
23 | 15217590540051591022738 | 16341591267829198702738 | 9510425471055777937262 |
24 | 366346173689015792225711 | 392198190427900768865711 | 228250211305338670494289 |
25 | 9184506358964279782282776 | 9804954760697519221642776 | 5706255282633466762357224 |
26 | 239417613734804513778712175 | 254928823778135499762712175 | 148362637348470135821287825 |
Enfin voici le listing du programme permettant de calculer cette table. Il a été écrit en SockZ, un excellent langage de programmation basé sur le Forth, et qui permet de manipuler aisément les grands nombres et les rationnels. Et, euh... écrit par votre serviteur... ce qui explique sans doute pourquoi il est tellement bon! ;) Bref, le voici:
;2004sep13 - Alain Brobecker ;Count NCS(n) the number of permutations of n elements with no invariant. ;It uses NCI(n) the number of permutations of n elements with at least ;one invariant, f(n) the number of permutations of n elements where the ;first element varies but with at least one invariant. The formulas ;used then are, for every n>2: ; NCS(n) = n! - NCI(n) ; NCI(n) = (n-1)! + f(n) ; f(2)= 0 and f(n) = (n-1) * [ NCI(n-2) + f(n-1) ] "n f(n) NCI(n) NCS(n)" CR 1 1 ;NCI(n-2) NCI(n-1) 0 ;f(n-1) 3 ;n .loop COPY PRINT " " ;print n COPY 1 - COPY ! SWAP2 ;... NCI(n-2) NCI(n-1) f(n-1) n (n-1)! n-1 6 OVER 5 OVER + * ;... n (n-1)! f(n)=(n-1)*(NCI(n-2)+f(n-1)) COPY PRINT " " ;print f(n) COPY 5 SWAP DROP ;replace f(n-1) by f(n) + ;... NCI(n-2) NCI(n-1) f(n) n NCI(n)=(n-1)!+f(n) COPY PRINT " " ;print NCI(n) OVER2 ! OVER2 - ;... NCI(n-2) NCI(n-1) f(n) n NCI(n) NCS(n)=n!-NCI(n) PRINT CR ;print and remove NCS(n) 3 SWAP ;... NCI(n-2) NCI(n-1) NCI(n) n f(n) SWAP2 1 + ;... NCI(n-2) NCI(n-1) NCI(n) f(n) n+1 COPY 26 SKIP> loop END ;Compute n!, from the library #! COPY SKIP>0 !end COPY 1 - ! * END .!end DROP 1 END