Nombre de surjections

[mehdi-128]

Bonsoir,

Pour (n,p) appartenant à N*, S_{n,p} désigne le nombre de surjections de [|1,n|] dans [|1,p|].

Je bloque sur les questions 4 et 5 de l'exo suivant. J'ai réussi les autres, j'aimerais savoir si c'est correct.

1) Que dire de Sn,p si p>n
Sn,p=0 si p>n

2) Déterminer Sn,1 et Sn,n.
Sn,1=1
Car f(1)=1 , f(2)=1 , f(3)=1 , ... , f(n)=1 est la seule application f qui va de [1,n] dans [1] et elle est surjective.
Pour Sn,n
On choisit d'abord f(1). Il y a n choix pour f(1) : 1,..,n. Pour f(2) il y a n-1 choix. Pour f(3) il y a n-2 choix.
Donc pour f(n) il y a 1 choix.
D'où : Sn,n=n(n-1)(n-2)...1=n!

3) Combien d'applications de [|1,n|] dans [|1,2|] sont non surjectives ? En déduire Sn,2
Il y a 2 applications non surjectives de [|1,n|] dans [|1,2|].
La première est : f(1)=1 .... f(n)=1
La deuxième est : f(1)=2 .... f(n)=2
Or il y a 2^n applications de [|1,n|] dans [|1,2|].
Sn,2=2^n-2

4) Montrer que S_{n,3}=3^n-3-3S_{n,2}

5) Si 0k

Sum_{q=k}^{p} (-1)^q C_{p,q} C_{q,k} = 0

Merci.

[Skullkid]

Ok pour celles auxquelles tu as répondu, et content de voir que tu as mis de te côté ta notation avec les accolades :p

Pour la 4, il te faut exprimer Sn,3 en fonction de Sn,2 donc il va falloir d'une façon ou d'une autre relier les applications surjectives de |[1,n]| dans {1,2,3} à celles de |[1,n]| dans {1,2}. Essaye de faire comme à la question 3 : compte les applications non surjectives.

[mehdi-128]

Ok pour celles auxquelles tu as répondu, et content de voir que tu as mis de te côté ta notation avec les accolades :p

Pour la 4, il te faut exprimer Sn,3 en fonction de Sn,2 donc il va falloir d'une façon ou d'une autre relier les applications surjectives de |[1,n]| dans {1,2,3} à celles de |[1,n]| dans {1,2}. Essaye de faire comme à la question 3 : compte les applications non surjectives.

Les applications surjectives de |[1,n]| dans {1,2,3} :

Je compte 3 applications non surjectives de |[1,n]| dans {1,2,3} :

f(1)=f(2)=...=f(n)=1

f(1)=f(2)=...=f(n)=2

f(1)=f(2)=...=f(n)=3

Je sais qu'il y a 3^n applications de |[1,n]| dans {1,2,3}.

Mais ensuite je bloque.

[Skullkid]

Il y a plus de 3 applications non surjectives de |[1,n]| dans {1,2,3} ! Les 3 applications que tu donnes sont les applications constantes de |[1,n]| dans {1,2,3}. Elles sont certes non surjectives, mais une application peut ne pas être surjective sans pour autant être constante !

Par exemple f(k) = k pour tout k < n et f(n) = n-1. Cette application n'est ni surjective ni constante.

Pour compter le nombre d'applications non surjectives, il faut que tu comprennes comment on peut construire, en toute généralité, une application non surjective de |[1,n]| dans {1,2,3}. Pour t'aider, comment traduire le fait que f est (ou non) surjective en utilisant l'ensemble image de f ?

[mehdi-128]

Il y a plus de 3 applications non surjectives de |[1,n]| dans {1,2,3} ! Les 3 applications que tu donnes sont les applications constantes de |[1,n]| dans {1,2,3}. Elles sont certes non surjectives, mais une application peut ne pas être surjective sans pour autant être constante !

Par exemple f(k) = k pour tout k < n et f(n) = n-1. Cette application n'est ni surjective ni constante.

Pour compter le nombre d'applications non surjectives, il faut que tu comprennes comment on peut construire, en toute généralité, une application non surjective de |[1,n]| dans {1,2,3}. Pour t'aider, comment traduire le fait que f est (ou non) surjective en utilisant l'ensemble image de f ?

J'ai pas trop compris pourquoi f(k) = k pour tout k < n et f(n) = n-1 n'est pas surjective. Pourquoi les nombres 1,2 et 3 n'apparaissent pas dans l'image ?

Sinon, une application surjective de |[1,n]| dans {1,2,3} doit vérifier :

Tous les points de l'image (1, 2 et 3) doivent être atteints.

Par exemple :

f(1)=1
f(2)=2
f(3)=3
.
.
.
f(n)=3

[Skullkid]

Ouais désolé pour mon exemple j'ai oublié d'écrire que je parlais d'une application de |[1,n]| dans lui-même... Enfin tout ça pour dire qu'il y a des applications non surjectives et non constantes. Quand l'ensemble d'arrivée était {1,2}, ça n'était pas le cas, mais maintenant l'ensemble d'arrivée a strictement plus de 2 éléments.

As-tu vu la notion d'image d'un ensemble ? Si f est une application de E dans F, f(E) est l'ensemble formé par les images des éléments de E. Dire que f est surjective équivaut à dire que f(E) = F (tous les éléments de F peuvent s'écrire comme l'image d'un élément de E).

Du coup, f non surjective ça veut dire que f(E) est strictement inclus dans F. Dans notre cas, f non surjective signifie que f(|[1,n]|) est un sous-ensemble strict (et non vide, bien sûr !) de {1,2,3}. Utilise ça pour compter le nombre d'applications non surjectives. Pour obtenir la formule qu'on te demande de montrer, tu dois tomber sur 3 + 3Sn,2 applications non surjectives, donc à un moment il va falloir que tu parles des applications surjectives de |[1,n]| dans {1,2}.

[mehdi-128]

Ouais désolé pour mon exemple j'ai oublié d'écrire que je parlais d'une application de |[1,n]| dans lui-même... Enfin tout ça pour dire qu'il y a des applications non surjectives et non constantes. Quand l'ensemble d'arrivée était {1,2}, ça n'était pas le cas, mais maintenant l'ensemble d'arrivée a strictement plus de 2 éléments.

As-tu vu la notion d'image d'un ensemble ? Si f est une application de E dans F, f(E) est l'ensemble formé par les images des éléments de E. Dire que f est surjective équivaut à dire que f(E) = F (tous les éléments de F peuvent s'écrire comme l'image d'un élément de E).

Du coup, f non surjective ça veut dire que f(E) est strictement inclus dans F. Dans notre cas, f non surjective signifie que f(|[1,n]|) est un sous-ensemble strict (et non vide, bien sûr !) de {1,2,3}. Utilise ça pour compter le nombre d'applications non surjectives. Pour obtenir la formule qu'on te demande de montrer, tu dois tomber sur 3 + 3Sn,2 applications non surjectives, donc à un moment il va falloir que tu parles des applications surjectives de |[1,n]| dans {1,2}.

Si f est une application de E dans F, f(E) est l'ensemble formé par les images des éléments de E. Dire que f est surjective équivaut à dire que f(E) = F (tous les éléments de F peuvent s'écrire comme l'image d'un élément de E).
Oui j'ai vu ça :id:

Je comprends mais j'arrive pas à faire le lien entre le applications surjectives de |[1,n]| dans {1,2,3} et celles de |[1,n]| dans {1,2}.

Et je me mélange les pinceaux, un coup on compte les non-surjectives, un coup on compte les surjectives, je suis perdu.

[Skullkid]

Ouais, le nombre d'applications non surjectives de |[1,n]| dans {1,2,3} est lié au nombre d'applications surjectives de |[1,n]| dans {1,2}. Ça peut sembler bizarre à première vue mais c'est assez logique en fait.

Le point clé c'est qu'une application de E dans F peut toujours être rendue surjective si on restreint son ensemble d'arrivée : si f est une application quelconque de E dans F, l'application x -> f(x) est surjective de E dans f(E) (ce n'est en toute rigueur plus la même application que f, mais elle se comporte exactement pareil, il n'y a que l'ensemble d'arrivée qui change).

Donc, on peut voir les applications non surjectives de |[1,n]| dans {1,2,3} comme des applications surjectives de |[1,n]| dans un sous-ensemble strict (non vide) de {1,2,3}.

[mehdi-128]

Ouais, le nombre d'applications non surjectives de |[1,n]| dans {1,2,3} est lié au nombre d'applications surjectives de |[1,n]| dans {1,2}. Ça peut sembler bizarre à première vue mais c'est assez logique en fait.

Le point clé c'est qu'une application de E dans F peut toujours être rendue surjective si on restreint son ensemble d'arrivée : si f est une application quelconque de E dans F, l'application x -> f(x) est surjective de E dans f(E) (ce n'est en toute rigueur plus la même application que f, mais elle se comporte exactement pareil, il n'y a que l'ensemble d'arrivée qui change).

Donc, on peut voir les applications non surjectives de |[1,n]| dans {1,2,3} comme des applications surjectives de |[1,n]| dans un sous-ensemble strict (non vide) de {1,2,3}.

Ah d'accord.

En ce qui concerne le nombre d'applications non surjectives de |[1,n]| dans {1,2,3} :
J'en compte déjà 3 : les applications constantes.

Pour le reste :marteau:

[Skullkid]

Comme dit, il faut raisonner via l'ensemble image.

Les applications constantes ce sont celles dont l'ensemble image est de cardinal 1. Il y a 3 sous-ensembles de {1,2,3} de cardinal 1 : {1}, {2} et {3}. Pour chacun de ces ensembles, il n'y a qu'une seule application qui l'admette pour ensemble image, ce qui te donne au total 3 applications de |[1,n]| dans {1,2,3} dont l'ensemble image est de cardinal 1.

Cette petite démonstration de dénombrement est évidemment inutilement compliquée quand il s'agit de dénombrer les applications constantes. Mais tu peux t'en inspirer pour dénombrer les autres applications non surjectives de |[1,n]| dans {1,2,3}.

[mehdi-128]

Comme dit, il faut raisonner via l'ensemble image.

Les applications constantes ce sont celles dont l'ensemble image est de cardinal 1. Il y a 3 sous-ensembles de {1,2,3} de cardinal 1 : {1}, {2} et {3}. Pour chacun de ces ensembles, il n'y a qu'une seule application qui l'admette pour ensemble image, ce qui te donne au total 3 applications de |[1,n]| dans {1,2,3} dont l'ensemble image est de cardinal 1.

Cette petite démonstration de dénombrement est évidemment inutilement compliquée quand il s'agit de dénombrer les applications constantes. Mais tu peux t'en inspirer pour dénombrer les autres applications non surjectives de |[1,n]| dans {1,2,3}.

Les applications non surjectives |[1,n]| dans {1,2,3} non constantes sont celles dont l'ensemble image est de cardinal 2 : {1,2}, {1,3} et {2,3}

Mais j'arrive pas à les dénombrer

[Skullkid]

Les applications en question sont surjectives sur leur ensemble image.

[mehdi-128]

Les applications en question sont surjectives sur leur ensemble image.

Oui effectivement.

Je voulais dire que les applications non surjectives de |[1,n]| dans {1,2,3} non constantes sont de la forme :

f(1)=1 ....f(2)=2....f(n)=2
f(1)=1.....f(2)=1....f(n)=3
f(1)=2.....f(2)=2....f(n)=3

Mais je vois pas comment les dénombrer.

[mehdi-128]

Tu pourrais m'expliquer comment on obtient le résultat ? D'où vient le 3Sn,2 ?
Ca fait 2 jours que je suis dessus et j'y arrive toujours pas :marteau:

[Skullkid]

Je t'ai donné tous les éléments là... Tu ne peux pas donner la forme générale des applications non surjectives et non constantes parce qu'il n'y en a pas. Tout ce que tu peux dire c'est que l'ensemble image d'une application non surjective non constante est de cardinal 2.

Autrement dit, une application non surjective non constante de |[1,n]| dans {1,2,3} peut s'interpréter comme une surjection de |[1,n]| dans un ensemble de cardinal 2. Tu n'as qu'à appliquer la méthode de dénombrement que j'ai utilisée pour compter les applications constantes.

[Doraki]

Oui effectivement.

Je voulais dire que les applications non surjectives de |[1,n]| dans {1,2,3} non constantes sont de la forme :

f(1)=1 ....f(2)=2....f(n)=2

est-ce que par pur hasard, tu ne serais pas en train de décrire une application de {1...n} surjective dans {1...2} ?

[mehdi-128]

Je t'ai donné tous les éléments là... Tu ne peux pas donner la forme générale des applications non surjectives et non constantes parce qu'il n'y en a pas. Tout ce que tu peux dire c'est que l'ensemble image d'une application non surjective non constante est de cardinal 2.

Autrement dit, une application non surjective non constante de |[1,n]| dans {1,2,3} peut s'interpréter comme une surjection de |[1,n]| dans un ensemble de cardinal 2. Tu n'as qu'à appliquer la méthode de dénombrement que j'ai utilisée pour compter les applications constantes.

Il y a 3 sous-ensembles de {1,2,3} de cardinal 2 : {1,2}, {2,3} et {3,1}. Pour chacun de ces ensembles, il n'y a Sn,2 applications qui l'admette pour ensemble image, ce qui te donne au total 3Sn,2 applications de |[1,n]| dans {1,2,3} dont l'ensemble image est de cardinal 2.

En comptant les applications constantes, on arrive à 3+3Sn,2 applications non surjectives de |[1,n]| dans {1,2,3}.

Or, il y a 3^n application de de |[1,n]| dans {1,2,3}.

D'où :

Sn,3=3^n-(3+3Sn,2)=3^n-3-3Sn,2

C'est correct ?

[mehdi-128]

est-ce que par pur hasard, tu ne serais pas en train de décrire une application de {1...n} surjective dans {1...2} ?

Oui bien vu !

[Skullkid]

Il y a 3 sous-ensembles de {1,2,3} de cardinal 2 : {1,2}, {2,3} et {3,1}. Pour chacun de ces ensembles, il n'y a Sn,2 applications qui l'admette pour ensemble image, ce qui te donne au total 3Sn,2 applications de |[1,n]| dans {1,2,3} dont l'ensemble image est de cardinal 2.

En comptant les applications constantes, on arrive à 3+3Sn,2 applications non surjectives de |[1,n]| dans {1,2,3}.

Or, il y a 3^n application de de |[1,n]| dans {1,2,3}.

D'où :

Sn,3=3^n-(3+3Sn,2)=3^n-3-3Sn,2

C'est correct ?

C'est correct, on peut même pousser plus loin et exprimer Sn,p en fonction des Sn,k pour k < p, et donc même s'il n'y a pas de formule générale simple pour Sn,p, on sait le calculer de proche en proche.

Tu peux passer à la question 5. Provient-elle du même exercice ? Je ne vois pas trop le lien entre la somme qu'on te demande de calculer et les surjections... ou alors il y a d'autres questions après ?

[mehdi-128]

C'est correct, on peut même pousser plus loin et exprimer Sn,p en fonction des Sn,k pour k < p, et donc même s'il n'y a pas de formule générale simple pour Sn,p, on sait le calculer de proche en proche.

Tu peux passer à la question 5. Provient-elle du même exercice ? Je ne vois pas trop le lien entre la somme qu'on te demande de calculer et les surjections... ou alors il y a d'autres questions après ?

Oui, c'est la dernière question de l'exo. Je vois pas trop le lien avec ce qui précède.

Je vois pas trop d'où partir.