Dénombrement de sommes d'entiers (Celui qui réussit cet exo est un génie)

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Florix



Alors là je vous pose le défi de comprendre et résoudre cette énoncé de maths ! Jamais rien vu d'aussi incompréhensible lol

Si qqn pouvait m'aider et me donner des explications !

Pour n,r entiers naturels non nuls données, nous considérons l'équation à r inconnues :

x1 + x2 + ....... + xr = n


On s'interesse aux solutions dont toutes les composantes sont des entiers naturels. Le but de cet exercice est d'établir les deux formules de dénombrement suivantes (cliquer ici pour voir ces formules)

Voici une traduction plus concrète du problème.

On dispose de n jetons identiques (il n'est donc pas possible de les distinguer) et de r boîtes numérotées de 1 a r. Le cas a donne le nombre de façons de répartir ces jetons dans les r boites (certaines pouvant rester vides). Le cas b donne le nombre de repartitions pour lesquelles aucune boîte ne reste vide. Dans cette interprétation, xi représente le nombre de jetons déposés dans la boîte n°i .

Pour démontrer les deux formules, nous nous aidons au codage suivant illustré par cet exemple suivant avec n = 9 et r = 4. On represente d'abord chaque jeton par le caractère "0" , avec un espace entre deux caractères consécutifs : 0 0 0 0 0 0 0 0 0 . Pour représenter les quatres boîtes, il suffit d'insérer 3 caractères ' | ' chacun dans un espace libre. Par exemple, la chaîne 0 0 | 0 0 0 | 0 | 0 0 0 code la répartition avec 2 jetons dans la première boite, 3 dans la deuxième, 1 dans la troisième et 3 dans la quatrième, autrement dit la solution (x1, x2, x3, x4) = (2;3;1;3)

Démontrer la formulation de a et de b

Quelqu'un y comprend quelquechose ou c'est juste moi qui suis débile lol ??

C'est strictement incompréhensible ! Si qnn pouvait m'aider

Merci d'avance pour vos réponses

Florix


Posted by: ParLaLaSortie

C'est hyper-standard comme exo.

La méthode la plus simple consiste à utiliser des séries formelles.

Tu trouveras la solution complète dans ce livre:

http://www.math.upenn.edu/~wilf/gfology2.pdf

page 16 et suivantes.

ParLaLaSortie


Posted by: ParLaLaSortie

Non pardon, c'est plutôt pages 96 et suivantes dudit livre.

ParLaLaSortie


Posted by: Florix

Oula, merci beaucoup mais les bouquins de maths en anglais à vrai dire je peux pas trop comprendre !

En plus il parle d'une certaine somme S je vois pas le raport !

Si qqn pouvait m'aider (en français si possible lol !)

Merci


Posted by: abcd22

Il y a beaucoup plus simple que des séries formelles !
Tu comprends l'équivalence avec les n jetons dans r boîtes ?
Pour le b (c'est plus simple que le a), on veut mettre au moins un jeton dans chaque boîte, donc :
- on a n-1 possibilités pour mettre les « | » (on ne peut pas avoir |0 0 ... ou 0 0|, le premier cas signifie que la 1e boîte est vide, ds le 2e la dernière boîte est vide).
- les r-1 | doivent être à des emplacements différents : si on a ...0||0..., il y a une boîte vide.
Donc répartir n jetons dans r boîtes avec aucune boîte vide, ça revient à choisir les r-1 emplacements (différents) où on met les | parmi n-1 possibilités : il y a {n-1}\choose {r-1} cas possibles.


Posted by: yos

n jetons : oooooooooooo...ooo
r tiroirs.
Une répartition des n jetons dans les r boites s'obtient en plaçant (r-1) séparations dans la liste des n jetons.

Dans le cas b (qui me parait le plus facile), aucune boite ne doit être vide. Tes séparations ne peuvent se toucher (au moins un jeton entre deux séparations). Il y a donc (n-1) espaces pour placer les (r-1) séparations. D'où la formule.
Le cas b m'a toujours paru très subtil (c'est un exercice très classique). Ici, les séparations peuvent se toucher et même figurer en début de liste (cas où la première boite est vide). Du coup on considère les n jetons et les (r-1) séparations comme un ensemble de (n+r-1) symbôles à arranger de toutes les façons possibles dans (n+r-1) cases alignées. Le nombre de ces façons est le nombre de façons de choisir (r-1) de ces cases pour les affecter à une séparation.


Posted by: Florix

Et après y'a une suite à l'exo ! Je vois pas le rapport avec la premiere question :

2. Soit n et p deux entiers tels que n >= p

n obules discernables ont été placées au hasard dans p tiroirs Ti
Xi désigne la Variable aléatoire égale au nombre de boules placées dans le tiroir n°i

Déterminer pour tout i [ 1 ; p ] i E N , la loi de Xi


Posted by: Florix




Posted by: Nicolas_75

Pour la première partie, voir aussi ce fil :
http://maths-forum.com/showthread.p...65&page=1&pp=10

Nicolas


Posted by: ParLaLaSortie

C'est curieux, ne peut-on pas dire que:
\displaystyle \sum_{i=1}^p X_i = n
d'où
\displaystyle \sum_{i=1}^p \mbox{E}X_i = n
donc, les X_i ayant même moyenne, il vient:
\displaystyle \mbox{E} N = \frac{n}{p}.

Ce qui est assez évident: en moyenne chaque tiroir a \displaystyle \frac{n}{p} boules.

Mais en fait je relis la question et visiblement, le E écrit ici ne correspond pas à l'espérance mais à l'appartenance. Ce qui est demandé c'est donc la loi de chaque X_i et non pas la moyenne. Et là c'est plus dur...

J'aurais tendance à dire:
\displaystyle\mbox{P}\[X_i = k\] = \mbox{P}\[\sum_{j \neq i}X_j = n-k\] et la seconde proba se relie immédiatement au début du problème, puisque tu as calculé tous les cas favorables.


Posted by: Alpha

Bonjour, je vous renvoie à ce très intéressant problème, qui a l'air différent, mais qui est en fait exactement le même : http://www.maths-forum.com/showthre...ghlight=lanc%E9

J'y donne une solution qui a l'avantage d'être très intuitive et de se comprendre facilement.

Cordialement, Alpha


Posted by: Florix

Bonjour,

Je n'ai pas compris la question 2. QQn pourrait il m'expliquer ?

Citation:
Posté par ParLaLaSortie
Ce qui est demandé c'est donc la loi de chaque X_i et non pas la moyenne. Et là c'est plus dur...

J'aurais tendance à dire:
\displaystyle\mbox{P}\[X_i = k\] = \mbox{P}\[\sum_{j \neq i}X_j = n-k\] et la seconde proba se relie immédiatement au début du problème, puisque tu as calculé tous les cas favorables.



Posted by: yos

Bonsoir.
Il est clair que les Xi ont tous la même loi .
Je suppose qu'il peut y avoir des tiroirs vides (pas précisé, mais le fait que n>=p peut laisser croire le contraire?).
Xi prend les valeurs 0,1,2,...n.
(Xi=k) signifie qu'on a réparti (n-k) boules dans (p-1) tiroirs. La formule déjà vue s'applique ici.










-