Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques DétentePour discuter des JFF, des problèmes intéressants. ExercicesExercices ludiques [tout]Lister tous les topics de mathématiques
Niveau exercices
Partager :

Nombre de surjections

Posté par
flight 18-03-23 à 22:04

Bonsoir,

Je vous propose l'exercice suivant  .. tout simplement , il s'agit de calculer le nombre de surjections d'un ensemble à n+3 elements dans un ensemble à n elements  .

Posté par
matheux14re : Nombre de surjections 18-03-23 à 22:22

 Cliquez pour afficher

Posté par
jarod128re : Nombre de surjections 18-03-23 à 22:40

Bonjour. Il y a la formule qui donne le nombre de surjections d'un ensemble à p éléments dans un ensemble à q éléments:
S_{p,q}=\sum _{k=0}^{q}(-1)^{q-k}{\binom {q}{k}}k^{p} d'où
S_{n+3,n}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{n+3}=\frac{n^2(n+1)(n+3)!}{48}

Posté par
jarod128re : Nombre de surjections 18-03-23 à 22:41

oups, j'ai oublié de blanker :

Posté par
jandri Correcteurre : Nombre de surjections 18-03-23 à 22:43

Bonjour,

il y a trois cas à distinguer :

 Cliquez pour afficher

On obtient un résultat final très simple :
 Cliquez pour afficher

Posté par
matheux14re : Nombre de surjections 18-03-23 à 22:45

Bonjour jarod128, Cette formule n'est rien d'autre que la formule du principe d'inclusion-exclusion.

Posté par
flightre : Nombre de surjections 19-03-23 à 05:38

Bravo à vous tous

Posté par
jandri Correcteurre : Nombre de surjections 20-03-23 à 11:18

@jarod128
comment démontres-tu \sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{n+3}=\dfrac{n^2(n+1)(n+3)!}{48} ?

Posté par
matheux14re : Nombre de surjections 27-03-23 à 12:11

jandri @ 20-03-2023 à 11:18

@jarod128
comment démontres-tu \sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{n+3}= \dfrac{n^2(n+1)(n+3)!}{48} ?



\Large \begin{aligned} \\ \sum_{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{n+3} &= \sum_{k=0}^{n}(-1)^{k}{\binom {n}{k}}k^{n+3} \quad \text{(On remplace } n-k \text{ par } k)\ \\ &= \sum_{k=0}^{n}{\binom {n}{k}}(-1)^{k}k^{n+3} \quad \\ &= \sum_{k=0}^{n}{\binom {n}{k}}(-1)^{k} {\sum_{i=0}^{n+3}{\binom {n+3}{i}}k^{i} \quad \text{(Binôme de Newton)}^{{\red{1}}}\\ \\ &= \sum_{i=0}^{n+3}{\binom {n+3}{i}}\sum_{k=0}^{n}{\binom {n}{k}}(-1)^{k}k^{i} \\ \\ &= \sum_{i=0}^{n+3}{\binom {n+3}{i}}\Delta^{n}((-1)^{k}k^{i})_{k=0} \quad \text{(Méthode de différences finies)} \\ \\ &= \sum_{i=0}^{n+3}{\binom {n+3}{i}}\Delta^{n}(k^{i}){k=0} \quad \text{(car } \Delta^{n}((-1)^{k}){k=0} = 0 \text{ pour tout } n\geq 1 \text{)} \\ \\ &= \sum_{i=0}^{n+3}{\binom {n+3}{i}}(n+1)^{\underline{i}} \quad \text{(avec} x^{\underline{i}} \text{ la notation pour } x(x-1)(x-2)\cdots(x-i+1) \text{)} \\ \\ &= (n+1)^{\underline{3}}\sum_{i=0}^{n+3}\frac{(n+1)^{\underline{i}}}{i!}{\binom {n+3}{i}} \\ \\ &= (n+1)(n+2)(n+3)\sum_{i=0}^{n+3}\frac{(n+1)^{\underline{i-1}}}{(i-3)!}{\binom {n+3}{i}} \\ \\ &= \frac{n^2(n+1)(n+3)!}{48} \quad \text{(Formule du binôme de Newton généralisé)} \\ \end{aligned}

Démonstration de 1 :

\Large \begin{aligned} \\ (-1+k)^{n+3} &= \sum_{i=0}^{n+3}{\binom {n+3}{i}}(-1)^{i}k^{i} \ \\ \Longrightarrow \sum_{k=0}^{n}{\binom {n}{k}}(-1)^{k}k^{n+3} &= \sum_{k=0}^{n}{\binom {n}{k}}(-1)^{k}(-1+k)^{n+3} \ \\ &= \sum_{k=0}^{n}{\binom {n}{k}}(-1)^{k}\sum_{i=0}^{n+3}{\binom {n+3}{i}}k^{i} \quad \text{(en utilisant le théorème du binôme de Newton)} \\ \end{aligned}

Posté par
jandri Correcteurre : Nombre de surjections 27-03-23 à 18:19

@matheux14

Merci d'avoir détaillé ta démonstration. Je t'ai posé la question car l'égalité que tu avais écrite le 18-03-23 à 22:40 semblait immédiate, je vois que ce n'est pas du tout immédiat !

Mais il y a des coquilles dans ce que tu as écrit ci-dessus : dès la première ligne tu n'as pas remplacé k par n-k partout, ensuite je ne vois pas d'où sort ce -1+k dans le renvoi (1), etc...

Dans cet exercice il n'est pas intéressant d'utiliser la formule générale pour le nombre de surjections, il est beaucoup plus rapide de distinguer les trois cas que j'ai indiqués le 18-03-23 à 22:43.

Posté par
matheux14re : Nombre de surjections 27-03-23 à 22:07

Citation :
dès la première ligne tu n'as pas remplacé k par n-k partout


Pourtant

n - k = k \iff n = 2k,

\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{n+3} = \sum _{k=0}^{2k}(-1)^{k}{\binom {2k}{k}}k^{2k+3} = \sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}k^{n+3}

Il y a effectivement une coquille dans le renvoi (1), en fait j'ai recopié un faux brouillon..

Posté par
jandri Correcteurre : Nombre de surjections 27-03-23 à 23:01

Je ne suis pas d'accord, si on remplace k par n-k cela donne :

\\ \sum_{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}k^{n+3} = \sum_{k=0}^{n}(-1)^{k}{\binom {n}{k}}(n-k)^{n+3}

Posté par
flightre : Nombre de surjections 28-03-23 à 13:26

bonjour ici sans utiliser la formule donnant le nombre de surjections

le nombre de surjections de n+3 dans n elements  peut se calculer tout simplement en donnant les dispositions possibles de :
a) 222111....11   ici n termes
b) 321111....11   ici n termes
c) 411111....11   ici n termes
(a) on a ( C(n+3,2).C(n+1,2).C(n-1,2).C(n-3,1)....C(1,1) ).C(n,3).
(b) on a   ( C(n+3,3).C(n,2).C(n-2,1).C(n-3,1)....C(1,1) ).C(n,2).2!
(c) on a C(n+3,4).C(n-1,1).C(n-2,1).C(n-3,1)....C(1,1)).n
soit en tout :   (n+3)! (C(n,3)/8  + C(n,2)/6 + n/4!) = n²(n+1)(n+3)!/48

Posté par
jarod128re : Nombre de surjections 28-03-23 à 18:24

Bonsoir, j'avais oublié ce topic. Je reviens donc pour lever le voile sur ma réponse. jandri C'est moi le post de 22:40 avec la formule de sommation et la réponse toute finie. En fait j'ai donné la formule générale appliquée à la question posée puis j'ai donné la réponse en distinguant les 3 cas comme certains l'ont fait. Cela faisait joli comme réponse

Posté par
jandri Correcteurre : Nombre de surjections 28-03-23 à 21:17

@jarod128
Merci pour cette explication et excuse-moi de ne pas avoir regardé qui avait posté à 18-03-23 à 22:40 (je n'avais pas fait remarqué que matheux14 avait répondu à ta place)

Pour calculer le nombre de surjections d'un ensemble E à n+3 éléments dans un ensemble F à n éléments je dénombre les partitions de E en n parties puis je multiplie par n! (nombres de bijections de l'ensemble des n parties dans F

Cela donne en distinguant les trois cas que j'avais indiqués le18-03-23 à 22:43 :

\Large\left( \binom {n+3}{4}+\binom {n+3}{5}\binom {5}{2}+\binom {n+3}{6}\times5\times3\right)n!=\dfrac{n^2(n+1)(n+3)!}{48} \\


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

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 !