Bonsoir à tous
Voilà, je cherche à déterminer le cardinal de l'ensemble suivant, sans succès :où n est un naturel non nul fixé et p un naturel strictement plus petit que lui.
Le plus naturel est pour moi de raisonner par récurrence simple sur p: j'ai émis une conjecture, qui est celle selon laquelle
L'idée étant, en passant à M(p+1,n), de faire une partition
Quelqu'un pourrait m'aider ?
Tu te trompes sur la conjecture . Notons
Essaie
On a
Ah bon ?
Mais ... :/ Oups
Oui, en effet, je me suis bien trompé ^^ Mais je ne vois pas trop où pour l'instant. Bon, je ne me fais pas de soucis, je le verrai surement demain !
En tout cas, la suite je crois que je sais faire
Merci beaucoup !
Bonne soirée !
Bonjour,
Une récurrence n'est pas nécessaire :
Considérez (p-1) séparateurs (par exemple le caractère |), disposés en ligne, ces séparateurs déterminent p cases (y compris la case de gauche et celle de droite), il reste à déposer dans ces cases, n objets (par exemple le caractère °), par exemple :
Pour faire 7 en 5 entiers : °°||°°°|°|° = (2, 0, 3, 1, 1), hors ici il est facile de voir que le nombre de dispositions revient à choisir les n places des ° parmi les (n + p - 1) emplacements valides (et de mettre les | dans les emplacements restants, mais cela ne peut se faire que d'une seule façon), ou dans l'autre sens : | d'abord et ° ensuite.
Dernière modification par Médiat ; 20/12/2011 à 05h56.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Bonjour Médiat, et merci de votre intervention: en dénombrement, un raisonnement est largement préférable à une récurrence qui donne le résultat "sans réflexion".
Hm ... Je n'ai pas très bien saisi: les séparateurs / jouent le rôle des p cases, c'est à dire en quelque sorte de la position dans la p-liste des y cherchés ? Les ° correspondent alors à la valeur des y, n'est ce pas ?
C'est une vision à laquelle je n'aurais vraiment pas pensé, comment parvenir à réfléchir de cette manière ? ...
C'est un peu comme chercher le nombre de chemins possibles pour aller du point en bas à gauche au point d'en haut à droite (diagonale) d'un rectangle de longueur n , de largeur p , en ne pouvant que monter d'une case ou tourner à droite ^^
S'il est vertical, alors les p colonnes correspondent aux cases (emplacement des éléments) et les n lignes aux possibilités d'atteindre n au bout du chemin choisi, la contrainte "ne pas pouvoir reculer ou tourner à gauche" permettant bien d'atteindre n en arrivant à la dernière caseNon ?
Bonjour,
Oui, les p-1 séparateurs déterminent p cases qui correspondent aux p éléments de la listeEnvoyé par Snowey
Chaque ° correspond à 1, donc si dans une case vous avez n fois °, cela correspond à la valeur n (à la position qui correspond à la case).
En étant très fort.
En fait cet exercice est un grand classique, qui met en lumière que penser à n objets pour démontrer un propriété du nombre n est en fait assez naturelle.
De largeur p - 1 plutôtC'est un peu comme chercher le nombre de chemins possibles pour aller du point en bas à gauche au point d'en haut à droite (diagonale) d'un rectangle de longueur n , de largeur p , en ne pouvant que monter d'une case ou tourner à droite ^^
S'il est vertical, alors les p colonnes correspondent aux cases (emplacement des éléments) et les n lignes aux possibilités d'atteindre n au bout du chemin choisi, la contrainte "ne pas pouvoir reculer ou tourner à gauche" permettant bien d'atteindre n en arrivant à la dernière case
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
De largeur p si on considère que l'on démarre sur cette case, non ?
En fait (je suis nul, je sais), je ne comprends plus pourquoi on choisit les n positions des ° parmi n+p-1 , et non pas juste p (nbe de "cases") :/ Pourriez vous juste me réexpliquer ce passage (vital et surement très simple pourtant) ?
De même, je cherche à montrer par dénombrement que.
Par déduction (entre dénombrement et récurrence), celà revient entre autre à dire que
Je sais que ces notions sont importantes, et qu'elles ne devraient pas me poser de problème ...
J'espère que vous aurez le temps et la patience de m'expliquer,
Snowey
PS: pour le rectangle, en fait il faut qu'il soit de longueur n+1 puisque si la "hauteur" de la case correspond à sa valeur, le niveau de départ (en bas) doit correspondre à 0 et non pas à 1.
Vraiment personne pour m'expliquer ?
Je comprends avec ma configuration du rectangle, mais pas avec les idées de coupure ... :/
Ce qui est amusant, par ailleurs, c'est que ce nombre correspond à celui des applications croissantes de (1,n) dans (1,p) ... Une coïncidence ? (j'y crois pas, moi ^^)
Vraiment personne ?
J'essaye de te faire une autre formulation qui est équivalente
Tu as une bijection entre l'ensemble dont tu veux calculer le cardinal et les tableaux lignes à n+p-1 colonnes composé de 0 et 1 avec p-1 "0" : Par exemple pour n=3 et p = 2
(0,3) -> [0,1,1,1]
(1,2) -> [1,0,1,1]
(2,1) -> [1,1,0,1]
(3,0) -> [1,1,1,0]
Ainsi, il suffit de compter le nombre de tableaux lignes à n+p-1 colonnes composé de 0 et 1 avec p-1 "0". Or il suffit de choisir la position des "0", donc le résultat en découle.
Ah, c'est rigolo comme façon de voir la chose ! Je comprends
MERCI bcp !
Et pour la formule itérée de Pascal, une idée pour la démontrer avec le dénombrement ? (parce que par récurrence, je sais faire)
On a n+p-1 cases, dans lesquels on place n symboles ° et p-1 symboles |. Mais il suffit de placer l'un des deux symboles, puisque l'autre se placera dans les cases restantes. Si l'on place d'abord les °, cela revient donc bien à choisir n cases parmi les n+p-1.
Ce qui est amusant, c'est que si l'on supprime l'ordre dans le cardinal recherché, on se ramène à chercher le nombre de partitions de l'entier n, dont l'expression exacte est bien moins simple : http://fr.wikipedia.org/wiki/Partition_d'un_entier#S.C3.A9r ie_de_Rademacher
If your method does not solve the problem, change the problem.
Très intéressant, cette notion de partition d'un entier !
Je suis certain que ces résultats sont très largement hors de ma portée pour l'instant (ben oui, je compte pas rester nul en maths toute ma vie quand même ^^), mais c'est vraiment intéressant. Comme quoi en ouvrant les yeux on voit beaucoup plus de choses que de simples exercices de dénombrements !
D'ailleurs un résultat récent (début 2011) à été obtenu dans ce domaine. Il existe maintenant un algorithme efficace pour calculer le nombre de partitions d'un entier (la série de Rademacher n'étant pas très sympathique).
Un article sur le sujet ici :
http://blogs.plos.org/badphysics/2011/01/20/ono/
