Forum : algèbre :
Nombre d'applications croissantes de [1,k] dans [1,p]

Bonjour. Je révise toujours ce lointain (pour moi) programme de math sup.

Dans un exercice précédent, on nous demandait de dénombrer les applications strictement croissantes de [1,k] dans [1,p] (intervalles entiers).

J'avais trouvé 0 si k>p car une application strictement croissante doit être injective, et C_p^k sinon, car il suffit de choisir k éléments (sans ordre) dans [1,p] puis de les "affecter" dans l'ordre croissant aux éléments de [1,k]

Mais un autre exercice me demande de dénombrer, cette fois, les applications croissantes de [1,k] dans [1,p]. Je ne vois pas comment envisager le problème...

Si p = 1, il y en a une : l'application qui à tout élément de [1,k] associe 1.

Si p = 2, il y en a autant que de façon de "couper" les k éléments de [1,k] en 2 parties dont l'une est éventuellement vide... Il y a donc k+1 choix (de lieux de coupure d'une k-liste)

En effet, si on "coupe" après l'entier m  de [0,k] : à tout entier de [1,m] on associe 1 et à tout entier de [m+1,k] on associe 2.

Pour p quelconque, il s'agit de partager [1,k] en p parties (éventuellement vides) sachant qu'on a k+1 "places" pour les "coupures" et que plusieurs "coupures" peuvent cohabiter à la même "place". Cela fait-il (k+1)^p possibilités ? Ou plutôt (k+1)^p/(k+1)! puis qu'il ne faut pas tenir compte de l'ordre ? Je ne sais pas.

Il y avait un autre exercice où il fallait trouver le nombre de p-uplets d'entiers de somme n. On modélisait par "comment noircir p-1 cases parmi n+p-1" et, si je ne me trompe pas, la réponse était C_n+p-1^p-1. On pourrait peut-être trouver quelque chose de semblable dans le problème présent : ?

Peut-être avez-vous une autre "modélisation" à me proposer ?

Merci d'avance de votre aide et de corriger mes fautes de logique.

Bonjour charmuzelle

Pour les applications croissantes au sens large de [1;k] dans [1;p], tu as eu la bonne idée d'introduire des coupures, mais tu n'es pas allée au bout de ton idée.

Je te propose la chose suivante:

tant que les entiers de [1;k] ont pour image 1, on écrit des 1 qui se suivent;

dès que les images passent à 2, on trace une barre verticale matérialisant la fin des 1, puis on écrit des 2 qui se suivent.

Si aucune image ne vaut 2 mais qu'on passe directement à 3, on trace deux barres verticales(une pour la fin des 1, l'autre pour la fin des 2) à la suite de la liste des 1.

On continue ainsi, puis on omet la barre verticale matérialisant la fin des p puisque cette barre est toujours à la même place.

Si aucun entier n'a pour image 1, on commence par une barre matérialisant la fin des 1.

Comptons à présent les symboles utilisés (chiffres et barres réunis):

il y a autant de chiffres écrits que d'entiers dans [1;k], soit k; il y a p-1 barres (une pour matérialiser la fin de chaque liste de chiffres compris entre 1 et p-1, même si certaines de ces listes sont vides).

En tout, on a donc écrit k+p-1 symboles, dont exactement p-1 barres.

A présent, remarque que la position des p-1 barres déterminent à elles seules les listes à écrire, et donc l'application croissante choisie!

Ainsi, si on va de [1;4] dans [1;6], il y aura 9 symboles à répartir dans 9 "cases" à occuper, dont 5 barres.

Supposons par exemple qu'on sache que les 5 barres sont en 2è, 5è, 6è, 7è et 8è positions, cela signifiera que la liste "complète" est :

1 | 2 2 | | | | 6  

ou encore que l'application f choisie est définie par f(1) = 1, f(2) = f(3) = 2, f(4) = 6.


Il y a donc autant de telles applications que de façons de placer p-1 barres dans une liste de k+p-1 cases alignées, ou encore que de choisir une partie de cardinal p-1 dans un ensemble de cardinal k+p-1:

le résultat cherché vaut donc    .

On appelle cela des combinaisons à répétition.

J'essaierais de commencer comme ça, mais je n'ai pas réfléchi jusqu'au bout:


Je vais compter le nombres d'applications croissantes  f  telles que  f(1)=1, puis celles telles que  f(1)=2, etc...

Si j'ai une application  f  telle que  f(1)=1, pour la "compléter" en une application croissante, je vais choisir de "monter" ou de "rester sur place" pour f(2), puis pour f(3)....

... mais ça n'a pas l'air très convivial pour la suite... peut-être pas une bonne idée..

Salut Tigweg. Je lis ta solution..

Salut Stokastik.

citation :
En tout, on a donc écrit k+p-1 symboles, dont exactement p-1 barres.

Une application constante n'a pas de barre non ? J'ai pas compris quelque chose ?

C'est pas un maximum de  p-1  barres à répartir ?

Pour ton autre exercice, si on considère une partition (x1;...;xp) de n (c'est-à-dire que la somme des xi fait n), on peut lui associer de manière bijective le p-uplet (x1;x1+x2;...;x1+x2+...+xp).

Les composantes de ce p-uplet est une suite croissante finie (puisque les xi sont positifs), x1 vaut au minimum 0 et la dernière composante vaut toujours n, en revanche lavant-dernière composante vaut au plus n.

Il y a donc autant de p-partitions de n que de suites d'entiers croissantes (au sens large) de [1;p-1] dans [0;n].

Comme l'ensemble d'arrivée contient n+1 éléments, on applique le résultat précédent et on obtient      p-partitions de l'entier n, sauf erreur.

Stokastik:

citation :
C'est pas un maximum de  p-1  barres à répartir ?

-> Non, on met une barre à la fin de chaque liste (éventuellement vide) d'éléments de l'ensemble d'arrivée, à l'exception de la liste des p.

Regarde l'exemple que j'ai écrit ensuite.

citation :
Une application constante n'a pas de barre non ?

->Mais si, par exemple l'application constante à 3 de [1;4] dans lui-même se représentera par le schéma:


  | | 3 3 3 3 |   (fin des 1 et des 2 avant qu'ils n'aient commencé, que des 3 pour les images des entiers 1, 2, 3 et 4, fin des 3 et c'est tout vu qu'on ne dessine pas la fin des 4).

Bonjour Tigweg et Stokastik

Comme c'est gentil de vous lancer sur les problèmes avec tant d'enthousiasme ! Je ne pensais pas avoir de réponses si rapides !

Ce que tu proposes, Stolastik, c'est ce que j'ai fait au tout début de ma recherche.

Si je comprends bien la solution de Tigweg, cet exercice est exactement identique à celui qui demandait de déterminer le nombre de k-uplets d'entiers naturels de somme p !

Ce qui m'ennuie avec ces exercices de dénombrement, c'est que j'ai l'impression d'avancer un peu dans le vague, que je ne peux pas être aussi rigoureuse que dans un exercice d'algèbre classique...

Merci en tout cas ! Je m'apprête à bosser tout l'été, nous correspondrons encore sûrement. Très bonne soirée à vous.

Pour le premier exo, si je dis que :

1 * 2 * * 3 4 5 * 6

représente l'application de [1,4] dans [1,6] définie par f(1)=1, f(2)=f(3)=2, f(4)=5.

Il s'agirait donc de répartir  4  étoiles parmi  10  symboles.. non ?

citation :
Mais si, par exemple l'application constante à 3 de [1;4] dans lui-même se représentera par le schéma:...

Ah ok. Je relis ça plus tard!

charmuzelle,

remarque que l'indication consistant à noircir p-1 cases sur un ensemble de n+p-1 cases est cohérente puisque, d'après les propriétés de base des coefficients binômiaux, on peut écrire:


.  

stokastik > l'application de [1,4] dans [1,6] définie par f(1)=1, f(2)=f(3)=2, f(4)=5

se représentera plutôt par la liste

1 | 2 2 | | | 5 |


qui comporte bien 9 symboles.

Tu as mal compris le procédé que j'ai décrit (peut-être mes explications sont-elles trop peu explicites?)

Voici un autre exemple (pour Stockastik ) :

On prend k = 8 et p = 11 (11 pas 10 : il y a une erreur sur le schéma)

On représente ainsi l'application croissante du schéma (je ne sais pas faire les barres verticales alors je mets des / ):

1 1 / / / 4 4 / / / 7 / 8 / / 10 10 /

On a bien 10 barres ( p-1 )
et 10 + 8 symboles c'est à dire k + p - 1

Je t'en prie charmuzelle, avec plaisir!

Je n'avais pas vu ton message intermédiaire.

En tout cas tu sembles avoir bien compris le truc, si j'en juge d'après ton dernier exemple!

_{Sans indiscrétion, comment se fait-il que tu reprennes le programme de Maths Sup s'il est si lointain que ça?Tu reprends tes études? Si je suis trop indiscret, je ne me vexerai pas que tu ne répondes pas!}

Je viens de faire un tour sur ton site personnel, chère collègue!

Désolé, je pensais m'adresser à une étudiante!

Tu passes sans doute l'Agreg dans ce cas

_{Ton petit bêtisier me rappelle pas mal de choses! En tout cas, très amusant le coup de l'angle plat qui est tout plat et qui ne fait pas beaucoup de degrés!!}

Non, tu n'es pas du tout indiscret.

J'ai eu le CAPES en 1997 et j'ai enseigné 8 ans en collège, dont la ZEP : un vrai lavage de cerveau.

Depuis la rentrée 2006, je suis en lycée. J'ai déjà dû me mettre à niveau et j'ai eu envie de continuer, surtout devant les questions de certains élèves. Alors je me suis inscrite à la formation de préparation de l'agreg interne. Mais l'année dernière je n'arrivais à rien faire : j'ai constaté qu'il me manquait presque toutes les connaissances niveau math sup pour arriver à suivre la formation. Comme c'est l'été, je m'y remets, en espérant avoir faire des progrès à la rentrée, parce que pendant l'année scolaire, les élèves et les copies me prennent tout mon temps et mon énergie. Les professeurs de la formation sont très sympas, les stagiaires aussi, et j'ai des amis agrégés qui m'ont passé leurs cours de prépa... Donc je persévère. Peut-être pourrai-je être au niveau dans 5 ou 6 ans

Je vais aller voir sur ta fiche à quel niveau tu enseignes.

Merci encore et très bonne soirée.

Oui, c'est vrai que durant l'année scolaire, il n'y a que très peu de temps pour se consacrer à d'autres activités...

citation :
Peut-être pourrai-je être au niveau dans 5 ou 6 ans

Courage, je suis persuadé qu'en travaillant un peu régulièrement tout de même, tu n'auras pas besoin d'autant de temps!

citation :
Je vais aller voir sur ta fiche à quel niveau tu enseignes.

->Dans le Secondaire moi aussi, en Alsace.

citation :
stokastik > l'application de [1,4] dans [1,6] définie par f(1)=1, f(2)=f(3)=2, f(4)=5 se représentera plutôt par la liste 1 | 2 2 | | | 5 | qui comporte bien 9 symboles. Tu as mal compris le procédé que j'ai décrit (peut-être mes explications sont-elles trop peu explicites?)

Non non, je n'ai pas relu. Mais là je proposais une autre solution qui donne un résultat différent de la tienne, mais il y a sans doute une erreur dans ce que j'ai fait, j'ai pas encore relu ta solution.

J'apprécie la musique d'accueil de ton site charmuzelle, cela détend. Comment tu t'en sortais dans tes études ? Si tu t'en sortais convenablement tu devrais y arriver pour l'agreg interne.

citation :
les élèves et les copies me prennent tout mon temps et mon énergie

C'est clair penser aussi à trouver des astuces pour faire des interros à "correction rapide"

citation :
Pour le premier exo, si je dis que : 1 * 2 * * 3 4 5 * 6 représente l'application de [1,4] dans [1,6] définie par f(1)=1, f(2)=f(3)=2, f(4)=5. Il s'agirait donc de répartir  4  étoiles parmi  10  symboles.. non ?

->OK, je comprends ce que tu veux dire.

Mais en fait le 1 est forcément en 1è place, donc il s'agit de répartir 4 étoiles dans 9 cases.

Tu trouves ainsi      possibilités, contre        pour moi, donc c'est bien la même chose.Ta représentation est en fait l'exacte duale de la mienne.

Ok j'ai pigé