maths BCPST : démonbrement

Posté par Belgarath Belgarath

Salut à tous! Je calle complètement sur un DM de maths... j'ai bien cherché, je ne comprends même pas la première question qui me bloque tout le reste! :

Dans tout le problème, n est un entier naturel strictement positif.
On note E_n=[|1;n|] et E_p=[|1;p|] (les [| et |] signifie intervalle des entiers)
On note S_n,p le nombre d'applications surjectives de E_n sur E_p.


1/a/     Calculer S_n,p pour p strictement supérieur à n
         Calculer S_n,n ; S_n,1 ; S_n,2

b/ Calculer S_p+1,p (on pourra considérer l'élément de E_p ayant 2 antécédents après avoir justifié son existence).

Bon, je vais m'arrêter là, et j'essayerai de faire la suite avec vos réponses pour le début... si je gallère trop encore, je reviendrais poser une chtite question...
Merci à tous!

Posté par jmg1 (invité)

Les surjections correspondent aux applications pour lesquelles une image n'a au plus qu'un antécédént.
Ton ensemble de départ a n éléments et celui d'arrivée p.
Pour le premier élément de D (ensemble de départ), tu peux choisir parmi p éléments. En revanche pour le second tu ne peux plus choisir que dans p-1 (le dernier étant celui qui est déjà image du premier et ainsi de suite.
Le nombre de surjection est donc:
Sn,p=p X (p-1) X (p-2) X ... X (p-n+1)

en notant n! (factorielle n) = n X (n-1) X  ... X (1)
on a:

Sn,p= p!/(n-p)!

Sn,n= n! = nombre de bijections de D dans A
S1,n = n (on choisit quel élément de départ aura le singleton comme image à l'arrivée parmi n)
S2,n= n X (n-1)


b) Sp,p+1=p
Voila!
Bon courage.
JMG

Posté par biondo (invité)

Salut,

?????

Les surjections correspondent plutôt aux applications qui donnent au moins un antécédent à tout élément de l'ensemble d'arrivée.

Donc Sn,p = 0 si p>n...

A+
biondo

Posté par jmg1 (invité)

He bien oui je me suis trompé...
Bon ceci dit corrigeant l'énormité on doit pouvoir refaire le raisonnement:
Les surjections correspondent aux applications pour lesquelles chaque élément de l'ensemble d'arrivée a au moins un antécédent.
Ton ensemble de départ a n éléments et celui d'arrivée p (p < n contrairement à ce qui m'a induit en erreur..)
Pour le premier élément de A (ensemble d'arrivée), tu peux choisir parmi n éléments. En revanche pour le second tu ne peux plus choisir que dans n-1 (le dernier étant celui qui est déjà image du premier et ainsi de suite.
Le nombre de surjection est donc:
Sn,p=n X (n-1) X (n-2) X ... X (n-p+1)

en notant n! (factorielle n) = n X (n-1) X  ... X (1)
on a:

Sn,p= n!/(n-p)!

Sn,n= n! = nombre de bijections de D dans A
Sn,1 = n (on choisit quel élément de départ aura le singleton comme image à l'arrivée parmi n)
Sn,2= n X (n-1)


b) Sp,p+1=p
Voila!
Bon courage.

Posté par biondo (invité)

????? (bis)

Sn,1 = 1 chez moi...

Les applications qui ont pour image le singleton {1}, j'en vois qu'une:
f: n élément de [1,..,n] -----> 1

biondo

Posté par Belgarath Belgarath

Euh... donc pour Sn,1 et Sn,2 c'est égal à quoi?

Posté par biondo (invité)

En bref:

Sn,p = 0 pour p>n
Sn,n = n!
Sn,1 = 1
Sn,2 = 2^n - 2 (si n>1. 0 si n=1)


La plus dure, c'est la derniere.
Deux manieres de faire: par recurrence, ou directement.

Directement:
Le nombre de surjections, c'est le nombre d'applications moins le nombre d'applications qui ne sont pas des surjections. Le nombre d'applications, ca fait 2^n (facile). Et les applis qui ne sont aps des surjections, ce sont celles dont l'image n'est pas l'intervalle compl,et. Autrment dit, les applis qui ont comme image l'un des deux singletons: {1} ou {2}. Ca en fait deux.

A+
biondo