Applications et combinatoire

par **legeniedesalpages** » 14 Sep 2007, 13:36

Bonjour, je ne vois pas comment démarrer cet exercice:

Soient

et

des ensembles finis totalement ordonnés ayant respectivement

et

éléments.

Le nombre d'applications strictement croissante de

dans

est

.

Merci pour vos indications.

par **alben** » 14 Sep 2007, 14:11

Bonjour,
Il faut que tu montres qu'un application strictement croissante est injective.
Ensuite que p est inférieur ou égal à n
Puis qu'il existe une bijection entre les parties de F à p éléments et les applications strictement croissantes de E->F

par **fahr451** » 14 Sep 2007, 14:41

bonjour

en complément (plus dur)

compter les applications croissantes (sens large)

par **legeniedesalpages** » 14 Sep 2007, 14:52

ok merci pour vos indications, je vais creuser le sillon :)

par **alben** » 14 Sep 2007, 17:16

fahr451 a écrit:bonjour
en complément (plus dur)
compter les applications croissantes (sens large)

Avec un awalé à n+p-1 cases, c'est pas trop dur :zen:

par **fahr451** » 14 Sep 2007, 17:34

moi je trouve que c'est subtil

bien sûr avec le temps on finit par oublier qu'on a trouvé ça subtil la première fois

par **alben** » 14 Sep 2007, 18:06

D'accord, Farh. Pour moi, la première fois c'était une demie journée de caculs avec des récurrences tordues pour arriver au final à un résultat exagérément simple

par **fahr451** » 14 Sep 2007, 18:14

oui récurrence sur n+p ...

vieillir c 'est perdre sa faculté d'émerveillement

waou c'est profond ça je vais le déplacer dand l'onglet philo

par **legeniedesalpages** » 15 Sep 2007, 12:53

Bonjour, pour le cas où

, je pensais utiliser le principe des tiroirs pour dire qu'il n'y a aucune injection de

dans

, et donc aucune application strictement croissante de

dans

.

Le principe des tiroirs se démontre-t-il? Sur quoi repose ce résultat?

par **aviateurpilot** » 15 Sep 2007, 15:49

une demo sans reccurence.

soit
l'ensemble des parties à elements de
tel que
l'ensemble des applications stric croissantes de

si

on a

et Le nombre d'applications strictement croissante de

dans

c'est

.

si

.
soit l'application

tel que pour

(

)

tel que pour

(donc

surjective)
est il est eveient que pour

on a

car

(donc

est surjective)
H bijective donne

par **fahr451** » 15 Sep 2007, 15:53

d'accord aviateur pilot

mais une simple remarque:
le dénombrement pose avant tout un problème de compréhension

une fois qu'on a compris formaliser ( ce que tu fais très bien ) est un autre problème qui est un peu annexe

donc moi j'aurais dit en français (mais c'est exactement ce que tu formalises

se donner une application strictement croissante c'est exactement se donner une partie à p éléments car une fois qu'on s'est donné cette partie il ya une e t une seule façon de choisir le s images dans cette partie pour

que l'application soit croissante strictement (l 'image du plus petit sera le plus petit élément de la partie etc)

par **legeniedesalpages** » 15 Sep 2007, 18:28

Oui, j'ai procédé de même en montrant qu'il a une bijection entre l'ensemble des parties de E à p éléments, et l'ensemble des applications injectives de E dans F.

Je voulais savoir justement, aviateurpilote utilise

avec

, est-ce que ce coefficient binomial est défini quand

, si oui pourquoi vaut-il 0?

par **aviateurpilot** » 16 Sep 2007, 01:23

legeniedesalpages a écrit:aviateurpilote utilise avec , est-ce que ce coefficient binomial est défini quand , si oui pourquoi vaut-il 0?

si

alors

par **fahr451** » 16 Sep 2007, 08:19

legeniedesalpages a écrit:Oui, j'ai procédé de même en montrant qu'il a une bijection entre l'ensemble des parties de E à p éléments, et l'ensemble des applications injectives de E dans F.

ceci est faux

pour construire une injection il ne suffit pas de se donner l'ensemble des images ( C( n ,p) façons ) il faut aussi les permuter (p ! façons)

donc A (n , p ) = C(n,p ) p ! injections

par **aviateurpilot** » 16 Sep 2007, 10:56

oui fahr451 il existent

injections.
mtn soit

l'ensemble des injections

et

l'ensemble des bijections de

.
et soit l'application

tel que
pour

( l'application

de mon 1er poste)
et on montre facilement que

d'ou

par **fahr451** » 16 Sep 2007, 11:11

ça s 'appelle le principe des bergers

pour compter les moutons rien de tel que de compter les pattes et de diviser par 4

à condition qu'aucune brebis ne soit galeuse

par **legeniedesalpages** » 16 Sep 2007, 12:52

fahr451 a écrit:ceci est faux

pour construire une injection il ne suffit pas de se donner l'ensemble des images ( C( n ,p) façons ) il faut aussi les permuter (p ! façons)

donc A (n , p ) = C(n,p ) p ! injections

Oui pardon, ma langue a fourchée, je voulais dire que j'ai montré qu'il y a bijection entre l'ensemble des parties de E à p éléments, et l'ensemble des applications strictement croissantes de E dans F.

par **legeniedesalpages** » 16 Sep 2007, 12:55

fahr451 a écrit:ça s 'appelle le principe des bergers

pour compter les moutons rien de tel que de compter les pattes et de diviser par 4

à condition qu'aucune brebis ne soit galeuse

Mais le principe des bergers se démontre? ça marche comment les principes en maths?

Applications et combinatoire

applications et combinatoire

Qui est en ligne