Discussion :

[bizulk]

Bonjour,

Je n'arrive pas à déglutiner une formule qui permettrait de calculer le nombre total d'arrangement d'intercalaire dans une suite.
Je m'explique avec le cas suivant :
Soit 2 intercalaires notées par 'a' et 'b'
Soit une suite ordonnée de trois éléments notés par des chiffres : 1 2 3

Je dois composer une suite mélangeant les intercalaires à la suite, par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
a,b,1,2,3
a,1,b,2,3
a,1,2,3,b

Voilà je pensais par chercher toutes les façons de placer les intercalaires, puis
sur les suites ou les intercalaires se succèdent utiliser un factorielle.

Merci pour toute suggestion.

[bizulk]

On comprend avec cet exemple que 1,2,3 doivent se suivrent, mais que l'on fait comme on veut avec a,b,c. Sachant que leur ordre est à prendre en compte pour le décompte.

[Alexis.M]

imagine que tu numérote les positions possibles prises par les intercalaires.
Pour une séquence de n nombres tu as n+1 positions d'intercalaires possibles.

Il suffit donc de trouver le nombre de combinaisons de m intercalaires prises parmis n+1 possibilités... ou les arrangements si l'ordre n'est pas important.

[bizulk]

Oui mais si m>(n+1) ?

Sinon j'ai abordé le problème en le simplifiant (sans distinction des intercalaires). J'ai trouvé une solution comme étant la suivante :
Soit N le nombres d'intercalaires
Soit E la taille de la suite

Solution(N,E) = 1 + Somme(n=1 à N) Solution(n, E-1).
Avec
Solution(1,i) = i+1 (i>0)
Solution(n,1) = n+1
On s'arrête quand n=1 ou e=1.

Je peux détailler comme je trouve cela...

Maintenant il me resterait à distinguer les intercalaires.

[bizulk]

Je vais vérifier si la solution est aussi simple qu'un arrangement de N intercalaires sur E+1 positions....

[bizulk]

Donc si jeprends l'exemple suivant :
N = 2, E = 2
L'arrangement est A(2,3) ie 3!/1! soit 6.

Maintenant pour cette exemple on peut dérouler pour vérifier :
D'abord on considère que les intercalaires sont identiques, je les notes X
La suite est notée avec les chiffres soit 1 et 2
On a donc les possbilités suivantes

XX 1 __ 2 __
_X 1 X_ 2 __
_X 1 __ 2 X_
__ 1 X_ 2 X_
__ 1 __ 2 XX
__ 1 XX 2 __

On retrouve bien 6 possibilités mais comme leur ordre compte on considère chacune des lignes en remplace une X par A et l'autre B. On voit facilement que cela multiplie le nombre par 2, donc on a 12 possibilités.

[bizulk]

Si l'on considère comme tu l'as dit que l'on arrange d'abord les positions, puis ensuite que l'on distribue les intercalaires sur ces positions ?
Cela donnerait donc N! A(N,E+1).

[bizulk]

Oui mais si N > E+1 ?

Si on considère par exemple N=4 intercalaires, et E=2 alors :
_X_X_X_X_
J'ai quatre positions pour poser le premier nombre, mais pour le second je dois obligatoirement le poser après l'autre.

Déroulons pour voir :
XXXX 1 ____ 2 ____

XXX_ 1 ___X 2 ____
XXX_ 1 ____ 2 X___

XX__ 1 XX__ 2 ____
XX__ 1 X___ 2 X___
XX__ 1 ____ 2 XX__

X___ 1 XXX_ 2 ____
X___ 1 XX__ 2 X___
X___ 1 XX__ 2 XX__
X___ 1 X___ 2 XXX_

____ 1 XXXX 1 ____
____ 1 XXX_ 2 X___
____ 1 XX__ 2 XX__
____ 1 X___ 2 XXX_
____ 1 ____ 2 XXXX

Ca fait 5+4+3+2+1 = 15 possibilités, or A(2,4+1) = 20. On s'y attendait dans ce listing on a supprimé les inversions des positions des nombres ce qui multiplierait par 2 la liste ci-dessus.

[bizulk]

Avec ce qu'on a déroulé au dessus je propose donc la solution suivante :

Solution(N,E) = 1 + Somme(n=1 à N) Solution(n, E-1).
Avec
Solution(n,e) = A(n, e+1) ssi n<= e+1,
Solution(1,i) = i+1 (i>0) (cas spécifique de ci-dessus),
Solution(n,1) = n+1
On s'arrête quand n=1 ou e=1.

Maintenant en distinguant les intercalaires on obtient : N! Solution(N,E) .

Voilà j'écrirai un code qui opposerait ce calcul à une méthode de recherches des listes composables :
Soit N intercalaires et une suite de E élements consécutifs.On a donc E+1 Positions

global nbChemins = 0 ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Recherche(QList<intercalaire> li,QList<position> lp, Qlist<QPair<intercalaire,position> > chemin)
Si taille(li) nulle alors 
    nbChemins++
    return
si taille(lp) == 1 alors
   chemin.ajouter(li)
sinon
   pour chacune des positions
   pour chacune des intercalaires
       li = li - intercalaire choisi (sauf si intercalaire=rien)
       lp = lp - position choisie
       chemin + QPair<intercalaire choisi, position choisie>
       Recherche(li, lp, chemin)

Programme
Je peuple li avec toutes les intercalaire + 'rien' (les intercalaires peuvent aussi etre des entiers ou des lettres)
Je peuple lp avec des entiers allant de 1 a E+1
chemin est au départ vide
Recherche( li , lp , chemin)

[/CODE]

[Alexis.M]

Si tu as le droit de mettre tes intercalaires vraiments n'importe où c'est encore plus facile...

J'ai n+1 positions possibles, la première itercallaires à n+1 possibilité, la deuxième aussi, etc.... Le nombre de positionnement de mais m intercallaires est simplement (n+1)^m. Si les intercallaires sont indifférencialbles il faut encore diviser par le nombre de permutations m!

[kwariz]

Hello,

en reprenant N le nombre d'intercalaires, et E la taille de la suite :
le problème consiste à répartir N intercalaires indistingables les uns des autres sur E+1 positions distingables, le nombre de solutions est :

Solution(N,E)=binom(N+E,E)=(N+E)!/(E!N!)

[bizulk]

Merci pour ton suivi.
C'est aussi simple que ça ? ... Je pense qu'il a quelque chose j'ai mal communiqué.
Si on dissocie les intercalaires, chaque ajout va ajouter une position pour l'intercalaire suivante.
Mettons que j'ai trois positions possibles (2 'X') et deux intercalaires A B

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
AB   X     X
A    X  B  X
A    X     X  B
     X A   X  B
     X     X AB
     X AB  X

Ca me fait 6, plus 6 en échangeant les places de A et B.
Ca me fait au total douze.
En appliquant ta formule j'ai (2+1)^2 = 9

[bizulk]

Hello,

en reprenant N le nombre d'intercalaires, et E la taille de la suite :
le problème consiste à répartir N intercalaires indistingables les uns des autres sur E+1 positions distingables, le nombre de solutions est :

Solution(N,E)=binom(N+E,E)=(N+E)!/(E!N!)

Si je reprends l'exemple ci-dessus ça fait :
Solution(2,2) = (4!)/(2!2!) = (2x3x4)/(2x2) = 6. Je n'ai que la moitié !

[kwariz]

Si je reprends l'exemple ci-dessus ça fait :
Solution(2,2) = (4!)/(2!2!) = (2x3x4)/(2x2) = 6. Je n'ai que la moitié !

Re-,

j'ai précisé intercalaires indistingables les uns des autres (cas C1), si on distingue les intercalaires (cas C2) alors à chaque solution du cas C1 correspondra N! solutions dans le cas C2 (le nombre de permutations sans répétitions des intercalaires) :

Par exemple pour le cas C1(N=3,E=2) :
_1XX2X

On obtient :
_1AB2C -> ABC
_1AC2B -> ACB
_1BA2C -> BAC
_1BC2A -> BCA
_1CA2B -> CAB
_1CB2A -> CBA

On a donc dans le cas C1 : Solution1(N,E)=(N+E)!/(N!E!)
et dans le cas C2 : Solution2(N,E)=(N+E)!/E!

[bizulk]

Je suis d'accord qu'il faille multiplier par N!
Ta solution me paraît être la bonne et la plus simple.
Par contre si j'imagine bien qu'en distribuant les intercalaires et les positions ça me donne (N+E)!, comment justifier la division par E! ?

[bizulk]

Ha oui la suite ne peut être qu'ordonnée (1, 2, 3) donc tu supprimes ces arrangements là avec le dénombrement de cette suite.
Bravo !