Nombre de combinaisons possibles ?

eratosthene

Bonjour la communauté !

J'ai x lettres que je répartis dans y groupes. Je liste toutes les combinaisons possibles.

Exemple pour 4 lettres à répartir dans 2 groupes, j'ai 7 combinaisons possibles :

a - bcd
b - acd
c - abd
d - abc
ab - cd
ac - bd
ad - bc

Pouvez-vous m'aider à trouver la formule pour déterminer le nombre de combinaisons possibles à partir de x et y ?

Un immense MERCI d'avance !

Eric

Poirot

Le nombre que tu cherches est le coefficient binomial $\binom{x+y}{x} = \binom{x+y}{y}$. Une fois que tu as choisi tes $x$ éléments du premier groupe, il n'y a pas d'autre choix que de mettre les $y$ autre dans l'autre groupe, et le raisonnement est symétrique en $x$ et $y$.

eratosthene

Merci Poirot !

Ton raisonnement est-il valable lorsqu'il s'agit de répartir (par exemple) ces 4 lettres dans 3 groupes ?
Je cherche une formule qui permettrait de calculer le nombre de combinaisons en fonction du nombre et lettres ET du nombre de groupes à former.

Exemple pour 4 lettres à répartir dans 3 groupes, j'obtiens 6 combinaisons possibles :

ab - c - d
ac - b - d
ad - b - c
bc - a - d
bd - a - c
cd - a - b

Poirot

Ton exemple est faussement simple car avec $4$ lettres, une fois un groupe à deux éléments fixé, il ne reste plus qu'un autre choix derrière. Il me semble également que tu ne différencies pas entre, par exemple, $(\{a, b\}, \{c\}, \{d\})$ et $(\{a, b\}, \{d\}, \{c\})$, ce qui donne simplement le choix des deux premières lettres $\binom{4}{2} = 6$. Est-ce volontaire ? Si oui, ça va influencer la réponse.

eratosthene

Je ne différencie pas ({a,b},{c},{d}) et ({a,b},{d},{c}), c'est la même combinaison pour moi.
J'ai hâte de lire ta réponse :-)

gerard0

Les deux donnent simplement {{a,b},{c,d}} puisqu'il n'y a pas d'ordre entre c et d. Donc c'est un problème à 2 boites de 2.

Cordialement.

eratosthene

Merci Gérard, en suivant tes indications j'ai trouvé exactement l'explication que je cherchais :
Répartir n objets dans k boites => C(k-1, n+k-1) combinaisons possibles

depasse

[size=small]Bonsoir,

Pour tout $(x,y) \in \mathbb N^{*2}$, le nombre $p_{x,y}$ de partitions d'un ensemble de cardinal $x$ en $y$ parties est
$0$ si $x<y$,
$1$ si $y=1$,
$p_{x-1,y-1} + y\ p_{x-1,y}$ si $x \geq y \geq 2$.

$1$
$1\ \ 1$
$1\ \ 3\ \ 1$
$1\ \ 7\ \ 6\ \ \ 1$
$1\ 15\ 25\ 10\ 1$
$1\ 31\ 90\ 65\ 15\ 1$

etc...

Je ne vois pas de formule close...sauf pour la diagonale, la sous-diagonale et la seconde colonne ;-)

Bonne année

Paul

[/size]

lourrran

J'arrive en retard...
Dans le cas de 2 boites, tu as la boite qui contient l'élément a, et l'autre boite.
Donc avec {a,b,c,d} , la question est de placer les éléments b,c,d , soit avec a, soit dans l'autre boite.
On a 2 possibilités pour b (avec a ou dans l'autre boite), 2 possibilités (pareil) et 2 possibilités pour d ( pareil)

Donc 2x2x2=8 possibilités. Tu n'en trouves que 7, parce que tu exclues le cas où on a {a,b,c,d} dans une des boites, et on laisse l'autre boite vide.
C'est voulu ?

Pour n objets à répartir dans 2 boites, on a donc $2^{n-1}-1$ solutions.

depasse

[size=small]
Bonjour,

@Eratosthène, la formule qui te satisfait apparemment est en contradiction avec ton exemple initial: tu trouves $7$ façons de ranger $4$ objets dans $2$ boîtes (dont aucune n'est vide) alors que $\binom {4+2-1} {2-1}=\binom {5} {1}=5$





[/size]

eratosthene

Tu as raison, en fait la bonne formule se trouve à cet endroit : http://villemin.gerard.free.fr/Denombre/aaaBalle/Balle00.htm#c5bn3p