Dénombrement de sommes d'entiers (Celui qui réussit cet exo

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Florix
Membre Relatif
Messages: 278
Enregistré le: 12 Nov 2005, 19:46

Dénombrement de sommes d'entiers (Celui qui réussit cet exo

par Florix » 26 Jan 2006, 19:37

:briques:

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 :hum:

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 :

[CENTER]x1 + x2 + ....... + xr = n[/CENTER]

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

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

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

Merci d'avance pour vos réponses

Florix



ParLaLaSortie
Membre Naturel
Messages: 26
Enregistré le: 26 Jan 2006, 14:29

par ParLaLaSortie » 26 Jan 2006, 19:57

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

ParLaLaSortie
Membre Naturel
Messages: 26
Enregistré le: 26 Jan 2006, 14:29

par ParLaLaSortie » 26 Jan 2006, 20:05

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

ParLaLaSortie

Florix
Membre Relatif
Messages: 278
Enregistré le: 12 Nov 2005, 19:46

par Florix » 26 Jan 2006, 20:11

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

abcd22
Membre Complexe
Messages: 2426
Enregistré le: 13 Jan 2006, 15:36

par abcd22 » 26 Jan 2006, 20:32

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 cas possibles.

yos
Membre Transcendant
Messages: 4858
Enregistré le: 10 Nov 2005, 21:20

par yos » 26 Jan 2006, 20:36

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.

Florix
Membre Relatif
Messages: 278
Enregistré le: 12 Nov 2005, 19:46

par Florix » 26 Jan 2006, 21:29

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

Florix
Membre Relatif
Messages: 278
Enregistré le: 12 Nov 2005, 19:46

par Florix » 27 Jan 2006, 16:27

:help: :help: :help: :help: :help: :help: :help: :help: :help: :help: :help: :help::help:

Nicolas_75
Membre Rationnel
Messages: 919
Enregistré le: 29 Aoû 2005, 12:42

par Nicolas_75 » 27 Jan 2006, 17:05

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

Nicolas

ParLaLaSortie
Membre Naturel
Messages: 26
Enregistré le: 26 Jan 2006, 14:29

par ParLaLaSortie » 27 Jan 2006, 17:29

C'est curieux, ne peut-on pas dire que:

d'où

donc, les ayant même moyenne, il vient:
.

Ce qui est assez évident: en moyenne chaque tiroir a 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 et non pas la moyenne. Et là c'est plus dur...

J'aurais tendance à dire:
et la seconde proba se relie immédiatement au début du problème, puisque tu as calculé tous les cas favorables.

Alpha
Membre Complexe
Messages: 2176
Enregistré le: 21 Mai 2005, 12:00

par Alpha » 28 Jan 2006, 10:18

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/showthread.php?t=3690&highlight=lanc%E9

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

Cordialement, Alpha

Florix
Membre Relatif
Messages: 278
Enregistré le: 12 Nov 2005, 19:46

par Florix » 29 Jan 2006, 18:22

Bonjour,

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

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

J'aurais tendance à dire:
et la seconde proba se relie immédiatement au début du problème, puisque tu as calculé tous les cas favorables.

yos
Membre Transcendant
Messages: 4858
Enregistré le: 10 Nov 2005, 21:20

par yos » 29 Jan 2006, 18:59

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.

BidGate
Messages: 4
Enregistré le: 12 Aoû 2019, 08:22

Re: Dénombrement de sommes d'entiers (Celui qui réussit cet

par BidGate » 08 Mar 2020, 07:43

Be pourrait on pas écrire tout simplement r^n? Comme le nombre d'applications d'un ensemble à n élts vers un autre à r élts?

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 87 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite