Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup AnalyseTopics traitant de analyse [tout]Lister tous les topics de mathématiques

1 2 +

Niveau Maths sup
Partager :

Nombre de surjections S(n,p)

Posté par Profil Ramanujan 09-07-18 à 20:50

Bonsoir,

Je bloque complètement sur cette exercice. J'ai du mal avec le dénombrement, donc j'aimerais aller doucement. Je trouve ce chapitre difficile.

Soit n \in \N^{*}
Soit E un ensemble de cardinal n et F un ensemble de cardinal p.
On note S(n,p) le nombre de surjections d'un ensemble E de cardinal n dans un ensemble F de cardinal p.

Soit f une application de E dans F.  On peut toujours dire que f définit une surjection de E dans f(E). Notons k le cardinal de f(E), on a :
1 \leq k \leq p

Jusque là tout va bien.

Combien y a-t-il d'applications de E dans F ? Exprimer ce nombre en fonction des S(n,k)

Je comprends pas pourquoi on doit utiliser le nombre de surjections pour calculer toutes les applications de E dans F.
Je vois pas comment procéder.

Posté par
verdurinre : Nombre de surjections S(n,p) 09-07-18 à 20:56

Bonsoir,
on connaît évidement le nombre d'applications de E dans F : pn.

On va essayer d'exprimer cette valeur à l'aide des S(n,k) pour calculer les S(n,k).

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 09-07-18 à 21:18

Oui ça j'ai compris, d'ailleurs à la question précédente, on démontre par récurrence la formule d'inversion de Pascal par récurrence (assez difficile).

Mais je vois pas trop la méthode avec les S(n,k).

Posté par
verdurinre : Nombre de surjections S(n,p) 09-07-18 à 21:27

J'ai répondu à la question que tu postas.

Si tu voulais en poser une autre, pose la.

Posté par
Jezebethre : Nombre de surjections S(n,p) 10-07-18 à 01:52

Bonsoir

Au passage dans l'esprit pas besoin de redémontrer la formule de Pascal. En tout cas ce n'est pas le point clé de l'exercice (et la démo est classique).

On peut commencer par mq S(n+1,p) = pS(n,p) + pS(n,p-1).

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 10-07-18 à 03:14

verdurin @ 09-07-2018 à 21:27

J'ai répondu à la question que tu postas.

Si tu voulais en poser une autre, pose la.


Je vois pas le lien entre le nombre d'application p^n et les S(n,k) j'arrive pas à avancer dans l'exercice.

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 10-07-18 à 03:15

Jezebeth @ 10-07-2018 à 01:52

Bonsoir

Au passage dans l'esprit pas besoin de redémontrer la formule de Pascal. En tout cas ce n'est pas le point clé de l'exercice (et la démo est classique).

On peut commencer par mq S(n+1,p) = pS(n,p) + pS(n,p-1).


D'après l'indication, il ne faut pas utiliser cette méthode. Mais une méthode directe puis l'inversion de Pascal.

Posté par
flightre : Nombre de surjections S(n,p) 10-07-18 à 11:15

salut

je vais tenter une explication plus" pratique et concrete" ..apres c'est à verifier pour la question de rigueur :
si E à n elements et F , p elements  alors  le nombre d'applications possibles est toutes les facons de joindre à un elements de E un elements de F , donc deja  
si E={e1,e2,e3,....en}    et F={f1,f2,....,fp}    alors pour e1 j'ai "p" choix , pour e2 j'ai "p" choix
..pour en j'ai "p" choix  soit  donc p.p.p...p = pn  choix  c'est un peu comme le cardinal de l'univers .
ensuite  pour le nombre de  surjections l'exercice est equivalent à remplir p boites avec n objets discernables et avec la contrainte "au moins un objet par boite".
en pratique on va donc calculer card( au moins un element dans la boite f1 au moins un element dans la boite f2......au moins un element dans la boite fp)   mais ceci ce calcul avec le complementaire  à savoir   card()  (qui vaut pn) - card( aucun element dans f1 U  aucun element dans f2 U....U aucun element dans fp)    et
card( aucun objet dans f1 U  aucun objet dans f2 U....U aucun objet dans fp)  se calcul avec la formule du crible ..sauf erreur
donc S(n,p) = pn - formule du crible  

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 10-07-18 à 12:31

@Flight

Intéressant mais je doit résoudre l'exercice sans la formule du crible. Elle n'a pas été vue.

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 10-07-18 à 12:44

Il y a une correction dans mon livre mais j'y comprends rien. Je vous la mets.

Nous avons S(n,k) façons de choisir une surjection de E dans un ensemble de cardinal k.

Nous obtenons :

\sum_{k=1}^{p}  \binom{p}{k}  S(n,k) applications de E dans F.

* Je comprends pas pourquoi on fait le produit \binom{p}{k} \times S(n,k)

* Je comprends pas pourquoi cette somme donne toutes les applications de E dans F : j'aurais dit (même si j'ai pas compris) qu'elle donne toutes les surjections de E dans F.

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 10-07-18 à 12:55

flight @ 10-07-2018 à 11:15

salut

je vais tenter une explication plus" pratique et concrete" ..apres c'est à verifier pour la question de rigueur :
si E à n elements et F , p elements  alors  le nombre d'applications possibles est toutes les facons de joindre à un elements de E un elements de F , donc deja  
si E={e1,e2,e3,....en}    et F={f1,f2,....,fp}    alors pour e1 j'ai "p" choix , pour e2 j'ai "p" choix
..pour en j'ai "p" choix  soit  donc p.p.p...p = pn  choix  c'est un peu comme le cardinal de l'univers .
ensuite  pour le nombre de  surjections l'exercice est equivalent à remplir p boites avec n objets discernables et avec la contrainte "au moins un objet par boite".
en pratique on va donc calculer card( au moins un element dans la boite f1 au moins un element dans la boite f2......au moins un element dans la boite fp)   mais ceci ce calcul avec le complementaire  à savoir   card()  (qui vaut pn) - card( aucun element dans f1 U  aucun element dans f2 U....U aucun element dans fp)    et
card( aucun objet dans f1 U  aucun objet dans f2 U....U aucun objet dans fp)  se calcul avec la formule du crible ..sauf erreur
donc S(n,p) = pn - formule du crible  


Sinon, j'ai pas compris la différence entre :

- "Aucun élément dans f1" et "aucun objet dans f1"

Posté par
flightre : Nombre de surjections S(n,p) 10-07-18 à 13:26

en effet ..correction : card("Aucun objet dans f1" et "aucun objet dans f2" et .... et aucun dans fn)

Posté par
flightre : Nombre de surjections S(n,p) 10-07-18 à 13:31

pas reveillé  S(n,p)=  pn - card("Aucun objet dans f1" U "aucun objet dans f2" U .... U aucun objet dans fn)

Posté par
Jezebethre : Nombre de surjections S(n,p) 10-07-18 à 14:56

Soit E de card n, F de card p.
Pour construire une application de E vers F, il faut et il suffit de choisir une partie de F de card k (k étant un entier entre 0 et p) pour former Im(f), puis de construire une surjection de E vers Im(f), ce qui laisse s(n,k) possibilités. Il vient donc :

p^n=\sum_{k=0}^{p}\begin{pmatrix}p\\ k \end{pmatrix}s(n,k)

La formule d'inversion de Pascal donne immédiatement le résultat...

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 10-07-18 à 15:17

Merci Jezebeth super clair !

Un petit détail : du coup dès qu'on a choisit l'ensemble image, le S(n,k) correspond aux nombres de surjections qu'on peut construire sur ce même ensemble image en sélectionnant différents antécédents de E ?

Posté par
Jezebethre : Nombre de surjections S(n,p) 10-07-18 à 15:18

S(n,k) est par déf le nombre de surjections d'un ensemble à n éléments (E) vers un ensemble à k éléments (Im(f)).

Posté par
etniopalre : Nombre de surjections S(n,p) 10-07-18 à 16:57

Mon grain de sel !
La somme \sum_{k=0}^{p}\begin{pmatrix}p\\ k \end{pmatrix}s(n,k) peut provenir du calcul du cardinal d'un ensemble X  dont on a une partition en p sous ensembles X1 ,....,Xp ,  le cardinal de  chaque Xk étant C(p,k)S(n,k) .

Ce C(p,k)S(n,k) peut s'interpréter comme le cardinal d'un  ensemble produit A[/sub] x B[sub]k tel que Card(A[/sub]) = C(p,k) et  Card( B[sub]k) =  S(n,k) .

Comme pn est le cardinal de  U(n,p) = {1,...p} {1,...n} on va donc partitionner U(n,p) en p parties  X1 ,....,Xp .
Reste à trouver les  A[/sub] ,  B[sub]k .

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 10-07-18 à 17:02

Jezebeth @ 10-07-2018 à 14:56

Soit E de card n, F de card p.
Pour construire une application de E vers F, il faut et il suffit de choisir une partie de F de card k (k étant un entier entre 0 et p) pour former Im(f), puis de construire une surjection de E vers Im(f), ce qui laisse s(n,k) possibilités. Il vient donc :

p^n=\sum_{k=0}^{p}\begin{pmatrix}p\\ k \end{pmatrix}s(n,k)

La formule d'inversion de Pascal donne immédiatement le résultat...


Quand vous utiliser le "puis" dans la phrase en langage mathématique ça se transforme en multiplication ?

J'ai encore un peu de mal avec ça.

Posté par
Jezebethre : Nombre de surjections S(n,p) 10-07-18 à 17:04

Oui en dénombrement quand on écrit "ou" généralement ça cache un partitionnement, et "puis" un produit cartésien.

Vous pouvez construire la bijection à partir de cela.

Posté par Profil RamanujanNombre de surjections entre ensembles finis 11-07-18 à 19:04

Bonjour,

J'essaie de faire un problème. Je n'ai pas le corrigé. J'aimerais juste quelques indications, j'aimerais trouver la solution seul. Je vais peux être donner des solutions stupides mais première fois que je me force à travailler des exos seul sans corrigé.

Je mets les premières questions, mais il y en a plein d'autres que je mettrai au fur et à mesure que je recherche l'exercice.

\forall n \in \N^{*} : E_n = \{1,2,...,n \}

On note S_{n,p} le nombre de surjections de E_n sur E_p.

1/ Calculer  S_{n,p} si p > n.

\forall p > n : S_{n,p}=0

2/ Calculer  S_{n,n},  S_{n,1} et  S_{n,2}.
S_{n,n}=n! on a une bijection en fait.
S_{n,1}=1 c'est assez évident sur un dessin.

J'ai des difficultés pour calculer   S_{n,2}.
Mon raisonnement :
* il faut au moins qu'un élément de E_n n'ait pas la même image que les autres. Je vois pas comment le traduire en langage mathématique.
- autre approche : il faut que f(E_n)=E_2 pareil je vois pas comment le traduire en équation pour calculer le nombre de surjection.

*** message déplacé ***

Posté par
lionel52re : Nombre de surjections S(n,p) 12-07-18 à 08:46

Pour Sn2, on prend un k entre 1 et n.
Je prends une application f telle que le nombre delements x tel que f(x) = 1 vaut k
Combien y a til de telles applications?

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 12-07-18 à 22:16

J'ai trouvé la solution finalement.

Il a 2^n application de E_n dans E_2
Il a que 2 applications non surjectives : les applications constantes égales à 1 ou 2.

S_{n,2}=2^n - 2

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 14-07-18 à 13:31

La suite... Je mets tous mes résultats intermédiaire je suis bloqué à la question 9.

3/ CalculerS_{p+1,p}
Nombre de possibilités de choisir 2 éléments dans E_{p+1}
Nombre de possibilités de choisir l'élément de  E_{p} qui admet 2 antécédents :p
A la fin fin il reste p-1 éléments dans les ensembles d'arrivée et et départ donc il y a : (p-1)! surjections.

J'ai donc : S_{p+1,p}=\binom{p+1}{2} \times p \times (p-1)! = \frac{(p+1)!}{2! (p-1)!} p!= \frac{p(p+1)}{2} p!

Finalement : S_{p+1,p} = \frac{p(p+1)!}{2}

On suppose désormais que 0 < p \leq n
4/ Montrer que \sum_{k=0}^{p} (-1)^k \binom{p}{k}=0
D'après la formule du binôme de Newton : \sum_{k=0}^{p} (-1)^k \binom{p}{k}=(1-1)^p=0

5/ Montrer que 0 \leq k \leq q \leq p \Longrightarrow \binom{p}{q} \binom{q}{k}=\binom{p}{k} \binom{p-k}{q-k}

En développant les 2 coefficients binomiaux :

\binom{p}{q} \binom{q}{k}=\frac{p!}{k!(p-q)!(q-k)!}=\binom{p}{k} \binom{p-k}{q-k}

6/ En déduire que, si 0 \leq k < p alors : \sum_{q=k}^{p} (-1)^q \binom{p}{q} \binom{q}{k}=0
Et si k=p ?

En changeant l'indice j=q-k, la somme devient

\sum_{q=k}^{p}(-1)^q\binom{p-k}{q-k}=\sum_{j=0}^{p-k}(-1)^{j+k}\binom{p-k}{j}

On peut sortir (-1)^k  et cela donne

\sum_{q=k}^{p}(-1)^q\binom{p-k}{q-k}=(-1)^k\sum_{j=0}^{p-k}(-1)^j\binom{p-k}{j}

Ré-écrivons cela en faisant apparaître 1^{p-k-j} qui vaut bien sûr 1

\sum_{q=k}^{p}(-1)^q\binom{p-k}{q-k}=(-1)^k\sum_{j=0}^{p-k}\binom{p-k}{j}(1)^{p-k-j}(-1)^j

Et la somme est  exactement le développement de (1-1)^{p-k}

Donc si k<p : \sum_{q=k}^{p} (-1)^q \binom{p}{q} \binom{q}{k}=0
Donc si k<p : \sum_{q=k}^{p} (-1)^q \binom{p}{q} \binom{q}{k}=(1-1)^0 (-1)^k = (-1)^k

7/ Déterminer\forall q \in \{1,2,..., p\}, le nombre d'applications de E_n dans E_p ayant un ensemble image à q éléments.

Toute application de  E_n dans E_p  est une surjection de E_n dans f(E_n). Il suffit alors de dénombrer les surjections.
Notons : Card(f(E_n))=q

Possibilités de choisir un ensemble à q éléments dans E_p : \binom{p}{q}

Possibilités de construire une surjection à partir de cet ensemble à q éléments choisi:
S(n,q)

Le nombre d'applications recherché est donc : \binom{p}{q} \times S(n,q)

8/ En déduire que p^n = \sum_{q=1}^{p} \binom{p}{q} \times S(n,q)
D'après le cours, le nombre d'applications de E_n dans E_p est :
Card(E_p)^{Card(E_n)}=p^n

Ensuite, quand on choisit nos q éléments dans E_p pour construire notre surjection, on peut en choisir 1 élément, 2 éléments, jusqu'à p éléments d'où :

p^n = \sum_{q=1}^{p} \binom{p}{q} \times S(n,q)

9/ En utilisant ce qui précède, montrer que : S_{n,p}= (-1)^p \sum_{k=1}^{p} (-1)^k \binom{p}{k} k^n
On cherche à simplifier : A=(-1)^p \sum_{k=1}^{p} (-1)^k \binom{p}{k} k^n

Or : k^n = \sum_{q=1}^{k} \binom{k}{q} \times S(n,q)

On en déduit :

A= (-1)^p \sum_{k=1}^{p} (-1)^k \binom{p}{k} \sum_{q=1}^{k} \binom{k}{q} \times S(n,q)=(-1)^p \sum_{k=1}^{p}  \sum_{q=1}^{k} (-1)^k \binom{p}{k} \binom{k}{q} \times S(n,q)

Or : \sum_{k=1}^{p}  \sum_{q=1}^{k}  = \sum_{q=1}^{p}  \sum_{k=q}^{p}

D'où : A=(-1)^p  \sum_{q=1}^{p}  S(n,q)  \sum_{k=q}^{p} (-1)^k \binom{p}{k} \binom{k}{q}

Mais :  \sum_{k=q}^{p} (-1)^k \binom{p}{k} \binom{k}{q} = (-1)^q

Soit A=(-1)^p  \sum_{q=1}^{p}  S(n,q)  (-1)^q

Et là je suis bloqué

Posté par
Jezebethre : Nombre de surjections S(n,p) 14-07-18 à 14:32

6/ erreur, deux cas k < p

8/ on comprend mais ce n'est pas vraiment une preuve, écrire la réunion d'ensembles disjoints pour justifier la somme

9/ formule d'inversion de Pascal… ça fait une ligne

et ceci :

Ramanujan @ 14-07-2018 à 13:31

Or : \sum_{k=1}^{p}  \sum_{q=1}^{k}  = \sum_{q=1}^{p}  \sum_{k=q}^{p}


est bien laid !

mais sinon votre démo marche aussi, il vous reste à conclure que seul le terme correspondant à q = p est non nul. C'est cette affirmation :

Ramanujan @ 14-07-2018 à 13:31

Mais :  \sum_{k=q}^{p} (-1)^k \binom{p}{k} \binom{k}{q} = (-1)^q


qui n'est vraie que si q = p, vous l'avez montré plus haut. Pour q < p ça fait 0.

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 14-07-18 à 18:21

Pour la question 8, pourriez-vous me montrer la rédaction avec les ensembles disjoints ?

Pour la 9, la formule d'inversion de Pascal n'étant pas exigible, est-ce possible de se débrouiller autrement ?

L'énoncé donne 2 indications :
Transformer le seconde membre à l'aide de la question précédente.
Justifier l'égalité :  \sum_{k=1}^{p}  \sum_{q=1}^{k} ... = \sum_{q=1}^{p}  \sum_{k=q}^{p}...

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 01:54

8/ Poser F_q=\begin{Bmatrix} f:E_n\rightarrow E_p \mid Card(Im(f))=q \end{Bmatrix}...

9/ Alors votre manière de procéder est bien, en tout cas pour l'énoncer que vous avez et qui semble quand même vous diriger dans cette direction (si vous voulez mon avis il y a beaucoup trop d'indications quand même? c'est pas drôle).

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 01:55

**énoncé

Ramanujan @ 14-07-2018 à 18:21

L'énoncé donne 2 indications :
Transformer le seconde membre à l'aide de la question précédente.
Justifier l'égalité :  \sum_{k=1}^{p}  \sum_{q=1}^{k} ... = \sum_{q=1}^{p}  \sum_{k=q}^{p}...


Ils mettent des … après les sommes, au moins.

Vous ne l'avez pas vraiment justifiée d'ailleurs. Il faut passer à la forme \sum_{1\leq q\leq k\leq p}....

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 15-07-18 à 19:42

Jezebeth @ 15-07-2018 à 01:54

8/ Poser F_q=\begin{Bmatrix} f:E_n\rightarrow E_p \mid Card(Im(f))=q \end{Bmatrix}...

9/ Alors votre manière de procéder est bien, en tout cas pour l'énoncer que vous avez et qui semble quand même vous diriger dans cette direction (si vous voulez mon avis il y a beaucoup trop d'indications quand même? c'est pas drôle).


Oui je suis d'accord trop d'indications mais comme j'avais un peu de mal avec ce chapitre tant mieux je pourrais mieux comprendre.

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 15-07-18 à 20:09

Pour la question 8 je dois montrer que : (si je note A l'ensemble des application d'un ensemble dans un autre)

\bigcup_{q \in \{1,...,p\}} F_{q}=A(E_n,E_p)

Et : \bigcap_{q \in \{1,...,p\}} F_{q}=\emptyset

?

Pour pouvoir utiliser que :

Card(F_1 +...+F_p)=Card(A(E_n,E_p))=p^n ?

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 20:11

Ramanujan @ 15-07-2018 à 20:09

Pour pouvoir utiliser que :

Card(F_1 +...+F_p)=Card(A(E_n,E_p))=p^n ?



Qu'est-ce que c'est que cette somme à l'intérieur du cardinal...

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 15-07-18 à 20:19

Ah erreur d'étourderie on est pas dans les espaces vectoriels !

C'est : Card(\bigcup_{q \in \{1,...,p\}} F_{q} ) = F_1 + F_2 + ...+ F_p

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 20:20

Toujours pas.

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 15-07-18 à 20:28

Montrons que \bigcup_{q \in \{1,...,p\}} F_{q}=A(E_n,E_p) par double inclusion.

1/ Soit F \in \bigcup_{q \in \{1,...,p\}} F_{q} alors \exists q \in [|1,p|] tel que : F \in F_i
Mais F_i est une partie de A(E_n,E_p) donc :
\bigcup_{q \in \{1,...,p\}} F_{q} \subset A(E_n,E_p)

2/ Soit F \in A(E_n,E_p) donc : \exists i \in [|1,p|] tel que : F=F_i d'où : F \in \bigcup_{q \in \{1,...,p\}} F_{q} ainsi :
A(E_n,E_p) \subset \bigcup_{q \in \{1,...,p\}} F_{q}

Par double inclusion on a le résultat.

C'est correct ?

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 15-07-18 à 20:30

J'ai trouvé mon erreur c'est plutôt :

Card(\bigcup_{q \in \{1,...,p\}} F_{q} ) = Card(F_1 )+ Card(F_2)+ ...+Card( F_p)

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 20:34

Oui, bon… c'est trivial tout ça. Personnellement j'accepterais qu'on me balance l'égalité.

Clairement

\bigcup_{q=1}^{p}F_q=\bigcup_{q=1}^{p}\left\{f:E_n \rightarrow E_p \mid card(Im(f))=q \right\}

=\left\{f:E_n \rightarrow E_p \mid 1\leq card(Im(f))\leq p \right\}

=A(E_n,E_p)

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 20:36

Ramanujan @ 15-07-2018 à 20:30

J'ai trouvé mon erreur c'est plutôt :

Card(\bigcup_{q \in \{1,...,p\}} F_{q} ) = Card(F_1 )+ Card(F_2)+ ...+Card( F_p)


Oui (là il faudrait sortir l'intersection vide)

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 15-07-18 à 20:56

Jezebeth @ 15-07-2018 à 20:34

Oui, bon… c'est trivial tout ça. Personnellement j'accepterais qu'on me balance l'égalité.

Clairement

\bigcup_{q=1}^{p}F_q=\bigcup_{q=1}^{p}\left\{f:E_n \rightarrow E_p \mid card(Im(f))=q \right\}

=\left\{f:E_n \rightarrow E_p \mid 1\leq card(Im(f))\leq p \right\}

=A(E_n,E_p)


En effet, c'est bien plus rapide !

Par contre je trouve pas trivial de montrer :

\bigcap_{q \in \{1,...,p\}} F_{q}=\emptyset

Il faut forcément raisonner par l'absurde ?

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 22:58

C'est totalement trivial aussi !

F_1 \cap F_2=\varnothing

donc

\bigcap_{i=1}^{p}F_i=F_1 \cap F_2 \cap \bigcap_{i=3}^{p}F_i= \varnothing

Posté par
Jezebethre : Nombre de surjections S(n,p) 15-07-18 à 22:58

(un ensemble ne peut pas être fini de cardinal 1 et de cardinal 2...)

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 16-07-18 à 15:22

C'est pas évident pour moi que l'intersection de 2 ensembles finis de cardinaux différent soit égale à l'ensemble vide.
Et s'il y avait une partie qui s'intersecte entre l'ensemble de cardinal 4 et l'ensemble de cardinal 2 ?

Posté par
Camélia Correcteurre : Nombre de surjections S(n,p) 16-07-18 à 15:28

Bonjour

En l'absence de Jezebeth. A force de pinailler, tu as oublié les définitions de l'énoncé. F_q est l'ensemble des f telles que Im(f) ait q éléments. Donc si q\neq p on a bien F_q\cap F_p=\emptyset puisque Im(f) ne peut pas avoir en même temps p et q éléments!

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 16-07-18 à 18:11

Merci Camélia !

Je reviens à la question 9 où j'étais bloqué :

9/ En utilisant ce qui précède, montrer que : S_{n,p}= (-1)^p \sum_{k=1}^{p} (-1)^k \binom{p}{k} k^n
On cherche à simplifier : A=(-1)^p \sum_{k=1}^{p} (-1)^k \binom{p}{k} k^n

Or : k^n = \sum_{q=1}^{k} \binom{k}{q} \times S(n,q)

On en déduit :

A= (-1)^p \sum_{k=1}^{p} (-1)^k \binom{p}{k} \sum_{q=1}^{k} \binom{k}{q} \times S(n,q)=(-1)^p \sum_{k=1}^{p}  \sum_{q=1}^{k} (-1)^k \binom{p}{k} \binom{k}{q} \times S(n,q)

Or : \sum_{k=1}^{p}  \sum_{q=1}^{k} ... = \sum_{q=1}^{p}  \sum_{k=q}^{p}...
Justification :
En effet : 1 \leq q \leq k \leq p
q varie de 1 à p d'après l'inégalité ci-dessus. Pour q fixé, alors k varie de q à p ...

D'où : A=(-1)^p  \sum_{q=1}^{p}  S(n,q)  \sum_{k=q}^{p} (-1)^k \binom{p}{k} \binom{k}{q}

Et là je coince.

Posté par
Jezebethre : Nombre de surjections S(n,p) 16-07-18 à 18:52

Jezebeth @ 14-07-2018 à 14:32

C'est cette affirmation :

Ramanujan @ 14-07-2018 à 13:31

Mais :  \sum_{k=q}^{p} (-1)^k \binom{p}{k} \binom{k}{q} = (-1)^q


qui n'est vraie que si q = p, vous l'avez montré plus haut. Pour q < p ça fait 0.

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 16-07-18 à 23:58

Ah je viens de trouver !

La somme étant nulle sauf pour q=p on obtient en remplaçant tous les q par p:

A=(-1)^p S(n,p) (-1)^p = (-1)^{2p} S(n,p) =S(n,p)

Posté par
Jezebethre : Nombre de surjections S(n,p) 16-07-18 à 23:58

oui

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 17-07-18 à 00:22

Je mets la suite.
10/ Montrer que si 0 < p \leq n-1 alors :

S_{n,p} = p  \times (S_{n-1,p}+S_{n-1,p-1})

Indication : étant donné une surjection \varphi de E_n dans E_p on pourra considérer sa restriction \varphi_1  à E_{n-1}.

J'ai des difficultés sur cette question :

On peut construire S_{n-1,p} surjections de E_{n-1} sur E_p et il reste un élément dans E_n à placer...
Je sèche sur mon brouillon.

Posté par
lafol Moderateurre : Nombre de surjections S(n,p) 17-07-18 à 13:09

tu n'as pas suivi l'indication ....

Posté par Profil Ramanujanre : Nombre de surjections S(n,p) 18-07-18 à 18:00

J'ai pas compris l'indication...

Posté par
Jezebethre : Nombre de surjections S(n,p) 18-07-18 à 18:02

Je vois pas comment on peut ne pas la comprendre… ne pas savoir quoi en faire à la rigueur oui.

Posté par
lafol Moderateurre : Nombre de surjections S(n,p) 18-07-18 à 18:04

as-tu considéré la restriction demandée ? t'es-tu demandé, au hasard, si elle est surjective ou pas ? (me demande bien comment on peut avoir cette idée, dans un exercice qui porte sur le nombre d'applications surjectives .... faudrait que tu y mettes un peu du tien aussi !)

1 2 +


Rechercher
Menu
Espace membre
Changer d'île

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 !