NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 14/04/2021 Orientation générale  DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Dénombrement
Débutants Général	COMPTER des …				Glossaire Général
INDEX Général Dénombrement	Nombres	Fractions	Ensembles	Droites
		Classer k éléments en suites ordonnées
		Sommaire de cette page >>> Approche avec k de 1 à 4 >>> Liste des quantités de ces sous-ensembles >>> Fonction génératrice

SOUS-ENSEMBLES ordonnés

à partir de k éléments

Un ensemble de k éléments. Combien d'ensembles ordonnés peut-on créer à partir de cet ensemble-mère ?

La quantité croit très rapidement !

.

Approche avec k de 1 à 4

Notion de partage des ensembles

Prenons les nombres 1 à 3 et ses 6 permutations.

En partageant les 3 nombres en deux sous-ensembles, il y a à nouveau 6 façons de permuter les nombres.

Enfin, il existe une seule façon de partager les 3 nombres en trois.

Remarque: les ensembles ne sont pas identifiés (numérotés) et, pour eux, l'ordre n'importe pas. (1, 2, 3) est équivalent à (2, 1, 3).

Avec les nombres 1 à 4, on atteint déjà 73 sous-ensembles de ce type

k	Qté	Ensembles
1	1	1
2	3	12	21	1, 2
3	13	123	132	213	231	312	321
		12, 3	21, 3	13, 2	31, 2	23, 1	32, 1
		1, 2, 3

k	Qté	Ensembles	Permutations
4	73	1234	24
		123, 4	4 x 6
		12, 34	2 x 2 x 3
		12, 3 ,4	12
		1, 2, 3, 4	1

Liste des quantités de ces sous-ensembles

Cette suite de nombres se rencontre dans de nombreuses applications comme le montre les exemples donnés dans A00262 (applications d'un niveau avancé).

Formule récurrente

Q_n = (2n – 1) Q_{n – 1} – (n – 1)(n – 2) Q_{n – 2}

Ex: n = 4 => 7 x 13 – 3 x 2 x 3 = 73

k	Quantité de S-E
0	1
1	1
2	3
3	13
4	73
5	501
6	4 051
7	37 633
8	394 353
9	4 596 553
10	58 941 091
11	824 073 141
12	12 470 162 233
13	202 976 401 213
14	3 535 017 524 403
15	65 573 803 186 921

Fonction génératrice
	La fonction génératrice est assez simple. Les coefficients correspondent à la quantité de sous-ensemble divisée par la factorielle de n qui est aussi le degré du monôme. Les fractions sont réduites. Pour retrouver la valeur du coefficient, repasser au dénominateur avec la factorielle idoine.

Suite	Compter les droites Théorie des ensembles Partition des ensembles Manipulation des sous-ensembles avec Maple Infini – Index
Voir	Calcul mental Cardinal Crises en maths Diagonale de Cantor Ensemble - Glossaire Fini et infini Groupe	Groupes de permutations Jeux Les infinitésimaux Les nombres et leurs ensembles Magie Nombres rationnels
Sites	OEIS A000262 - Number of "sets of lists": number of partitions of {1,...,n} into any number of lists, where a list means an ordered subset
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Compter/CompESO.htm