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... Autre AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques
Niveau autre
Partager :

Injections, surjections

Posté par
laure21 21-10-07 à 20:24

Bonjour,

Cet exercice me parait tellement facile, que je pense avoir la réponse mais je ne saurais pas l'expliquer
Enoncé:

" 1)Déterminer le plus petit entier naturel n0 tel que: n²< 2^n pout tout n> ou égal à n0.

  2)Soit E un ensemble à n éléments. Déterminer le nombre d'injections, de surjecions, de bijections de E*E dans P(E). On utilisera le cours pour traiter le cas n=3."


Pour le 1), j'aurais di n0=0 mais je ne saurais pas l'expliquer.

Posté par
laure21re : Injections, surjections 21-10-07 à 20:32

Si quelqu'un pouvait m'aider, ça serait gentil.

Posté par
Tigweg Correcteurre : Injections, surjections 21-10-07 à 20:35

Bonjour laure21,

1)Attention, jusqu'à n=3 ça ne marche pas tout le temps quand même!
Pour n>3, un seul mot d'ordre:récurrence!


Tigweg

Posté par
laure21re : Injections, surjections 21-10-07 à 20:40

Donc tu dis que je dois faire une récurence pour la question 1??
Je comprends pas.
je pars donc de n=4 c'est ça?

Mais pour n=0, 1, 2 et même 3, je fais comment??

Posté par
Tigweg Correcteurre : Injections, surjections 21-10-07 à 20:41

Eh bien ce résultat est faux pour n=3, tu ne peux donc pas le démontrer pour n=3!
Initialise donc ta récurrence à n=4

Posté par
laure21re : Injections, surjections 21-10-07 à 20:47

Ah d'accord, donc je ne m'occupe pas de 0; 1; 2 et 3
c'et ça?

Posté par
Tigweg Correcteurre : Injections, surjections 21-10-07 à 20:49

Voilà!

Posté par
laure21re : Injections, surjections 21-10-07 à 22:49

Ca arrive à rien la récurrence!

Posté par
Dieliennere : Injections, surjections 21-10-07 à 23:09

Bonsoir,

n²< 2^n  <=> ln(n²)< ln(2^n) pour n > 0

<=> 2ln(n)< nln(2)
<=> ln(n)/n < ln(2)/2

On peut ensuite dériver la fonction f(x)=ln(x)/x, ça donne f'(x)=[1-ln(x)]/x²
Donc la fonction est croissante jusqu'à x = e et décroissante ensuite.
Donc si f(n)=ln(n)/n < ln(2)/2=f(2) pour un n supérieur à e (=2.73..) ça marchera pour tous ceux après ! Le n0 est le plus petit entier n supérieur à e tel qu'on ait l'inégalité vraie.

Ca marche pour n=4 > e, donc n0 = 4

Posté par
Dieliennere : Injections, surjections 21-10-07 à 23:13

Flûte, non ça ne marche pas pour n=4, car l'inégalité est stricte ^^'
n=5 par contre marche

Posté par
Tigweg Correcteurre : Injections, surjections 22-10-07 à 15:17

Bonjour Dielienne

laure21>

Citation :
Ca arrive à rien la récurrence!


>Et d'un t'es pas polie, et de deux ce n'est pas parce que tu n'y arrives pas que "ça arrive à rien"



Voici à quoi je pensais (sans sortir de l'arithmétique, ce qui n'enlève rien à la jolie démonstration de Dielienne

Pour tout n\ge 4 on a 2^{n-1}=(1+1)^{n-1}=\bigsum_{k=0}^{n-1}\(n-1\\p\).

Cette somme comporte n termes et chaque coefficient binômial est supérieur ou égal à 1, avec n-2>2 d'où \(n-1\\n-2\)>1.

On en déduit que 2^{n-1}\ge n+1 et en particulier que 2n+1<2n+2\le 2^n.


Pour n=5 on a bien n^2=25<32=2^n.

Supposons à présent qu'à l'entier n\ge 5 on ait n^2< 2^n.

Alors (n+1)^2=n^2+2n+1<2^n+2n+1<2^n+2^n=2^{n+1} ce qui prouve la propriété par récurrence à l'entier n+1


Tigweg

Posté par
laure21re : Injections, surjections 22-10-07 à 19:05

Désolé, je ne voulais pas être mal polie.

Merci beaucoup!

Posté par
Tigweg Correcteurre : Injections, surjections 22-10-07 à 19:17

Pour ma part, je t'en prie

Citation :
Désolé, je ne voulais pas être mal polie.

>Ok, désolé dans ce cas et pas de problème, c'est juste que par internet, on interprète parfois mal certaines choses...

Posté par
laure21re : Injections, surjections 22-10-07 à 19:38

Bonsoir,

Est-ce que vous pourriez juste me dire comment on fait pour déterminer le nombre d'injections, de surjections et de bijections?

Merci d'avance.

Posté par
Tigweg Correcteurre : Injections, surjections 22-10-07 à 20:16

Commence par remarquer que ExE a n² éléments, contre 2n pour P(E).

Il ne peut exister d'injections d'un ensemble fini dans un autre que si l'ensemble de départ possède moins d'éléments que l'ensemble d'arrivée.D'où un lien avec la question 1.
Pour n supérieur ou égal à 4, c'est possible et le choix d'une injection est celui d'un arrangement (partie ordonnée d'éléments deux à deux distincts) de cardinal n² dans un ensemble à 2n éléments.

Pour les surjections, il faut la condition contraire d'avant (l'ensemble de départ doit posséder plus d'éléments que l'ensemble d'arrivée) donc il n'y aura que 4 cas à examiner!

Pour les bijections, il n'y en a que s'il y a des bijections, donc c'est encore plus rapide!

Posté par
Tigweg Correcteurre : Injections, surjections 22-10-07 à 21:08

Pour les bijections, il n'y en a que s'il y a des surjections voulais-je dire!

Posté par
laure21re : Injections, surjections 22-10-07 à 21:27

D'accord pour l'injection
C'est bien un arrangement. Mais est-ce que cet arrangement est simplifiable?

Posté par
veledare : Injections, surjections 23-10-07 à 14:46

bonjour à tous
le nombre d'injections est -il bien(n²)!C2n n²
je n'arrive pas à taper la formule en latex

Posté par
1 Schumi 1re : Injections, surjections 23-10-07 à 15:48

Tu veux écrire \rm\large (n^2)!C^{n^2}_{2n}?

Posté par
Tigweg Correcteurre : Injections, surjections 23-10-07 à 16:49

Bonjour à tous,

oui laure21 et veleda, le nombre d'arrangements à p éléments s'écrit plus simplement \frac{n!}{(n-p)!}.
Dans notre cas, il s'agit donc de \frac{2^n!}{(2^n-n^2)!}.



Tigweg

Posté par
veledare : Injections, surjections 23-10-07 à 16:55

oui mais entre parenthèses le plus grand haut comme il faut en principe ecrire maintenant
les indices sont 2n et n² j'ai essayé{2n}\choose{n²} et quelques variantes mais ça ne marche pas -je ne suis pas douée

Posté par
veledare : Injections, surjections 23-10-07 à 16:58

>>Tigweg je voulais juste réussir à taper une formule un peu compliquée pour m'entrainer mais c'est raté

Posté par
Tigweg Correcteurre : Injections, surjections 23-10-07 à 17:39

Citation :
le nombre d'injections est -il bien(n²)!C2n n²?


>Ok, ta question m'a laissé penser que tu n'en étais plus sûre


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 1675 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 !