Dénombrement

PRINCIPE MULTIPLICATIF : k choix successifs (n₁,n₂,…,nₖ) indépendants : Total = n₁×n₂×…×nₖ ARRANGEMENT Aₙᵖ (ordre compte, sans répétition) : Aₙᵖ=n!/(n−p)!=n(n−1)…(n−p+1) PERMUTATION : Aₙⁿ=n! LIEN INFORMATIQUE : Nombre de tableaux triés possibles : n! Algorithme bogosort (tri aléatoire) : O(n·n!) en moyenne Problème du voyageur de commerce (TSP) : (n−1)!/2 tours Tri à bulles : O(n²) comparaisons (bien mieux que n!)

⚡ 10!=3 628 800 ; 20!≈2,4×10¹⁸. Les algorithmes en O(n!) sont inutilisables pour n>15.