Exercice de dénombrement

[haltius]

Bonjour,

J'ai un petit problème de dénombrement très concret.

Admettons que j'ai un gros paquet de cartes (contenant N cartes)
Je dois couper ce paquet 2 fois successivement pour obtenir X paquets plus petits (X < N).
On coupe "successivement" c'est a dire que je coupe mon gros paquet en K petits paquets (K au moins egal a 2) X1, X2, ..., XK, puis je coupe chaque sous paquet en sous-sous paquets X11, X12, ...,X1L, X21, X22, ... ainsi de suite, tels qu'au final j'obtienne X paquets.
On doit donc au minimum couper en 2, et pas de maximum (dans la limites des contraintes de X bien entendu).

Question 1: J'essaie de trouver un algo pour lister exhaustivement toutes les possibilités de coupe:
Ex: Si X=50, couper en 2 puis chaque paquet en 25
couper en 2 puis en 45 et 5,
couper en 5 puis en 2, 2, 2, 2, 42, etc...
Question 2: Comment calculer le nombre de possibilités?

Question subsidiaire: Peut on generaliser cet exemple avec un nombre quelconque C de coupes successives (ici C=2).

D'avance, merci.

[alben]

Bonjour,
Au final, on obtient donc 50 paquets contenant chacun au moins une carte (si j'ai bien compris).
Il s'agit donc de répartir N cartes et X-1 séparateurs.
Parmi ces séparateurs, certains sont particuliers, ils délimitent les paquets intermédiaires, il y en a K-1.
Si j'ai bien compris, tout paquet intermédiaire doit être recoupé au moins en deux, donc les séparateurs particuliers ne peuvent occuper la première ni la dernière place. En outre, ils ne peuvent se succéder.
Il va donc falloir évaluer la façon de choisir K-1 objets parmi X-1 avec les contraintes évoquées.
Ensuite il faut placer ces séparateurs parmi les N cartes avec une contrainte identique (pas de paquet de 0 carte)
Le nombre de possibilités sera le produit de ces deux résultats.

à suivre
edit non , j'ai supprimé les formules qui n'allaient pas

[alben]

suite
1 De combien de manière peut-on placer K-1 séparateurs particuliers parmis X-1 de telle sorte qu'il y ait au moins 1 séparateur ordinaire entre deux particuliers.
Le plus simple est de commencer par prélever K séparateurs ordinaires et de remplacer K-1 séparateurs ordinaires dans ceux qui restent : X-1-K
Il y a possibilités. Ensuite on inserera nos K séparateurs ordinaires dans chacune des K parties formées par les K-1 séparateurs particuliers. On a ainsi la garantie que toutes les parties contiendront au moins un séparateur ordinaire.
2 même raisonnement, il faut maintenant placer nos X-1 séparateurs (ordinaires et spéciaux) dans une liste contenant N+X-1 éléments. On commence par éliminer X cartes, on place nos séparateurs, puis on réinjecte nos X cartes en en plaçant une derrière chaque séparateurs. L'ordre des cartes sera ensuite rétabli de manière à retrouver l'ordre initial.
On trouve ici
Et le nombre total de possibilités est finalement
Je ne pense pas m'être trompé mais dans ce genre de calculs, ce n'est pas garanti :triste:

[alben]

Bonjour,
Suite et fin
La méthode un peu fastidieuse pour dénombrer les possibilités (il y a peut-être plus direct) nous fournit un moyen de construire les cas un par un.
par exemple on pose N=30, X=12, K=4
1ère étape : choisir les 3 limites de paquets intermédiaires parmi les 11 limites de paquets finaux.
Il faut d'abord choisir K-1=3 nombres parmis X-1-K=7 par exemple (1;4;7).
Ensuite, injecter un séparateur entre chaque choix revient à décaler selon la formule , ici
1->1+1=2, 4->4+2=6 7->7+3=10
NB j'ai volontairement pris les extrêmes dans le choix, on voit bien que la méthode garantit que chaque paquet intermédiaires sera découpé puis ça donne (en gras les limites des gros paquets)
S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11
On visualise les 4 paquets intermdiaires, le premier sera coupé en 2 ainsi que le dernier alors que les deux autres sont coupés en 4.
2ième étape: mettre les cartes dans les paquets On suppose que les cartes sont numérotées de 1 à 30.
Il suffit de choisir 11 nombres de 1 à N-1=29, par exemple (1,3,7,8,14,16,17,19,22,25,29) et c'est alors très simple, chacun des séparateurs viendra après la carte dont le numéro aura été choisit.
Ainsi le premier petit paquet comprendra uniquement la carte 1, le deuxième les cartes 2 et 3 et comme S2 était un séparateur spécial, le premier paquet intermédiaire sera formé des cartes 1,2,3.
De même le deuxième paquet intermédiaire contiendra les cartes 4 à 16 et sera découpé en 4 : (4à7) (8) (9à14) (15 et 16)
Et voilà. Je pense que tu as besoin de programmer des simulations, ça ne devrait pas être difficile.

PS merci de répondre, j'aimerais savoir si ça te sert

[haltius]

Oui merci Alben de ta reponse! Ca va me servir bien entendu :)

[alben]

Correction de la fin du message 3

Et le nombre total de possibilités est finalement
Pas de simplification dans le produit des coeff binomiaux