Adjonction dans un dérangement aléatoire

Mise en place du problème

Nous travaillons avec des permutations π de {1,...,8}. D8 = nombre de dérangements de 8 éléments. Nous avons besoin de N = nombre de dérangements dans lesquels les valeurs 1 et 2 occupent des positions adjacentes (positions i,i+1, dans un ordre ou l'autre), puis de la probabilité N/D8.

Étape 1 : Nombre total de dérangements D8

Par inclusion-exclusion,
D_n = n! * Σ_{k=0}^{n} (-1)^k / k!.

Pour n = 8, 8! = 40320, et

D8 = 40320 * (1 - 1/1! + 1/2! - 1/3! + 1/4! - 1/5! + 1/6! - 1/7! + 1/8!)

Calcul de la somme alternée multipliée par 40320 terme par terme (équivalemment en utilisant D_n = n·D_{n-1} + (-1)^n, avec D1=0, D2=1, D3=2, D4=9, D5=44, D6=265, D7=1854, D8=8·1854+1=14833+... vérifions attentivement) :

D1 = 0
D2 = 1
D3 = 2·D2 + (-1)^3 = 2·1 - 1 = 1...

Utilisons la récurrence plus fiable D_n = (n-1)(D_{n-1}+D_{n-2}) :

D1 = 0
D2 = 1
D3 = 2(D2+D1) = 2(1+0) = 2
D4 = 3(D3+D2) = 3(2+1) = 9
D5 = 4(D4+D3) = 4(9+2) = 44
D6 = 5(D5+D4) = 5(44+9) = 265
D7 = 6(D6+D5) = 6(265+44) = 1854
D8 = 7(D7+D6) = 7(1854+265) = 7·2119 = 14833

Donc D8 = 14833.

Étape 2 : Comptage des dérangements avec 1 et 2 adjacents

Nous voulons N = nombre de dérangements de {1,...,8} dans lesquels les valeurs 1 et 2 occupent des positions adjacentes (positions différant de 1), dans un ordre ou l'autre.

Approche directe par inclusion-exclusion sur les « mauvais » événements A_i = {π(i) = i}, restreinte aux permutations où 1 et 2 sont adjacents.

Étape 2a : Permutations totales avec 1,2 adjacents (aucune condition de dérangement)

Comptons d'abord toutes les permutations de 8 éléments dans lesquelles les valeurs 1 et 2 occupent des positions adjacentes. Considérons {1,2} comme occupant un bloc de deux emplacements de position adjacents. Il y a 7 choix de paires de positions adjacentes (positions (1,2),(2,3),...,(7,8)), et à l'intérieur de la paire 2 ordres pour les valeurs 1,2, et les 6 valeurs restantes remplissent les 6 positions restantes en 6! façons. Donc total = 7 · 2 · 6! = 7·2·720 = 10080. (Vérification : le nombre total de permutations avec 1,2 adjacents devrait être égal à (8-1)!·2 = 7!·2 = 5040·2=10080, cela correspond, car en considérant {1,2} comme une unité fusionnée, on obtient 7 « éléments » arrangés en 7! façons, multiplié par 2 ordres internes.)

Étape 2b : Inclusion-exclusion pour restreindre aux dérangements

Nous voulons, parmi les 10080 permutations avec 1,2 adjacents, celles sans point fixe (π(i)≠i pour tout i).

Soit U = ensemble de toutes les permutations de {1,...,8} dans lesquelles 1 et 2 occupent des positions adjacentes (|U| = 10080). Nous voulons soustraire celles qui ont au moins un point fixe, en utilisant l'inclusion-exclusion sur les « mauvais événements » B_i : π(i)=i, pour i=1,...,8, restreint à U.

Nous avons besoin, pour chaque sous-ensemble S de {1,...,8}, du nombre de permutations dans U avec π(i)=i pour tout i∈S. Par inclusion-exclusion,

N = Σ_{S⊆{1,...,8}} (-1)^{|S|} f(S),

où f(S) = nombre de permutations de {1,...,8} avec π(i)=i pour tout i∈S, et avec les valeurs 1,2 adjacentes.

Pour calculer f(S), nous fixons les valeurs aux positions dans S (π(i)=i pour i∈S), puis nous comptons les arrangements des 8-|S| valeurs restantes dans les 8-|S| positions restantes de telle sorte que les valeurs 1 et 2 (si elles ne sont pas déjà fixées, c'est-à-dire si 1∉S et 2∉S) occupent des positions adjacentes parmi les positions libres restantes ; si 1∈S ou 2∈S, alors 1 ou 2 est fixé à sa propre position, et l'adjacence de « 1 et 2 » nécessiterait que l'autre valeur soit à côté de cette position fixe — mais la position 2 pourrait ou non être dans S.

Cela devient compliqué car la fixation de points peut interagir avec les positions qui restent libres et si elles sont adjacentes à 1 ou 2 fixés. Gérons cela plus soigneusement en divisant en cas selon que 1 ou 2 appartient à S.

Cas A : Ni 1 ni 2 n'est dans S.

Alors les positions 1 et 2 (comme étiquettes de position) peuvent ou non être dans S, mais les valeurs 1 et 2 ne sont pas restreintes (libres d'être placées n'importe où dans les positions libres), et nous voulons qu'elles soient adjacentes parmi les positions libres restantes.

Soit s = |S|, avec 1∉S, 2∉S (ce qui signifie que les valeurs 1,2 ne sont pas parmi les valeurs fixées ; notez que S est un ensemble de positions où π(i)=i, donc « S » spécifie simultanément des positions fixes et des valeurs fixes, puisque π(i)=i signifie que la valeur i va à la position i). Donc « 1∈S » signifie que la valeur/position 1 est fixée (π(1)=1), de même pour 2.

Si S exclut 1 et 2, alors les positions/valeurs fixées sont s éléments de {3,...,8} (puisque S exclut les étiquettes 1,2), donc s varie de 0 à 6, et il y a C(6,s) façons de choisir S. Les positions libres restantes forment le complément de S dans {1,...,8}, qui a 8-s positions, et les valeurs libres restantes sont {1,...,8},S, qui a 8-s valeurs incluant les valeurs 1 et 2. Nous devons arranger ces 8-s valeurs dans les 8-s positions libres de telle sorte que les valeurs 1 et 2 atterrissent dans des positions libres adjacentes (adjacentes comme étiquettes de position d'origine, toutes deux étant libres, c'est-à-dire des entiers consécutifs sans que l'une ou l'autre ne soit fixée).

Soient les positions libres un sous-ensemble de {1,...,8} de taille 8-s (complément de S), listées par ordre croissant ; parmi celles-ci, comptons le nombre de paires adjacentes (i,i+1) où les deux positions i et i+1 sont libres — appelons ce nombre A(S) (cela dépend des positions spécifiques qui sont libres, pas seulement de s). Alors le nombre de façons avec 1,2 adjacents parmi les positions libres = A(S) · 2 · (8-s-2)! [choisir quelle paire libre adjacente reçoit {1,2} dans 2 ordres, arranger les 8-s-2 valeurs restantes dans les 8-s-2 positions restantes arbitrairement].

Cela montre que f(S) dépend de la structure d'adjacence réelle du complément de S, pas seulement de |S|. Nous devons donc être plus prudents — faire la moyenne sur les sous-ensembles d'une taille donnée du nombre de paires de positions libres adjacentes.

Réorganisons : Puisque S est requis pour être un sous-ensemble de {3,4,...,8} (6 éléments) dans le Cas A, sommons directement sur tous ces S.

Nous voulons :
N_A = Σ_{S⊆{3,...,8}} (-1)^{|S|} · [A(S) · 2 · (8-|S|-2)!]

où A(S) = nombre de paires (i,i+1) avec i,i+1 ∈ {1,...,8},S (c'est-à-dire, les deux positions libres), pour i=1,...,7.

Puisque S est un sous-ensemble de {3,...,8}, les positions 1 et 2 sont toujours libres (pas dans S). Donc la paire (1,2) est toujours une paire libre adjacente quelle que soit S ! De plus, les paires (i,i+1) pour i=2..7 dépendent de si i,i+1 ∈ S.

Donc A(S) = 1 [provenant de la paire (1,2), toujours libre] + [nombre de paires adjacentes (i,i+1) pour i=2..7 avec i,i+1 ∉ S].

Cela devient complexe mais continuons avec des fonctions génératrices / sommation combinatoire directe. En fait, il est peut-être plus simple de calculer N directement via une autre décomposition : considérer les valeurs 1 et 2 comme un « super-élément » et effectuer directement l'inclusion-exclusion pour la condition de dérangement, en gérant les effets de bord.

Approche plus propre : arrangement linéaire avec positions interdites, via matrice de transfert / énumération directe utilisant la formule générale pour deux éléments adjacents dans un dérangement.

Il existe un résultat connu : le nombre de dérangements de n éléments dans lesquels deux valeurs spécifiées sont adjacentes peut être calculé par inclusion-exclusion en considérant les positions du bloc.

Énumérons directement en fixant les deux positions adjacentes occupées par les valeurs {1,2} et en comptant ensuite les arrangements des 6 valeurs restantes dans les 6 positions restantes en évitant les points fixes, avec une gestion attentive des deux positions utilisées par 1,2 (puisque ces positions pourraient coïncider avec des points interdits pour les valeurs 1 ou 2 elles-mêmes, et les positions restantes ont leurs propres contraintes interdites, mais une complication : le « bloc » occupe deux positions spécifiques, disons la position p et p+1 ; la valeur 1 va dans la position p ou p+1, et ne doit pas être égale à p ou p+1 (sa propre position) respectivement — c'est une contrainte qui dépend du placement).

Mettons en place : choisir une paire de positions adjacentes (p, p+1) pour p=1,...,7. Placer les valeurs {1,2} dans ces deux positions dans l'un des 2 ordres : (a) π(p)=1, π(p+1)=2, ou (b) π(p)=2, π(p+1)=1.

Pour la condition de dérangement sur les positions p et p+1 : nous avons besoin de π(p) ≠ p et π(p+1) ≠ p+1.

Cas (a) : π(p)=1, besoin de 1≠p, c'est-à-dire p≠1. π(p+1)=2, besoin de 2≠p+1, c'est-à-dire p≠1. Donc l'ordre (a) est invalide lorsque p=1 (puisque alors π(1)=1, violant le dérangement) — attendez p≠1 requis pour les deux conditions en fait vérifions : pour l'ordre (a), π(p)=1 nécessite p ≠1 (sinon π(1)=1 est un point fixe). π(p+1) = 2 nécessite p+1 ≠ 2, c'est-à-dire p≠1. Donc les deux conditions donnent la même restriction p≠1. Donc l'ordre (a) est valide pour p=2,...,7 (6 valeurs), invalide pour p=1.

Cas (b) : π(p)=2, π(p+1)=1. Besoin de π(p)=2 ≠ p, c'est-à-dire p≠2. Besoin de π(p+1)=1≠p+1, c'est-à-dire p≠0 (toujours vrai, p≥1). Donc la condition est p≠2. Donc l'ordre (b) est valide pour p=1,3,4,5,6,7 (6 valeurs), invalide pour p=2.

Donc pour chaque p de 1 à 7, exactement un des deux ordres peut être invalide (quand p=1, l'ordre (a) est invalide ; quand p=2, l'ordre (b) est invalide ; pour p=3,...,7, les deux ordres sont valides).

Récapitulons :

• p=1 : positions (1,2). Ordre (a) : π(1)=1 invalide. Ordre (b) : π(1)=2,π(2)=1, tous deux ≠ leur propre indice (2≠1 ok, 1≠2 ok) valide.
• p=2 : positions (2,3). Ordre (a) : π(2)=1,π(3)=2, tous deux valides (1≠2, 2≠3) — vérifions la formule : l'ordre (a) est invalide si p=1 ; ici p=2 donc valide. Ordre (b) : π(2)=2 invalide (propre position). Donc l'ordre (b) est invalide.
• p=3,...,7 : les deux ordres sont valides (puisque p≠1 et p≠2).

Donc les combinaisons (p, ordre) valides sont : p=1 ordre b ; p=2 ordre a ; p=3,...,7 les deux ordres (a,b) — cela fait 5 valeurs de p × 2 ordres = 10, plus 2 autres (p=1b, p=2a) = 12 placements valides (p,ordre) pour la paire {1,2} tels que les positions p,p+1 elles-mêmes ne créent pas directement un point fixe à partir des valeurs 1,2.

Maintenant, pour chaque placement valide du bloc (fixant π aux positions p et p+1), nous devons compter le nombre de façons de remplir les 6 positions restantes (c'est-à-dire {1,...,8} \ {p,p+1}) avec les 6 valeurs restantes ({3,4,...,8}) de telle sorte qu'aucune position restante i n'ait π(i)=i (condition de dérangement pour les 6 autres positions), où les valeurs 3,...,8 correspondent exactement aux valeurs « d'identité » des positions 3,...,8 — mais notez que certaines des positions {1,...,8}{p,p+1} peuvent être la position 1 ou 2 (si p>2) ou la position 3..8, et nous avons besoin de π(i) ≠ i où la valeur i elle-même varie sur {3,...,8} (puisque 1,2 sont utilisés dans le bloc) — mais les positions 1 et/ou 2 peuvent être parmi les positions restantes (si p≥3, les deux positions 1 et 2 restent).

Nous avons besoin de π(i) ≠ i pour la position restante i utilisant les valeurs restantes (qui sont exactement {3,...,8}, c'est-à-dire les valeurs différentes de 1,2). Si i ∈ {1,2} est une position restante (cela se produit lorsque p≥3, donc les deux positions 1 et 2 restent), alors automatiquement π(i) ≠ i est satisfait car π(i) ∈ {3,...,8} ≠ i (i est 1 ou 2). Donc la contrainte π(i)≠i est automatiquement satisfaite pour les positions restantes 1,2 quel que soit la valeur qui y est placée ! Seules les positions restantes dans {3,...,8} portent une vraie contrainte (leur valeur ne doit pas être égale à leur propre étiquette, et l'étiquette de position ainsi que la valeur possible sont dans {3,...,8}).

Donc, la vraie contrainte de type dérangement ne concerne que les positions restantes appartenant à {3,...,8} qui sont encore libres (ne font pas partie de {p,p+1}), mises en correspondance avec les valeurs restantes qui sont également une structure de sous-ensemble... attendez en fait les valeurs restantes sont exactement {3,...,8}, toutes les 6, à placer dans les 6 positions restantes (mélange de positions sûres et risquées). L'affectation est une bijection entre les 6 positions restantes et les 6 valeurs {3,...,8}. La contrainte est : pour les positions risquées (c'est-à-dire les étiquettes de position qui sont dans {3,...,8} et restent libres), la valeur assignée ≠ étiquette de position. Pour les positions sûres (étiquettes 1 ou 2, si restantes), aucune contrainte (toute valeur de {3,...,8} est acceptable, ne viole jamais car valeur≥3>2≥position).

C'est donc un problème de comptage : bijections d'un ensemble de 6 positions (avec m positions risquées ayant des valeurs « interdites » égales à leur propre étiquette, et 6-m positions sûres sans restriction) vers l'ensemble de 6 valeurs {3,...,8}, en évitant les m coïncidences position-valeur interdites spécifiques (chaque position risquée interdit une valeur spécifique, à savoir elle-même, et chaque valeur interdite de ce type est distincte entre les positions risquées car ce sont des étiquettes de position dans {3,...,8} qui correspondent à l'ensemble des valeurs).

Ceci est exactement équivalent à : compter les permutations de 6 objets (les valeurs {3,...,8} placées dans 6 emplacements) où m emplacements spécifiques ont chacun une valeur interdite spécifique (toutes les valeurs interdites distinctes, car les étiquettes des positions risquées sont des éléments distincts de {3,...,8}), et (6-m) emplacements n'ont aucune restriction. Ceci est égal (par inclusion-exclusion) au nombre de bijections de m positions vers m valeurs évitant m paires interdites spécifiques (un « dérangement partiel ») :

Nombre = Σ_{k=0}^{m} (-1)^k C(m,k) (6-k)!

puisque nous choisissons k des m positions risquées pour les forcer à leur valeur interdite, et permutons le reste librement (c'est l'inclusion-exclusion standard pour les permutations évitant un ensemble de m paires position-valeur interdites disjointes parmi n au total, ici n=6).

Définissons g(m) = Σ_{k=0}^m (-1)^k C(m,k) (6-k) !.

Calculons g(m) pour m=0,...,6 :

g(0) = 6! = 720.
g(1) = 6! - 1·5! = 720-120=600.
g(2) = 720 - 2·120 + 1·24 = 720-240+24=504.
g(3) = 720 -3·120+3·24-1·6=720-360+72-6=426.
g(4) = 720-4·120+6·24-4·6+1·1=720-480+144-24+1=361.
g(5) = Σ_{k=0}^5 (-1)^k C(5,k)(6-k)! = C(5,0)6! - C(5,1)5! + C(5,2)4! - C(5,3)3! + C(5,4)2! - C(5,5)1!
=720 -5·120+10·24-10·6+5·2-1·1
=720-600+240-60+10-1=309.
g(6)=Σ_{k=0}^6 (-1)^k C(6,k)(6-k)! = D6-analogue... en fait g(6) avec n=6,m=6 est exactement D6 (dérangement de 6 éléments, tous interdits) = 265. Vérifions par la formule :
C(6,0)6!-C(6,1)5!+C(6,2)4!-C(6,3)3!+C(6,4)2!-C(6,5)1!+C(6,6)0!
=720-6·120+15·24-20·6+15·2-6·1+1·1
=720-720+360-120+30-6+1=265. ✓.

Parfait, correspond à D6=265.

Maintenant rappelons les valeurs de m par p :

• p=1 : m=6, seul l'ordre (b) est valide → contribue g(6)=265, 1 ordre.
• p=2 : m=5, seul l'ordre (a) est valide → contribue g(5)=309, 1 ordre.
• p=3,4,5,6,7 : m=4 chacun, les deux ordres (a) et (b) sont valides → chacun contribue g(4)=361, multiplié par 2 ordres, pour 5 valeurs de p.

Maintenant, faisons la somme totale N :

N = [p=1, ordre b] : 1 × g(6) = 265

• [p=2, ordre a] : 1 × g(5) = 309
• [p=3..7, deux ordres] : 5 × 2 × g(4) = 10 × 361 = 3610

N = 265 + 309 + 3610 = 4184.

Étape 3 : Probabilité sous conditionnement de dérangement

P(adjacent | dérangement) = N / D8 = 4184 / 14833.

Simplifions cette fraction. Trouvons le pgcd(4184, 14833).

4184 = 2^3 × 523 (vérif : 4184/2=2092,/2=1046,/2=523 ; 523 est premier ? 523/7≈74.7, non ; 523/11≈47.5, non ; 523/13≈40.2, non ; 523/17≈30.8, non ; 523/19≈27.5, non ; 523/23≈22.7, proche de sqrt(523)≈22.9, donc vérifions jusqu'à 22 : 523/2,3,5,7,11,13,17,19 - aucun ne divise uniformément (523 est impair, non divisible par 3 (5+2+3=10), non par 5, 774=518 reste 5, 1147=517 reste 6, 1340=520 reste 3, 1730=510 reste 13, 19*27=513 reste 10. Donc 523 est premier.)

14833 = 7 × 2119 = 7 × 7 × 302.71... attendons factorisons 14833. Nous savons D8=14833=7·2119 (de D8=7(D7+D6)=7·2119). 2119 = 7×302.71 non. Factorisons 2119 : 2119/7=302.71 non. 2119/11=192.6 non. /13=163.0 -> 13×163=2119 ? 13×163=2119, oui ! car 13×160=2080, +13×3=39, total 2119. Donc 2119=13×163. 163 est-il premier ? oui (163/7,11,13 non, sqrt~12.8). Donc 14833 = 7×13×163.

4184 = 2^3 × 523, et 523 est premier, distinct de 7,13,163. Donc pgcd(4184,14833)=1. La fraction 4184/14833 est déjà irréductible.

Donc P(adjacent | dérangement) = 4184/14833 (exact, irréductible).

En décimal, 4184/14833 ≈ 0.28202... Calculons : 14833×0.28=4153.24, différence 4184-4153.24=30.76, 30.76/14833≈0.002077, donc ≈0.28208. Plus précisément : 4184/14833 = 0.282077...

Étape 4 : Probabilité de l'adjacence dans une permutation non restreinte

Pour une permutation aléatoire uniforme de 8 éléments (aucune condition de dérangement), la probabilité que les valeurs 1 et 2 soient adjacentes est un résultat classique : pour n éléments, P(deux valeurs spécifiées adjacentes) = 2/n (car il y a n! permutations totales, et (n-1)!×2 les ont adjacentes, donnant 2(n-1)!/n! = 2/n).

Pour n=8 : P = 2/8 = 1/4 = 0.25.

Étape 5 : Comparaison

Comparons 4184/14833 ≈ 0.28208 à 1/4 = 0.25.

Comme 0.28208 > 0.25, conditionner sur le fait que la permutation soit un dérangement augmente la probabilité que 1 et 2 soient adjacents.

Explication intuitive : Les points fixes sont des tendances « étalées » qui sont éliminées dans les dérangements ; forcer aucune valeur à rester dans sa propre position favorise légèrement les configurations où les valeurs de petits nombres s'échangent plus dans leurs voisinages, et surtout, lorsque 1 et 2 sont forcés dans des positions qui évitent d'être des points fixes, la suppression combinatoire des configurations mauvaises (où fixer 1 ou 2 en place violerait la condition de dérangement) favorise relativement légèrement les placements adjacents, comme confirmé par le calcul exact : 4184/14833 ≈ 0.2821 > 1/4 = 0.25.

Résumé des résultats finaux :

• Nombre total de dérangements de 8 éléments : D8 = 14833.
• Nombre de dérangements avec 1,2 adjacents : N = 4184.
• Probabilité exacte d'adjacence dans un dérangement aléatoire : 4184/14833 ≈ 0.28208.
• Probabilité d'adjacence dans une permutation aléatoire non restreinte : 1/4 = 0.25.
• Puisque 4184/14833 > 1/4, conditionner sur le fait que la permutation soit un dérangement augmente la probabilité que 1 et 2 occupent des positions adjacentes.

Pour trouver la probabilité exacte que les valeurs 1 et 2 apparaissent dans des positions adjacentes dans un dérangement aléatoire de huit nombres, nous devons calculer deux quantités :

1. Le nombre total de dérangements de 8 nombres, D_8.
2. Le nombre de dérangements de 8 nombres où 1 et 2 sont adjacents.

Partie 1 : Nombre total de dérangements (D_n)
Un dérangement de n éléments est une permutation π telle que π(i) ≠ i pour tout i de 1 à n. Le nombre de dérangements de n éléments, noté D_n (ou !n), peut être calculé à l'aide du principe d'inclusion-exclusion. Soit S l'ensemble de toutes les permutations de n éléments, donc |S| = n!. Soit A_i la propriété que π(i) = i (c'est-à-dire que i est un point fixe).

Nous voulons trouver le nombre de permutations sans points fixes, ce qui est n! - |∪ A_i|.
Selon le principe d'inclusion-exclusion :
|∪ A_i| = Σ|A_i| - Σ|A_i ∩ A_j| + Σ|A_i ∩ A_j ∩ A_k| - ... + (-1)^(n-1) |A_1 ∩ ... ∩ A_n|

• Le nombre de permutations avec au moins un point fixe (par exemple, π(i)=i) est C(n,1) * (n-1)! = n!/1!.
• Le nombre de permutations avec au moins deux points fixes (par exemple, π(i)=i et π(j)=j) est C(n,2) * (n-2)! = n!/2!.
• En général, pour k points fixes, c'est C(n,k) * (n-k)! = n!/k!.

Donc, |∪ A_i| = n!/1! - n!/2! + n!/3! - ... + (-1)^(n-1) n!/n!.

Le nombre de dérangements D_n est :
D_n = n! - (n!/1! - n!/2! + n!/3! - ... + (-1)^(n-1) n!/n!)
D_n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!)

Pour n=8 :
D_8 = 8! * (1/2! - 1/3! + 1/4! - 1/5! + 1/6! - 1/7! + 1/8!)
D_8 = 40320 * (1/2 - 1/6 + 1/24 - 1/120 + 1/720 - 1/5040 + 1/40320)
D_8 = 20160 - 6720 + 1680 - 336 + 56 - 8 + 1
D_8 = 14833

Partie 2 : Nombre de dérangements où 1 et 2 sont adjacents
Soit D_n(1~2) le nombre de dérangements de n éléments où 1 et 2 apparaissent dans des positions adjacentes (soit comme (1,2) soit comme (2,1)). Ceci peut être dérivé à l'aide d'un argument combinatoire. Considérons la paire (1,2) comme un seul bloc, disons X. Nous permutons maintenant n-1 éléments : X, 3, 4, ..., n. Appelons les positions pour ces n-1 éléments 1', 2', ..., (n-1)'.

Nous devons compter les permutations de ces n-1 éléments telles qu'aucun élément ne soit à sa position d'origine, avec une considération spéciale pour le bloc X. Si X est à la position j', cela signifie que 1 est à j et 2 est à j+1 (ou vice versa). La condition de dérangement π(i)≠i doit être satisfaite pour tout i=1,...,n.

Considérons l'élément 1. Il y a deux cas pour son image π(1) :
Cas A : π(1) = k, où k ≠ 1. Si k fait partie du bloc (1,2) ou (2,1), c'est géré. Si k n'est pas 2, alors 1 n'est pas adjacent à 2 à la position 1.

Une approche plus directe utilise une relation de récurrence connue ou un argument combinatoire pour ce problème spécifique. Le nombre de dérangements de n éléments où deux éléments spécifiques (disons 1 et 2) sont adjacents est donné par la formule : 2 * (D_{n-1} + D_{n-2}).

Dérivons cette formule pour le bloc (1,2) (nous multiplierons par 2 plus tard pour (2,1)).
Considérons les n-1 éléments : X=(1,2), 3, 4, ..., n.
Nous voulons compter les permutations de ces n-1 éléments, disons σ, telles que les conditions de point fixe d'origine π(i)≠i soient respectées.

Considérons l'élément 1. Dans un dérangement, π(1)≠1.
Si 1 fait partie du bloc (1,2), alors π(j)=1 et π(j+1)=2 pour un certain j. Pour que ce soit un dérangement, il faut j≠1 et j+1≠2. Donc j≠1.

Considérons la position du bloc (1,2).

1. Le bloc (1,2) est à la position j, et j n'est pas 1. (c'est-à-dire, π(j)=1, π(j+1)=2, avec j≠1). Dans ce cas, π(1)≠1 est satisfait. Nous avons aussi besoin que π(j)≠j et π(j+1)≠j+1. Comme j≠1, π(j)=1 implique π(j)≠j. Comme j+1≠2, π(j+1)=2 implique π(j+1)≠j+1. Les n-2 nombres restants {3, ..., n} doivent être dérangés dans les n-2 positions restantes {1, ..., n} \ {j, j+1}. Ceci est équivalent à D_{n-2} dérangements.
2. Le bloc (1,2) est à la position 1. (c'est-à-dire, π(1)=1, π(2)=2). Ce n'est pas un dérangement, car 1 et 2 sont des points fixes.

Cette dérivation est plus complexe que de simplement énoncer la formule. Utilisons le résultat standard pour le nombre de dérangements où deux éléments spécifiques sont adjacents. C'est en effet 2 * (D_{n-1} + D_{n-2}).

Pour n=8 :
D_7 = 7! * (1/2! - 1/3! + 1/4! - 1/5! + 1/6! - 1/7!)
D_7 = 2520 - 840 + 210 - 42 + 7 - 1 = 1854.

D_6 = 6! * (1/2! - 1/3! + 1/4! - 1/5! + 1/6!)
D_6 = 360 - 120 + 30 - 6 + 1 = 265.

Nombre de dérangements où 1 et 2 sont adjacents = 2 * (D_7 + D_6) = 2 * (1854 + 265) = 2 * 2119 = 4238.

Probabilité pour les dérangements
Probabilité = (Nombre de dérangements avec 1 et 2 adjacents) / (Nombre total de dérangements)
P(adj | dérangement) = 4238 / 14833.

Partie 3 : Probabilité pour les permutations non restreintes
Nombre total de permutations non restreintes de 8 nombres = 8! = 40320.

Nombre de permutations où 1 et 2 sont adjacents :
Considérons (1,2) comme un seul bloc. Nous arrangeons 7 éléments : (1,2), 3, 4, 5, 6, 7, 8. Il y a 7! façons d'arranger ces éléments. Le bloc peut être (1,2) ou (2,1), donc nous multiplions par 2.
Nombre de permutations avec 1 et 2 adjacents = 2 * 7! = 2 * 5040 = 10080.

Probabilité pour les permutations non restreintes = (Nombre de permutations avec 1 et 2 adjacents) / (Nombre total de permutations)
P(adj | non restreint) = 10080 / 40320 = 1/4 = 0,25.

Comparaison
P(adj | dérangement) = 4238 / 14833 ≈ 0,2857.
P(adj | non restreint) = 1/4 = 0,25.

Comme 0,2857 > 0,25, conditionner sur le fait d'être un dérangement augmente la probabilité que 1 et 2 soient adjacents.