Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

Dénombrement de fonctions surjectives

Posté par
Lochenmeteo
21-03-17 à 20:10

Soit F l'ensemble des application surjectives et bijectives de A vers B où card (A) = p et card (B)=q avec p>=q:

prouvez que S(p,q)=q[ S(p-1,q) + S(p-1,q-1) ]

où S(p,q)= card(F)
Aucun problème pour les cas particulier S(p,1)=1 et S(p,p)=p! (bijection) ça va...
mais pour le cas général, c'est la galère et elle coule..
Un indice serait le bienvenu!

Posté par
carpediem
re : Dénombrement de fonctions surjectives 21-03-17 à 20:15

salut

encore un énoncé foireux

pour être bijective il faut le même cardinal ...

Posté par
Lochenmeteo
re : Dénombrement de fonctions surjectives 21-03-17 à 20:32

Éclaircissement

Lire p>= q , c'est-à-dire. p plus grand ou égal à q
si p>q , c'est une surjection
si p=q , c'est une bijection.

Posté par
jandri Correcteur
re : Dénombrement de fonctions surjectives 22-03-17 à 15:46

Bonjour,

Je suppose que A=\{1,2,...,p\}.
Il y a q choix possibles pour l'image de p.
Pour chacun de ces choix il faut choisir les images des entiers de 1 à p-1. Il y a deux cas:
soit on définit une surjection de \{1,2,...,p-1\} sur B, soit on définit une surjection de \{1,2,...,p-1\} sur B privé de l'image de p.

Posté par
etniopal
re : Dénombrement de fonctions surjectives 22-03-17 à 16:01

Lochenmeteo
                    C'est quoi l'énoncé correct ?

Posté par
Lochenmeteo
re : Dénombrement de fonctions surjectives 22-03-17 à 21:01

En réponse à etniopal
Mes excuses pour la confusion, je reprends l'énoncé du problème est espérant
que ce sera plus compréhensible...

Soit S(p,q) représentant le nombre d'application (mapping) surjective d'un ensemble
à  p éléments vers un ensemble à q éléments (p est plus grand ou égal à q).
Prouvez que :
                                         S(p,q)=q[S(p-1,q)+S(p-1,q-1)]

Les cas évidents sont lorsque  S(p,1)=1 et pour la bijection (q=p) S(p,p)= p!
Voilà.

Mes salutations à jandri!
Je me penche sur ta réponse et te reviendrai
là-dessus pour vérifier si j'ai bien compris.

Posté par
Lochenmeteo
re : Dénombrement de fonctions surjectives 22-03-17 à 23:35

Mille fois merci Jandri!

Si j'ai bien compris , on décompose les combinaisons des éléments des deux ensembles A X B en partitions ( par définitions mutuellement exclusives). En ce qui me concerne, mon problème est réglé! ...Cependant et oui , là j'avoue que je charrie, il y aurait-il moyen de faire autrement (par équation) sans que ce soit trop tarabiscoté (par exemple , dans le forum voir la réponse de cailloux sous le sujet "Dénombrement-surjections" ou quelque chose dans le genre mais en plus simple)?
Sinon, tant pis!

Posté par
jandri Correcteur
re : Dénombrement de fonctions surjectives 23-03-17 à 10:04

Il n'existe pas de formule simple pour le nombre de surjections de A vers B où card (A) = p et card (B)=q avec p>=q.
Il y a seulement une formule avec un sigma.
On peut la démontrer par récurrence en utilisant la relation S(p,q)=q*( S(p-1,q) + S(p-1,q-1) ).
J'ai seulement donné l'idée de la démonstration de cette relation.
Il ne s'agit pas de combinaisons d'éléments de A X B. Il faut construire une surjection de A vers B en donnant une image à chaque élément de A. Pour faire intervenir S(p-1,q) et S(p-1,q-1) on choisit un élément particulier de A (j'ai choisi p) qui a comme image n'importe quel élément de B, puis on choisit les images des autres éléments de a en s'assurant qu'on définit bien une surjection de A vers B. Il y a alors deux cas à distinguer.

Posté par
jsvdb
re : Dénombrement de fonctions surjectives 23-03-17 à 11:08

Bonjour à tous.

Je souhaiterais comprendre pourquoi  ce raisonnement n'est pas bon :

Si je note \Omega = \text{Card}(A), \alpha =\text{Card}(B) avec \Omega \geq \alpha.

Pour construire mes surjections de A dans B, je prends d'abord \alpha éléments de A que j'affecte bijectivements aux éléments de B et les \Omega - \alpha éléments restants de A sont entièrement libres.

On aurait donc pour \alpha éléments fixés de A, \alpha ! bijections, puis j'ai la possibilité de prendre \binom{\alpha}{\Omega} paquets de \alpha éléments de A et j'aurai donc \alpha !.\binom{\alpha}{\Omega}.\alpha^{(\Omega -\alpha)} surjections de A dans B.

Je vois bien que, dans les calculs, la formule ne marche pas avec \alpha = 1 puisqu'à ce moment là je trouve \Omega surjections alors qu'il n'y a qu'une application possible. (évidemment si \Omega > 1 ... on est d'accord ) mais je n'arrive pas à raccorder cette conclusion calculatoire avec une erreur de raisonnement.

Merci bien !

Posté par
jandri Correcteur
re : Dénombrement de fonctions surjectives 23-03-17 à 11:23

Bonjour jsvdb,

Il y a d'abord une coquille, c'est \Omega\choose \alpha.

Ensuite ton raisonnement compte plusieurs fois chaque surjection.
Un élément x qui n'est pas parmi les \alpha aura pour image un y qui est déjà l'image de z, l'un des \alpha. Si on échange les rôles de x et z on obtient la même surjection pour une autre partie de \alpha éléments.

Posté par
lionel52
re : Dénombrement de fonctions surjectives 23-03-17 à 11:24

Un petit exemple !

{0,1,2,3} dans {0,1,2}

Tu choisis {0,1,2}  dans A => tu poses f(0) = 0, f(1) = 1 et f(2) = 2. Et f(3) = 0
Tu choisis {1,2,3} dans A => tu poses f(1) = 1, f(2) = 2 et f(3) = 0. Et f(0) = 0  

Posté par
jsvdb
re : Dénombrement de fonctions surjectives 23-03-17 à 12:06

Okay super ! merci messieurs, je vois où mon raisonnement foire : je n'ai pas créé par ce biais une partition de l'ensemble des surjections.

Posté par
Lochenmeteo
re : Dénombrement de fonctions surjectives 23-03-17 à 19:11

Salut Jandri!
Encore merci  pour tes explications complémentaires.
En ce qui me concerne c'est une affaire classée.

Posté par
Lochenmeteo
re : Dénombrement de fonctions surjectives 30-03-17 à 03:00

Salut!

Juste un petit ajout, j'ai trouvé un formule explicite lorsque q=p-1...

S(p,p-1)=(p-1)! \left[p(p-1)/2 \right]

Posté par
jandri Correcteur
re : Dénombrement de fonctions surjectives 30-03-17 à 10:43

Bonjour Lochenmeteo,

C'est juste.
On peut aussi écrire une formule explicite pour q=p-2:

S(p,p-2)=\dfrac{(p-2)(3p-5)p!}{24}.

Mais pour S(p,p-3) cela se complique.

Posté par
veleda
re : Dénombrement de fonctions surjectives 30-03-17 à 14:50

bonjour,
pour S(p,p-3) j'avais trouvé (il ya quelques années!)
  \frac{ (p-3)^2(p-2)p!}{48}
cela a l'air correct mais je manque de courage pour refaire le calcul

Posté par
jandri Correcteur
re : Dénombrement de fonctions surjectives 30-03-17 à 15:08

Bonjour veleda,

J'ai vérifié, ta formule est exacte.
Je ne pensais pas que le résultat se factorisait aussi bien.
En fait ce n'est pas si compliqué à calculer, il y a trois cas à distinguer:

S(p,p-3)=(p-3)!\left(\dfrac{p!}{4!(p-4)!}+\dfrac{p!}{3!2!(p-5)!}+\dfrac1{3!}\dfrac{p!}{2!2!2!(p-6)!}\right).

Posté par
Lochenmeteo
re : Dénombrement de fonctions surjectives 31-03-17 à 03:29

Bonjour Jandri.

Es-tu bien sûr pour ta formule de S(p,p-3)?

Si  p=5,  tu es pris avec (p-6)! négatif, même avec mon combinatoire
très rouillé, il me semble qu'il y a là quelque chose de bizarre, non?

Posté par
jandri Correcteur
re : Dénombrement de fonctions surjectives 31-03-17 à 10:05

Bonjour Lochenmeteo,

Tu as parfaitement raison de refuser la factorielle d'un entier négatif!
J'aurais du préciser que mon expression est valide seulement quand p\geq6.
Pour p=5 le dernier terme de la somme doit être remplacé par 0 (le cas correspondant n'existant pas).
Pour p=4 les deux derniers termes de la somme doivent être remplacés par 0.
Mais la forme simplifiée de mon expression (donnée par veleda) est bien valable pour p\geq4.

Posté par
veleda
re : Dénombrement de fonctions surjectives 31-03-17 à 17:51

ma démonstration utilisait
*  les dérivées de f_n(x)= (e^x-1)^n=\sum_{k=0}^nC_n^ke^{kx} (-1)^{n-k}
f_n^p(x)=\sum_{k=0}^nC_n^kk^pe^{kx}(-1)^{n-k}
donc
f_n^p(0)=\sum_{k=0}^nC_n^kk^p(-1)^{n-k}=S_n^p

* deux écritures différentes du d.l. à l'ordre  n+ 3   de f_n au voisinage de 0
l'une utilisant  le théorème de T- Y
l'autre partait du d.l. de e^x-1 à l'ordre 4
cela fait quand même beaucoup de calculs



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !