Exercice de combinatoire

[inviteae18d553]

Bonjour,

après avoir passé (perdu me paraît plus proche de la réalité) plusieurs heures de mon après-midi là-dessus, je renonce et solicite votre aide pour m'aider à résoudre un problème de combinatoire dans mes équations.

Observez la somme suivante :



Je serai intéressé dans cette somme qui comporte n^4 termes de savoir

* Combien de fois il y aura 4 fois le même indice (réponse manifeste : n fois)
* Combien de fois il y aura 3 fois le même indice et un indice différent
* Combien de fois il y aura 2 fois un même indice et deux autres indices différents.
* Combien de fois il y aura 2 fois un même indice et deux fois un même autre indice.
* Combien de fois il y aura 4 indices différents.

La somme de ces réponses devrait faire n^4, c'est précisément parce que je n'arrive jamais à ça que je renonce et requiers votre aide.
-----

[RoBeRTo-BeNDeR]

Bonjour,

- 4 fois le même indice me semble juste.
- 3 fois le même indice, réfléchissons un peu :

Fixons i=j=k=1 ce qui nous laisse pour l les valeurs 2...n donc (n-1) valeurs

d'où on peu prendre i=j=k=m avec m de {1...n} (n valeurs) et donc pour chaque m on aura n-1 valeurs possible de l d'où celà nous donne (n-1)*n
et comme chaque variable joue un même role alors ceci peut se faire sur i sur j sur k aussi bien que sur l ce qui nous donne 4 fois plus de possibilités donc 4n(n-1) (si je ne me trompe pas)

Pour résumer on choisit le triplet fixe parmi 4 variables donc Un fois choisit on choisit la valeur prise parmi n donc et enfin la valeur prise par la dernière variable parmi les n-1 restantes donc d'où en multipliant le tout on obtient bien 4n(n-1)

A ton tour pour les 2 derniers cas en expliquant comment tu procèdes comme je viens de le faire.

RoBeRTo

[inviteae18d553]

* Combien de fois il y aura 2 fois un même indice et deux autres indices différents.


j'ai n choix pour le premier indice, puis 1 choix pour le deuxième, n-1 pour le 3ème et n-2 pour le 4ème

Toutefois l'ordre dans lequel j'ai fait ceci pourrait être modifié. La réponse est donc n(n-1)(n-2) multiplié par une constante.

Par dénombrement

AABC
AACB
ABAC
ACAB
BAAC
CAAB
BCAA
CBAA
BACA
CABA
ABCA
ACBA

soit 12 possibilités

12n(n-1)(n-2)

Correct ?

[RoBeRTo-BeNDeR]

Il me semble oui

Je vais tenter de t'expliquer pour la constante ce que tu as oublié de dire

Alors on doit choisir des valeurs pour un couple et des valeurs pour les 2 indices restants.

On doit choisir 2 indice. Le premier on a 4 choix et le second il en reste donc 3 donc 4x3=12
Sinon on peut se dire que l'on en prend 2 parmi 4 donc MAIS CE N'EST PAS UNE BONNE IDEE! comme dans ce qui précède les deux indices choisit non pas de sens c'est à dire que {i,j}={j,i} il faut donc multiplier par deux pour ainsi séparer les deux cas d'où (i,j)(j,i) donc on a bien 6*2=12 mais le premier raisonnement est plus simple.

Allez au dernier maintenant

[A voir en vidéo sur Futura]

[inviteae18d553]

Le dernier me fait peur car c'est probablement de lui que vient l'erreur -_-'


On a donc n choix pour le premier indice, un seul pour le second, n-1 pour le 3ème et un seul pour le dernier.

Toutefois, je peux faire ça avec d'autres ordres.

Par dénombrement

AABB
BBAA
ABBA
BAAB
BABA
ABAB

6.

Donc 6n(n-1)

Pour le dernier j'ai n(n-1)(n-2)(n-3)
et j'ai ABCD. De combien de façon puis-je agencer ces lettres ? Je dirai 4!


Somme totale :

n+4n(n-1)+12n(n-1)(n-2)+6n(n-1)+4!n(n-1)(n-2)(n-3)

réponse attendue : n^4

Pour n=10, je trouve que la somme totale vaut 130510. Quelques chose ne va pas

[RoBeRTo-BeNDeR]

Bonjour,

Sur le dernier cas il ne faut pas dénombrer les permutations possibles car elle sont déjà prise dedans!
Mias ca ne donne toujours pas la bonne réponse...

RoBeRTo

[inviteae18d553]

Je veux changer d'avocat !

Quelqu'un d'autre ?

[invite1e1a1a86]

et si on prenais n=4? il n'y a alors "que" 4^4 possibilités.


* Combien de fois il y aura 4 fois le même indice (réponse manifeste : n fois)
4 (=n) les 1111 2222 3333 4444

* Combien de fois il y aura 3 fois le même indice et un indice différent
1112, 1113, 1114, 2221, 2223,2224,3331,3332,3334, 4441,4442,4443+ tous les autres en permutant: 4*3*4=48 (=4n(n-1) )


* Combien de fois il y aura 2 fois un même indice et deux autres indices différents.
1123,1132,1124,1142,1132,1123 + les autres avec des 22/33/44 puis toute permutation de choix de la paire.

ça nous donne 6*4*6=144 (différent de votre résultat!)

* Combien de fois il y aura 2 fois un même indice et deux fois un même autre indice.
1122,1133,1144, + les 22/33/44 plus changer les paires.

ça nous donne 3*4*3=36 (encore différent!)

* Combien de fois il y aura 4 indices différents.
le reste: les 1234 dans n'importe quel ordre soit 4*3*2=24 (=n(n-1)(n-2)(n-3))

au final:
24+36+144+48+4=256 le compte est bon.

attention au double comptage. par exemple dans le cas 3
AABB et BBAA vous donne les même termes (sauf si par exemple vous imposer A>B) d'ou le facteur 2 (36=3*n(n-1))

de même avant AABC et AACB (sauf si on impose par exemple B<C)
encore un facteur 2 (144=12n(n-1)(n-2))

et donc au final