Nombre d'applications

[hamdo]

Soit E={1;2;...;n} , où n est un entier naturel supérieur ou égal à 1.
C'est quoi le nombre d'applications de E vers E vérifiant

[Lierre Aeripz]

Un tel f est nécessairement bijectif, donc est une permutation. Utilise ensuite la décomposition en cycle à support disjoint pour et obtient une condition sur la taille de ces cycles. Ce n'est ensuite qu'un problème de dénombrement qui se résout à coup de coefficients binomiaux.

[hamdo]

un tel f est composée de transpositions , on calcule d'abord de nombre de celles qui sont composée d'une seule transposition , Il en a etc...

[ffpower]

je pense que c bon

[ThSQ]

Je dois me tromper car ce problème ne me parait pas si simple :mur: ...

Comme dit par Pierre c'est le nombre de partitions de {1,..,n} en sous-ensembles de taille 1 ou 2 = u(n).

Deux attaques, "infructueuses" :

Attaque n° 1 :

u(n) = u(n-1) + (n-1)*u(n-2) (suivant que l'élément ajouté est envoyé sur lui-même ou non (auquel cas il faut choisir la place qu'il occupe))
Même en passant par des fonctions génératrices je vois pas de formules "simples" pour u(n) ...

Attaque n° 2 :



(on choisit 2k éléments qu'on distribue en couples)

Pas trouvé comment simplifier ce machin ...


hamdo, on te demande une formule explicite ? Je serais enchanté d'avoir la réponse !!

[Lierre Aeripz]

Je pense que la bonne formule est


Il y a un téléscopage de terme et on trouve

La formule est juste au moins pour n = 3 et n = 4

[ThSQ]

Je pense que la bonne formule

Je pense que nos deux formules sont strictement les mêmes ...... sauf que tu t'es trompé et que les indices commencent à 0. :ptdr:

[Lierre Aeripz]

Je pense que nos deux formules sont strictement les mêmes ...... sauf que tu t'es trompé et que les indices commencent à 0. :ptdr:

Tu as raison ! J'avais oublié l'identité.