Problème de dénombrement

[invite32373aeb]

Je suis entrain de dénombrer certains ensembles et je suis tombé sur un os.
Je considère les permutations sur l'ensemble I={0,...n} afin de représenter un cycle. La permutation (012) exprime le cycle 0120

Je décompose l'ensemble des permutations en ensemble de schémas.
Un schéma est un ensemble de permutations qui sont en partie fixées.
Par exemple, le schéma de longueur n {(0,2,*,*,*...)} contient toute les permutations sur I commençant par 0 et 2 (le caractère "*" veut dire "n'importe quoi").

Mon problème:
Il y a schémas possible, mais combien y en a t-il qui spécifient des paquets d'au minimum deux entiers?
exemple:
{(0,3,5,*,*,...,*)} est valide,
{(0,*,*,...,3)} est valide car on considère un cycle
{(4,5,*,3,*,...,*)} n'est pas valide car 3 est encadré par deux "*".
-----

[invite7265fdfc]

Je ne suis aucunement spécialiste, j'essaie de comprendre votre question:

Toute permutation peut se décomposer comme produit de cycles à supports disjoints. (un cycle c'est une permutation spéciale, c'est une permutation circulaire). Je ne sais pas comment on calcule le nombre de cycles d'une permutation, je ne m'étais jamais posé la question. Cela ne semble pas facile, je viens de trouver un article bien difficile sur ce sujet:http://www.eleves.ens.fr/home/kortch...cycles-rms.pdf.
Par exemple, la permutation sur {0,5}:
0 1 2 3 4 5
5 4 1 0 2 3

se décompose en 2 cycles:
(0 5 3) (1 4 2)

Pour revenir à votre question:
un schéma, si je comprends bien, c'est un cycle en partie connue, de longueur fixée, ou plus formellement un ensemble de cycles:

par exemple, toujours sur {0,5}, (0 5 *) , ce sont les cycles (0 5 1) , (0 5 2), (0 5 3), (0 5 4) .

C'est cela que vous voulez dire ?

[invite32373aeb]

Oui, exactement,
et je m'excuse pour l'histoire du , ce n'est pas vrai dans le cas de permutations.

Je vais essayer de chercher le nombre de permutation correct avant de m'attacher à résoudre mon problème

[invite7265fdfc]

C'est vrai que ce n'est pas la bonne formule pour le nombre de permutations sur un ensemble à n éléments. La formule exacte se trouve facilement sur internet ou dans les livres, c'est un grand classique, mais il est bon de retrouver les formules par soi-même. Il faudrait établir deux formules: celle qui donne le nombre de permutations de {1, ..., n} et celle qui donne le nombre de cycles de longueur p de {1, ..., n}, avec p compris entre 1 et n. Ce ne sont pas les mêmes formules. Sinon cela voudrait dire que toutes les permutations de {1, ..., n} sont des cycles de longueur n, ce qui n'est pas exact dès que n>1

Exemple: {1}
Une permutation: l'identité (notée id)
Un seul cycle de longueur 1: (1), qui est en fait l'identité.

Exemple: {1,2}
Les permutations sont:
12 12
12 21
Il y en a deux

Un seul cycle: (1) =(2) = id
Un cycle de longueur 2: (1 2)

Exemple:{1,2,3}
Les permutations de {1,2,3} sont:
123 123 123 123 123 123
123 132 213 231 312 321
(il y en a 6)

Le seul cycle de longueur 1 est l'identité.
(on pourrait se dire: il y a (1), (2) et (3) mais ce sont un même cycle, qui est en fait l'identité)

Les cycles de longueur 2 sont:
(1 2) , (1 3) et (2 3)
Il y en a 3. Les cycles de longueur 2 sont appelées des transpositions.

Les cycles de longueur 3 sont:
(1 2 3) et (1 3 2)

Je raisonne avec l'ensemble {1, ..., n}, mais on peut raisonner avec {0, 1, ..., n} comme vous le faites.

[A voir en vidéo sur Futura]