Problème combinatoire

[Absaloth]

Bonjour à tous,

C'est probablement un problème assez bête mais je bloque sur l'exo :

On a Nb boules indiscernables, et Nt tiroirs, avec Nb<Nt.

Il faut trouver le nombre de manières de placer les boules dans les tiroirs, sachant qu'un tiroir peut contenir autant de boules qu'on veut.

Si les boules étaient discernables, on aurait juste le nombre de manières donné par (Nb)^Nt. Cependant, avec l'indiscernabilité ça m'embrouille et je ne parviens pas au bon résultat.

Merci d'avance pour votre aide.
-----

[pseudoarallonge]

Bonjour,

C'est effectivement plus compliqué.
Pour te rassurer, dis toi qu'Einstein a buté aussi pas mal de temps, avant de remarquer le lien avec les photons.

Sinon, l'indiscernabilité fait que tu dois considérer des combinaisons et non des arrangements.

Ensuite, puisque dans un même tiroir on peut mettre autant de boules que l'on veut, on peut voir la configuration suivante équivalente :
Nt+Nb-1 tiroirs.
Ainsi au lieu de mettre une deuxième boule dans un même tiroir, il suffit de la placer dans 1 des Nb-1 tiroirs.
Ensuite il suffit d'appliquer la formule bien connue de la combinaison.

[Absaloth]

Merci pour ta réponse. Par contre je ne suis pas sûr de suivre.

Je ne sais pas si c'est de cela que tu parles, mais je crois connaitre l'astuce où au lieu de placer les boules dans les tiroirs, tu places les parois des tiroirs entre les boules : le nombre de manières est alors donné par la combinaison de Nt-1 (les cloisons) parmi Nb+1 (ou quelque chose du genre). Cependant, il me semble que cela ne marche que lorsque Nb>Nt non?

Peut-être que j'ai juste mal compris ton explication.

[pseudoarallonge]

Dans le premier message tu dis Nb<Nt et maintenant tu me dis Nb>Nt.
Sur ce coup là, tu me perds...

[A voir en vidéo sur Futura]

[Absaloth]

Justement, dans mon problème c'est Nb<Nt (moins de boules que de tiroirs), alors qu'il me semble que la technique de déplacer les cloisons des tiroirs au lieu de déplacer les boules ne marche que, au contraire, pour Nb>Nt.

[Absaloth]

Ah c'est bon, je pense avoir compris ! Merci !

[pseudoarallonge]

Justement, dans mon problème c'est Nb<Nt (moins de boules que de tiroirs), alors qu'il me semble que la technique de déplacer les cloisons des tiroirs au lieu de déplacer les boules ne marche que, au contraire, pour Nb>Nt.

Excuse moi, si je ne lisais pas les messages en diagonale, cela irait mieux...

Sinon, comme je ne suis pas un matheux pur et dur, je me raccroche à des choses que je connais.
Ainsi pour ton affaire, je vois deux applications :

1. Le tirage du loto : les tiroirs c'est la grille, les boules ce sont les boules. Mais dans ce tirage là, lorsqu'une boule est sortie, on la remet immédiatement dans le mélangeur, de sorte qu'une même boule puisse ressortir plusieurs fois.

2. La théorie cinétique des gaz
Imaginons les molécules de gaz comme des boules pouvant se déplacer dans une cavité ou une boite.
La boite est quadrillée dans les 3 dimensions de sorte à avoir des petites boites représentant les tiroirs.
La encore, le nombre de tiroirs est supérieur au nombre de boules, sinon les boules ne pourraient se déplacer.

[Médiat]

Bonjour,

Si j'ai bien compris, il s'agit de combinaisons avec répétitions, voir l §7.1 du document : http://forums.futura-sciences.com/ma...ml#post4570545

[minushabens]

Le fait qu'il y ait plus ou moins de boules que de tiroirs ne joue pas. Une façon élégante de voir les choses est la suivante : on considère une chaîne de n+m-1 symboles de deux sortes, n points (".") et (m-1) barres "|"). Une telle chaîne est ..|.||....|.| L'interprétation est qu'un point représente une boule et une barre la limite entre deux tiroirs. Les Limites extrêmes des tiroirs ne sont pas représentées, c'est pourquoi il n'y a que (m-1) barres pour m tiroirs. Dans mon exemple il y a 5 barres, donc 6 tiroirs et le tiroir de droite est vide. Alors il est facile de voir que le nombre de configurations est égal au nombre de façons de choisir n objets parmi n+m-1, c'est le coefficient binomial C(n+m-1,n)=C(n+m-1,m-1)

[Médiat]

Je préfère utiliser (m+1) barres et imposer que la première et la dernière place soit des barres (cela ne change donc rien au résultat) mais votre exemple serait : |..|.||....|.||,
ce qui permet de mieux visualiser les cases, en particulier de voir que la dernière est vide.
En tout état de cause c'est ainsi que je l'ai fait dansle document cité.

[Absaloth]

Merci à tous, c'est bien clair maintenant .

[pseudoarallonge]

Je ne suis pas particulièrement pro-formule, mais écrire les formules (sans répétition)et sous forme développé, de les comparer entre elles, de les jauger et de voir en quoi elles diffèrent et en quoi elles se ressemblent, aide grandement l'intuition...

[minushabens]

Ton premier coefficient binomial est nul si Nb>Nt. En fait il n'y a pas lieu de distinguer les cas Nt<Nb et Nt>Nb.

[joel_5632]

bonjour

Il y a quatre variantes possibles pour dénombrer les rangements de b boules dans t tiroirs

- On considère les boules et les tiroirs discernables
Il y a rangements possibles

- les boules sont indiscernables et les tiroirs discernables
Il y a rangements possibles

- Pour les 2 autres cas correspondant aux tiroirs indiscernables et aux boules discernables ou pas, il n'existe pas de formules donnant le nombre de rangements mais des relations de récurrence. J'ai un pdf sur le sujet si ça intéresse quelqu'un.

[pseudoarallonge]

bonjour



- les boules sont indiscernables et les tiroirs discernables
Il y a rangements possibles

Si je développe vos formules





Oui, effectivement il y a égalité. C'est remarquable.

Par contre pour chipoter un petit peu: parle t -on de rangements ou de combinaisons ?

[joel_5632]

Oui, effectivement il y a égalité. C'est remarquable.

Rien de remarquable, c'est juste
Quand on choisit une partie de k éléments dans un ensemble de n éléments, on a automatiquement une partie à n-k éléments.

Par contre pour chipoter un petit peu: parle t -on de rangements ou de combinaisons ?

est le nombre de combinaisons à k éléments avec répétitions dans un ensemble de n éléments.
k peut être supérieur à n.

[pseudoarallonge]

Rien de remarquable, c'est juste

Il faut toujours s'étonner de tout et s'émerveiller d'un rien, comme les enfants.
Que deux écritures mathématiques représentent la même quantité, c'est pas très courant tout de même. Les maths n'ont pas la propriété de parcimonie.

[minushabens]

Si tu te souviens que C(n,k) est le nombre de parties à k éléments parmi n, alors il est clair que choisir les k éléments à garder est équivalent à choisir les (n-k) éléments à exclure. Et donc le nombre de parties à k éléments est égal au nombre de parties à (n-k) éléments.

[pseudoarallonge]

Si tu te souviens que C(n,k) est le nombre de parties à k éléments parmi n, alors il est clair que choisir les k éléments à garder est équivalent à choisir les (n-k) éléments à exclure. Et donc le nombre de parties à k éléments est égal au nombre de parties à (n-k) éléments.

C'est un peu comme le verre à moitié-plein, le verre à moitié-vide. Tout dépend du point du vue qu'on adopte