Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 06-12-2022 19:08:52

Franck D.
Membre
Inscription : 06-12-2022
Messages : 16

Combinatoire sur les séquences de n boules colorées

Bonjour, je cale sur un problème d'analyse combinatoire dont voici l'énoncé:

Combien existe-t-il de séquences de n boules colorées choisies parmi r couleurs possédant au moins un sous ensemble de d boules exactement de la même couleur ?

Voici un exemple calculé par un programme en générant toutes les séquences de 3 couleurs et en ne retenant que celles ayant des  sous-ensembles de 2 boules de la même couleur. On peut avoir 2 sous-ensembles ayant 2 boules de la même couleur mais ils sont de couleur différente. Ici, n = 4; r = 3; d = 2 et le résultat est 54 séquences parmi 81.

https://www.ibisc.univ-evry.fr/~delapla/images/exemple-color.png

Merci de votre aide.

Franck

Hors ligne

#2 06-12-2022 20:37:04

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,

  Pour t'aider, il faudrait avoir quelques précisions :
* Apparemment, tu mets un ordre sur tes boules : par exemple, la suite (vert,vert,rouge,rouge) n'est pas la même que la suite (rouge,rouge, vert,vert). Est-ce bien le cas?
* Si c'est le cas, est-ce que les d boules de la même couleur doivent être consécutives?

F.

Hors ligne

#3 07-12-2022 11:19:22

Franck D.
Membre
Inscription : 06-12-2022
Messages : 16

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,
merci de t'intéresser à mon problème dont la solution m'aidera beaucoup.

oui les boules sont ordonnées, ce n'est pas un multi-ensemble mais une séquence. Ainsi, JBVV et VVBJ sont 2 solutions distinctes (d=2).

De plus  les boules de la même couleur ne sont pas nécessairement consécutives. Elles peuvent être placées n'importe où  dans la séquence, par exemple  RBRV est une bonne solution avec la couleur R(ouge) (n=4, d=2).

Cependant, il y en a exactement d de cette même couleur  (et non pas au moins ou au plus  d). Par contre on peut avoir plus d'un sous ensembles de d boules dans la séquences avec la même couleur, mais chacune distincte par ensemble. Par exemple, la séquence RVRV  est une bonne solution avec d=2 pour R et V (n=4).

F.

Dernière modification par Franck D. (07-12-2022 11:39:14)

Hors ligne

#4 07-12-2022 12:05:55

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 074

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,
allez je me lance...
Nécessairement $n \ge d$. Je chercherais à savoir :
-le nombre de choix possibles de $d$ boules de la même couleur.
-Pour chaque couleur de ces $d$ boules, le nombre de manières de les ranger parmi $n$ boules
-le nombre de choix possibles pour les $n-d$ boules restantes

Dernière modification par Zebulor (07-12-2022 12:06:16)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#5 07-12-2022 13:00:40

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,

  Le dénombrement est de plus en plus délicat si $n$ devient grand. Je vais présenter comment faire si $2d\leq n<3d$.
On peut se baser sur ce que propose Zébulor :
1. On commence par choisir la couleur qui va se répéter $d$ fois : il y a $r$ choix possibles.
2. Pour ces couleurs, on choisit l'emplacement des $d$ boules : il y a $\binom nd$ choix possibles
3. Sur les $n-d$ autres emplacements, on choisit une boule de couleur différente : il y a $(r-1)^{n-d}$ choix possibles.

Malheureusement, si on se contente de cela, on ne trouve pas le bon résultat car on a compté deux fois les dispositions où il y a deux couleurs qui se répètent $d$ fois. Il faut donc enlever ces tirages :
1. On commence par compter le nombre de choix de 2 couleurs parmi $r$ : il y a $\binom r2$ choix possibles.
2. On choisit l'emplacement des $d$ boules de la première couleur et celui des $d$ boules de la deuxième couleur : il y a $\binom nd\times\binom{n-d}d$ choix possibles
3. On complète pour les autres emplacements, il y a $(r-2)^{n-2d}$ choix.

Quand $n<3d$, il n'y a pas besoin d'aller plus loin car il ne peut pas y avoir 3 couleurs qui apparaissent $d$ fois. Sinon, il faudrait aussi tenir compte de cette possibilité.

Finalement, dans le cas $2d\leq n<3d,$ on trouve
$$r\times\binom nd\times (r-1)^{n-d}-\binom r2\binom nd\times\binom{n-d}d\times (r-2)^{n-2d}.$$

J'ai l'impression que pour $n=4$, $r=3$ et $d=2,$ on trouve bien 54.

F.

[Edit Fred : Version corrigée grâce à Zebulor. Merci Zebulor!]

Hors ligne

#6 07-12-2022 14:39:36

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 074

Re : Combinatoire sur les séquences de n boules colorées

re,
j'avais bien le sentiment que ce que j'avais proposé était incomplet car sur l'exemple de notre ami Franck je trouvais 162 au lieu de 81 dispositions... :-) . On a bien au passage $81=r^n=3^4$

@Fred : je crois qu"il y a une coquille. J'écrirais plutôt
$$r\times\binom nd\times (r-1)^{n-d}-\binom r2 \times \binom nd\times\binom{n-d}d\times (r-2)^{n-2d}.$$
puisque pour chaque choix de 2 couleurs parmi $r$ on choisit les emplacements restants..

Dernière modification par Zebulor (07-12-2022 15:26:56)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#7 07-12-2022 15:50:16

Franck D.
Membre
Inscription : 06-12-2022
Messages : 16

Re : Combinatoire sur les séquences de n boules colorées

Merci je regarde attentivement

Dernière modification par Franck D. (07-12-2022 16:14:06)

Hors ligne

#8 07-12-2022 16:06:10

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,

Je détaille pas à pas ( sachant qu'on arrête de sommer quand arithmétiquement les termes n'auront plus de sens )

On dénombre le nombre d'injections acceptables de n positions numérotées 1,2, ... n dans  r x d "multi-objets".

Pour exactement une couleur de d boules ( pas d'autres )  on a le choix de 1 couleur parmi r, donc $\binom{r}{1}$.
Il faut aussi choisir (pour chaque choix précédent) les d positions qui vont leur correspondre, il y en a bien-sûr $\binom{n}{d}$

Les deux choix précédents étant effectués, il faut donc compter les nombre d'injections restantes possibles, donc de n-d positions dans (r-1)(d-1),
c'est A(  (r-1)(d-1) , n-d ).

C'est pas plus compliqué pour exactement deux couleurs de d boules, $\binom{r}{2}$ choix de (2) couleurs, $\binom{n}{d} \binom{n-d}{d}$ positions possibles,
et enfin il y a A( (r-2)(d-1) , n-2d ) injections possibles de n-2d positions restantes vers (r-2)(d-1).

etc.
On a donc ( en appelant X la quantité cherchée de séquences différentes possibles ) la somme suivante, qu'on arrête au dernier terme qui a un sens:

X = $\binom{r}{1}\binom{n}{d}A_{(r-1)(d-1)}^ {n-d} + \binom{r}{2}\binom{n}{d} \binom{n-d}{d}A_{(r-2)(d-1)}^{n-2d} + \binom{r}{3}\binom{n}{d} \binom{n-d}{d}\binom{n-2d}{d}A_{(r-3)(d-1)}^{n-3d } + $ .....

La somme s'arrête évidemment dès qu'on ne peut plus procéder à l'augmentation du nombre de sous-séquences d'exactement d boules.

Effectivement 54 séquences avec le sujet de Franck qui comportera deux termes : $\binom{3}{1}\binom{4}{2}A_2^2 + \binom{3}{2}\binom{4}{2} \binom{2}{2}A_1^0  $

Le dernier arrangement correspond à l'application vide  unique (injective, de 0 éléments vers ce qu'on veut ) de graphe vide.

Sujet original.

A.

Dernière modification par bridgslam (07-12-2022 16:36:02)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#9 07-12-2022 16:09:59

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 074

Re : Combinatoire sur les séquences de n boules colorées

re,
original je trouve aussi et d'autant plus intéressant qu'illustré par Frank avec la liste colorée des 54 échantillons..


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#10 07-12-2022 16:31:57

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Bonsoir,

Si vous aimez la couleur, il y en a pas mal ici https://www.youtube.com/watch?v=mRsg2lqEjPM avec les pavages d'Esher (et les maths qui vont avec of course).

Dans les messages, comme le prof actionne un groupe pour les dominos en cours de video, je lui ai proposé le calcul sur les triominos en actionnant le groupe
diédral du triangle, puis utilisation de Burnside.

A.

Dernière modification par bridgslam (07-12-2022 16:32:28)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#11 07-12-2022 17:33:20

Franck D.
Membre
Inscription : 06-12-2022
Messages : 16

Re : Combinatoire sur les séquences de n boules colorées

@bridgslam merci pour la contribution. Si je comprends la formule est :
$\sum _{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor } \binom{r}{k} \left(\prod
   _{j=0}^{k-1} \binom{n-j d}{d}\right) A^{(n-k d)}_{((r-k) (d-1))}$

Si c'est juste je l'ai testé pour le cas présenté et on trouve 54 effectivement. Je l'ai testé aussi pour une autre configuration (n=6;r=3;d=2)
par programme on trouve 540 cas et par la formule 90. Je ne sais pas pourquoi. Malgré mon attention j'ai pu faire une erreur.

Mais soit Di le nombre  solution comportant exactement i sous ensembles de la même couleur de taille d, on a pour l'exemple
D1=450 - D2 = 0 - D3 = 90. Pour D2 il n'est pas possible de faire des séquences de 2 sous-ensembles de taille 2 car si on prend 2 couleurs pour chacun des sous ensembles, il reste 1 couleur, donc nécessairement une troisième paire de boules de la même couleur.

As tu une idée pourquoi je n'ai pas le même résultat entre programme et formule ? Merci encore.

Hors ligne

#12 07-12-2022 18:03:28

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Bonsoir,

Je pense que vous essayez dans votre programme de calculer des applications vers des ensembles de couleurs ( cardinal r).
La formule considère des injections ( pas des applications quelconques) vers un ensemble plus grand imaginaire ( de cardinal rxd ) pour pouvoir représenter
les séquences avec leurs contraintes et qui tiennent compte de l'ordre en même temps. Chaque boule va vers une possibilité unique, mais qui peut être répétée,
il faut don considérer si vous voulez un multi-objet  $rouge_1, rouge_2, ... rouge_d$ ainsi que $jaune_1, ..., jaune_d$ etc et considérer les injections de
{1,..n }  vers tout cela ensemble... donc de cardinal rxd. On dénombre alors ce qui vous intéresse.

Je regarderai avec vos nouveaux paramètres (n=6) demain.

Bonne soirée
A.


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#13 07-12-2022 18:59:55

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 074

Re : Combinatoire sur les séquences de n boules colorées

De retour,
en relisant quelque chose m'échappe :

Fred a écrit :

... il ne peut pas y avoir 3 couleurs qui apparaissent $d$ fois...,

EDIT : a 22h j'en vois la raison...

Dernière modification par Zebulor (07-12-2022 22:00:45)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#14 07-12-2022 19:49:31

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Bonsoir,

@Franck,

Si on est bien d'accord sur votre problématique, pour moi D1 , c'est le nombre de configurations, où l'on a exactement 1 couleur répétée d fois, ici d=2.
Par exemple RRxxxx avec n=6.
Mais avec 3 couleurs en tout, ça veut dire que les deux autres couleurs sont au plus répétées une fois, alors qu'il reste 4 positions encore à affecter une autre couleur:
D1 est donc nul parce-que il n'y a pas d'injection dans un ensemble fini plus petit.
Pour D2 , un examen du même principe fait que D2 est nul ( il restera une couleur pour deux positions à affecter).
Enfin pour D3 c'est OK, on en trouve 90.
A chaque étape, on est bien resté sur un calcul d'injections, à cardinal égal au départ et à l'arrivée ( 6 = 3x2 ) , ce qui limite à 0 certains cas.

Si vous souhaitez des valeurs non nulles pour les premiers termes de la somme, il faut augmenter le nombre de couleurs possibles vis à vis de n.

Je ne sais pas ce que fait votre programme, mais si j'ai bien compris votre exercice, il y a une erreur quelque part dedans.

Si vous prenez par exemple n=6, r=4, d=2, vous devriez avoir moins de termes nuls en début de somme.
Là vous aurez des injections de 6 vers 8 , donc un peu plus de possibilités non nulles.
Dans votre sujet initial pas de termes nuls au début non plus, n=4  < 3x2 = rd  et les possibilités d'injections augmentent, c'est tout.

Donc je vous confirme la valeur de 90 avec n = 6, r = 3, d = 2, ou bien je n'ai rien compris à votre sujet.

-le résumé de ce que j'ai compris de votre exo (merci svp de me dire si je me trompe ):

- On a n positions, r couleurs, d est le nombre de répétions ( maximum possible) de toute couleur.

a/ A chaque position est affectée une couleur
b/ deux configurations diffèrent lorsque pour une position au moins les couleurs sont différentes
c/ Pour  chaque configuration, au moins une couleur est répétée d fois exactement
d/ Aucune couleur n'est répétée plus de d fois

En tout cas ces règles étaient en accord avec votre schéma en couleur.

Bonne soirée

A.

Dernière modification par bridgslam (07-12-2022 22:09:24)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#15 07-12-2022 21:26:30

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

J'ai fait pas mal de développements informatiques à une époque , un peu trop loin en tous cas dans l'immédiat pour taper le programme lui-même rapidement
(par exemple en python + tkinter pour l'affichage graphique, de mémoire c'est assez rapide, mais en pseudo-code,  la sélection pour n = 6, r = 3, d = 2 par exemple pour vérifier la valeur de 90 pourrait être comme ceci :

/////// initialisations
( n, r, d) <--- (6 , 3, 2)
total = 0

/////// boucle de parcours en force brute
Pour chaque configuration C parmi $r^n$
{
     ( R,V, J) <----   ( nbre de positions rouges(C) , nbre de positions vertes de(C) , nbre de positions jaunes (C)  )
      si max (R,V,J) == d
     {
       afficher( C )
       total += 1
     }
}

//////// nombre des configurations valables
afficher(total)    // 90 espéré!

A.

Dernière modification par bridgslam (08-12-2022 08:53:38)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#16 08-12-2022 09:23:33

Franck D.
Membre
Inscription : 06-12-2022
Messages : 16

Re : Combinatoire sur les séquences de n boules colorées

Bonjour @bridgslam

D1 correspond effectivement au nombre de cas ayant un sous ensemble unique de boules de même couleur de taille d, mais il ne me semble pas nul, par exemple pour n=6, d=2, r=3 on a
RRVVVB, RRVVVV, RRVBBB et toutes permutations de ces exemples correspondent au cas décrit pour R.

pour B et V on  n’a jamais un groupe de taille d dans ces profils. Il est soit plus grand, soit plus petit que d. La formule que j ai déduite de ton  précèdent message ne semble pas fonctionner pour cet exemple.


Dans ton énoncé  ci après

- On a n positions, r couleurs, d est le nombre de répétions ( maximum possible) de toute couleur.
a/ A chaque position est affectée une couleur
b/ deux configurations diffèrent lorsque pour une position au moins les couleurs sont différentes
c/ Pour  chaque configuration, au moins une couleur est répétée d fois exactement
d/ Aucune couleur n'est répétée plus de d fois
En tout cas ces règles étaient en accord avec votre schéma en couleur.
Bonne soirée

a/ b/ c/ oui mais d/ n est pas requis une couleur peut être répétée plus de d fois mais ce n est pas une solution car seule les cas où il y a au moins un sous ensemble de $d$ boules exactement de la même couleur est considéré comme une solution. d n’est pas un maximum car on a $r^n$ profils de boules possibles.

Merci encore de ton intérêt.

Dernière modification par Franck D. (08-12-2022 09:35:40)

Hors ligne

#17 08-12-2022 09:48:15

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,

Ceux que vous donnez ne passe pas l'épreuve puisque par exemple l'un a 3 verts, l'autre 4, qui dépassent donc d=2.
Dans votre premier schéma en couleur, je ne vois jamais de 3 ou 4 boules de même couleur... et là ça restait cohérent avec d=2...

En lisant la suite de votre post, apparemment il est normal que vous en comptiez plus.
En tous cas la formule que j'ai donnée ( compactée par vos soins, merci) donne le résultat en fonction des 4 alinéas que j'ai cité.

Si d peut être dépassé, c'est une autre question que j'examinerai en fin de semaine alors.

Bonne journée

A.


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#18 08-12-2022 10:02:07

Franck D.
Membre
Inscription : 06-12-2022
Messages : 16

Re : Combinatoire sur les séquences de n boules colorées

Pour le  problème qui se pose à moi  oui on peut avoir plus de d boules de la même couleur.  L énoncé originel est

Combien existe-t-il de séquences de n boules colorées choisies parmi r couleurs possédant au moins un sous ensemble de d boules exactement de la même couleur ?

Il n y a pas de contrainte sur la cardinalité des sous ensemble de boules de la même couleur. Simplement on ne retient que ceux de taille d.

Dans l exemple donné n=4 d=2 on ne peut jamais dépasser $d$  car il reste 2 positions de libre seulement si on a mis un sous  ensemble de  2  de boules de la même couleur. Mais dans le cas général oui on peut le dépasser. J aurais  dû le préciser.

Merci encore, si vous avez une nouvelle idée intégrant cette hypothèse  cela m aidera beaucoup.

Dernière modification par Franck D. (08-12-2022 10:22:28)

Hors ligne

#19 08-12-2022 11:43:15

vam
Membre
Inscription : 04-10-2020
Messages : 120

Re : Combinatoire sur les séquences de n boules colorées

Bonjour
ça fait toujours plaisir à ceux qui ont passé du temps à répondre voir ici

Hors ligne

#20 08-12-2022 14:17:17

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,

Finalement, si on formalise ( et c'est calculable ), cela revient à chercher le nombre d'applications de {1,2,, ..n  } (les emplacements de boules) dans
un ensemble à r éléments $\{ c_1, ...,c_r\}$ (les r couleurs), applications telles que pour chaque application une des r couleurs ait exactement d antécédents.

En notant $E_1$ celles pour qui c'est $c_1$ ,  ... $E_i$ celles pour qui c'est $c_i$ , cela revient à calculer   $ card \cup E_i$ .
Sachant que ces ensembles s'intersectent , il faut donc pour éliminer ce qu'on va compter plusieurs fois utiliser le cribe de Poincaré (formule d'inclusion-exclusion) , autrement-dit dénombrer (ce qui est très facile et je prend l'exemple de 3 couleurs RVB pour simplifier mon argumentation :
$Card (E_R) = Card( E_V) = Card ( E_B)$, puis $Card ( E_R \cap E_V) = Card()  = card()$ , par permutations  et enfin $Card (E_R \cap E_V \cap E_B)$.

Chacun de ces dénombrements élémentaires est relativement facile, et il suffit de les injecter dans la formule du crible pour avoir le cardinal de la réunion.

par exemple pour $E_R \cap E_V $ le cardinal sera $\binom{n}{d}\binom{n-d}{d}$ et idem pour les deux autre paires, la couleur B étant affectée automatiquement à tout ce qui reste ( s'il y en a à savoir n >2d).
Pour $Card (E_R) $  ce sera évidemment $\binom{n}{d} 2^{n-d}$ et idem sur les deux autres...

Je vous ai tout fait ou presque, à vous de jouer maintenant, vôtre seule tâche sera de scruter la formule de Poincaré, savoir l'appliquer en utilisant les dénombrements élémentaires qui vous incombent aussi (mais que je vous ai donné sur le cas r = 3 )
Généraliser la formule à des paramètres quelconques pour n,d,r ne devrait pas être hors de portée non plus...

A.

Dernière modification par bridgslam (08-12-2022 14:44:45)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#21 08-12-2022 14:38:08

Zebulor
Membre expert
Inscription : 21-10-2018
Messages : 2 074

Re : Combinatoire sur les séquences de n boules colorées

Bonjour,
@bridgslam : je trouve cette approche par les applications originale .

bridgslam a écrit :

Finalement, si on formalise ( et c'est calculable ), cela revient à chercher le nombre d'applications de {1,2,, ..n  } (les emplacements de boules) dans
un ensemble à r éléments $\{ c_1, ...,c_r\}$ (les r couleurs), applications telles que pour chaque application une des r couleurs ait exactement r antécédents.

Tite question : est ce que ça ne serait pas plutôt $d$ antécédents au lieu de $r$ ? les couleurs n'ont a priori pas de préférence :-)

Dernière modification par Zebulor (08-12-2022 18:18:34)


En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Hors ligne

#22 08-12-2022 14:43:16

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Allez je fais l'effort :

la formule générale - si quelqu'un sait simplifier je suis preneur - merci

voici l'expression

Je note $E_i$ l'ensemble des applications de {1,..,n} dans $\{ c_1,...,c_r \}$ telles que $Card  f^{-1} (c_i) = d$
On doit donc dénombrer le cardinal de leur réunion.

$X = card( \cup_{1 \le i \le r}  E_i ) = \sum_{k=1}^{[n/d]} (-1)^{k+1}\binom{r}{k}\binom{n}{d}\binom{n-d}{d}... \binom{(n-k+1)d}{d} (r-k)^{n-kd}$

qui s'écrit aussi:

$X = card( \cup_{1 \le i \le r}  E_i ) = \sum_{k=1}^{[n/d]} (-1)^{k+1}\binom{r}{k}\frac{n!}{(n-kd)!(d!)^k} (r-k)^{n-kd}$


Normalement celles ou ceux (pour employer le jargon politique) qui vous ont donné ce sujet vous ont forcément évoqué le crible de Poincaré.
Sinon c'est infaisable.

Désolé d'avoir mal interprété la question originale.
@Franck vous pourrez toujours vérifier en préambule que vous aurez 540 avec (6,3,2) en paramètres, si votre programme est juste, je manque de courage là...

Concernant le pseudo-code que je vous avais donné, il faut remplacer la ligne max( R,V,B) == d par celle-ci:
R == d ou V == d ou J == d

D'un autre côté c'est pas négatif, vous aurez deux expressions de dénombrement correspondant à des contraintes un peu différentes.
A.

Dernière modification par bridgslam (08-12-2022 15:56:25)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#23 08-12-2022 14:46:02

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 299

Re : Combinatoire sur les séquences de n boules colorées

Bonjour Zébulor,

Evidemment c'est d , sinon c'est idiot , j'ai corrigé ma coquille - merci à toi.
J'ai aussi rajouté le coefficient binomial que j'ai zappé en relisant mon papier, qui représente le nombre de sélections k à k des divers $E_i$

A.

Dernière modification par bridgslam (08-12-2022 14:55:11)


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#24 08-12-2022 16:55:43

Franck D.
Membre
Inscription : 06-12-2022
Messages : 16

Re : Combinatoire sur les séquences de n boules colorées

Bonjour  @bridgslam

Je regarde et j'essais de comprendre l'explication car je ne suis pas un expert de l'analyse combinatoire. Pour l'instant je n'ai pas sa généralisation malheureusement.

Franck

Dernière modification par Franck D. (08-12-2022 16:57:18)

Hors ligne

#25 08-12-2022 19:23:55

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 947

Re : Combinatoire sur les séquences de n boules colorées

Bonsoir,

Tu as posé ton sujet chez nous le 06/12/2022 à 19 h 08 min 52 s...
A 20 h 37 min 04 s, soit 1 h 28 min 12 s, plus tard Fred t'a demandé des précisions...

Le même jour, à 19 h 32, tu postais le même sujet chez nos confrères : ici.
Pourquoi ?
Scandalisé parce que à 19 h 32, soit 23 min 52 s plus tard, tu n'avais pas encore eu de réponse chez nous ?
Parce que tu t'es dit qu'un seul esclave ne suffisait pas, qu'il te fallait en trouver d'autres ?
Parce que tu t'es dit qu'il te serait ainsi possible de fournir aux autres les réponses obtenues des uns ?

Dans tous les cas, ce sont des procédés consuméristes qui ne devraient pas avoir droit de cité sur des forums : c'est insupportable !
Comment crois-tu qu'aurait réagi ton prof, si 28 min après lui avoir transmis ta question, tu en avais contacté un autre ?
Moi, c'est clair, je l'aurais mal pris : je t'aurais envoyé paître...

Je ne vois d'ailleurs pas pourquoi mes camarades ici continuent encore à te répondre...

A bon entendeur...

      Yoshi
- Modérateur -


Arx Tarpeia Capitoli proxima...

Hors ligne

Pied de page des forums