Les Schtroumpfs - Solution

Nombre total de relations

Notons plus simplement aSb si a schtroumpfe b, ou plus traditionnel aRb pour noter la relation entre a et b.
On peut écrire la table de vérité de R qui donne pour toute valeur du couple ordonné (a,b) la valeur de R = (0,1).
Il y a N = n² valeurs du couple (a,b), pour chacune 2 valeurs pour R et donc r = 2^N = 2^(n²) tables de vérités possibles.

n	n²	r = 2^(n²)
0	0	1
1	1	2
2	4	16
3	9	512
4	16	65536
5	25	33554432
6	36	68719476736

Ce nombre croît extrèmement vite avec n.

Restrictions

On note ici r(p,q) le nombre de relations R pour lesquelles il y a au plus p valeurs de x avec xRb et au plus q valeurs de y avec aRy
On remarque immédiatement que :

r(p,q) = r(q,p)
r(p,q) = r(p,n) si q≥n
r(p,0) = r(0,0) = 1
r(n,n) = r = 2^(n²)

Pour n = 1 r(0,0)=1, r(1,0)=1 et r(p,q)=r(1,1)=2 si p et q≥1

Pour n = 2 on peut recenser les 16 cas possibles

	nb max de x : xRy	nb max de y : xRy
aucun	0	0
aRa	1	1
aRb	1	1
bRa	1	1
bRb	1	1
aRa aRb	1	2
aRa bRa	2	1
aRa bRb	1	1
aRb bRa	1	1
aRb bRb	2	1
bRa bRb	1	2
aRa aRb bRa	2	2
aRa aRb bRb	2	2
aRa bRa bRb	2	2
aRb bRa bRb	2	2
aRa aRb bRa bRb	2	2

et donc r(1,1)=7, r(2,1)=9 et comme d'hab r(p,0)=1 et r(2,2)=16

Pour n = 3 recenser les 512 cas possibles est déja trop fastidieux et un programme donne facilement les valeurs cherchées
Ce programme donne aussi les valeurs pour n = 4 (65536 cas) et n = 5 (33554432 cas) :

****** n=1 ********

p\q	0	1
0	1
1	1	2

****** n=2 ********

p\q	0	1	2
0	1
1	1	7
2	1	9	16

****** n=3 ********

p\q	0	1	2	3
0	1
1	1	34
2	1	61	265
3	1	64	343	512

****** n=4 ********

p\q	0	1	2	3	4
0	1
1	1	209
2	1	557	7343
3	1	621	13623	41503
4	1	625	14641	50625	65536

****** n=5 ********

p\q	0	1	2	3	4	5
0	1
1	1	1546
2	1	6396	304186
3	1	7646	865036	6474726
4	1	7771	1032961	11086351	24997921
5	1	7776	1048576	11881376	28629151	33554432

Au dela le programme s'essouffle à examiner 68719476736 cas et plus, d'ailleurs il faut commencer à traiter des nombres en multiple précision car plus de 32 bits sont nécessaires !

Calcul de r(1,1)

Il s'agit de compter le nombre de tables de vérité de R ayant au plus un 1 dans chaque ligne et dans chaque colonne.
En posant Cⁱ_n=n!/(i!(n-i)!) le nombre de combinaisons de i objets parmi p et Aⁱ_n=n!/(n-i)! le nombre d'arrangements de i objets parmi p
il y a 1 = C⁰_nA⁰_n façon de mettre aucun 1 dans la table
Il y a n*n = C¹_nA¹_n façons de mettre un seul 1 dans la table
C²_nA²_n façons de mettre deux 1
C³_nA³_n façons de mettre trois 1
...
il y a Cⁿ_nAⁿ_n = n! façons de mettre n fois 1
et donc r(1,1) = ∑_i=0ⁿ Cⁱ_nAⁱ_n

Calcul de r(n,p)

Pour r(n,1), cela revient à choisir au plus un 1, donc de C⁰_n+C¹_n = n+1 façons, dans chacune des n colonnes de la table.
Donc r(n,1) = (n+1)ⁿ = (C⁰_n+C¹_n)ⁿ
pour r(n,2), il y a C⁰_n+C¹_n+C²_n façons de mettre au plus deux 1 dans une ligne et donc
r(n,2)=(C⁰_n+C¹_n+C²_n)ⁿ
et de façon générale r(n,p) = (∑_i=0^p Cⁱ_n)ⁿ
Nota : r(n,n) = (∑_i=0ⁿ Cⁱ_n)ⁿ = (2ⁿ)ⁿ = 2^(n²)

Calcul de r(n-1,p)

Ceci revient à éliminer des r(n,p) cas ceux qui ont exactement n fois 1 dans une ou plusieurs lignes
soit C¹_n+C²_n+...+C^p_n cas, et r(n-1,p) = r(n,p) - ∑_i=0^p Cⁱ_n
En particulier r(n-1,1) = r(n,1) - n

Calcul de r(n-2,1), r(n-3,1), ...

Parmi les r(n-1,1) cas on élimine ceux qui ont un seul 0 par ligne :
n lignes
fois n emplacements du 0 sur la ligne
fois n valeurs de la colonne contenant le 0 : pas de 1, un 1 sur une des n-1 autres lignes.
Soit r(n-2,1) = (n+1)ⁿ-n-n³

Pour éliminer les cas avec deux 0 par lignes :
n lignes
fois C²_n=n(n-1)/2 façons de choisir les deux 0 sur la ligne
fois n façons de placer éventuellement un 1 sur la colonne du 1er zéro
fois n façons de placer éventuellement un 1 sur la colonne du 2eme zéro
Soit r(n-3,1) = r(n-2,1)-n⁴(n-1)/2

Mais attention ! ceci n'est vrai que si n est "assez grand", c'est à dire si n-2>2
Sinon les choix pour placer un 1 dans les colonnes de 0 sont limités.

pour n=4, les cas où il y a deux 1 sur la même ligne sont comptés deux fois, soit (C²₄)² = 36 cas
et r(n-3,1) = r(n-2,1)-n⁴(n-1)/2+(n(n-1)/2)²

De façon générale : r(n-i-1,1) = r(n-i,1)-nCⁱ_nnⁱ = r(n-i,1)-nⁱ⁺¹Cⁱ_n pourvu que n-i>i

Pour i≥n/2, c'est un peu plus dur à éliminer les cas comptés plusieurs fois ou à rejeter.
Examinons par exemple le cas n=8.
r(8,1) = 9⁷,
elimination des lignes toutes à 1 : r(7,1) = r(8,1)-n
elimination des lignes avec un seul 0 : r(6,1) = r(7,1)-n³ =
elimination des lignes avec deux 0 : r(5,1) = r(6,1)-n³C²_n
elimination des lignes avec trois 0 : r(4,1) = r(5,1)-n⁴C³_n
elimination des lignes avec quatre 0 : r(3,1) = r(4,1)-n⁵C⁴_n+(C⁴_n)² pour prendre en compte les cas en double comme pour n=4 ci-dessus.
elimination des lignes avec cinq 0 : on élimine n⁶C⁴_n cas, mais sont éliminés en trop les cas où dans les cinq colonnes avec un 0, il y a des lignes de trois, quatre ou cinq 1

En résumé :

r(p,q) = r(q,p)
r(p,0) = r(0,0) = 1
r(p,q) = r(p,n) si q≥n
r(n,n) = r = 2^(n²)
r(1,1) = ∑_i=0ⁿ Cⁱ_nAⁱ_n
r(n,p)=(∑_i=0^p Cⁱ_n)ⁿ, en particulier r(n,1) = (n+1)ⁿ
pour i<n/2 r(n-i-1,1) = r(n-i,1)-nⁱ⁺¹Cⁱ_n