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

Zebulor · 08-12-2022 20:31:26

Bonsoir,

yoshi a écrit :

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...

@yoshi : J'ai hésité à continuer sur le sujet après la remarque de vam mais l' intérêt des écrits de brigdslam a pris le dessus
Mais sur le fond le terme de "consumériste" me semble approprié au vu des éléments que tu présentes. Et les consuméristes ne semblent jamais satisfaits des réponses qu'on leur donne.

Dernière modification par Zebulor (08-12-2022 22:45:49)

Bernard-maths · 08-12-2022 21:21:05

Bonsoir à tous !

Je suis comme vous, je déplore ce manque de respect de la part des "multi-demandeurs" ... et je suis d'accord pour lutter contre les excès. Merci à Yoshi pour sa vigilance !

Par contre, j'apprécie la diversité des questions qui se posent, et qui nous font travailler, certes, mais qui nous tiennent en "éveil mathématique" ... Ainsi, lorsque les échanges entre "collègues" sont lancés, il peut être agréable de continuer ...

Et comme l'a dit récemment Spike, dans "café" ... ce site est formidable !

Saluons au passage les autres sites qui se dévouent à l'aide ... mathématique, ou autre ...

Cordialement, Bernard-maths

Dernière modification par Bernard-maths (08-12-2022 21:23:54)

bridgslam · 08-12-2022 22:57:52

Bonsoir,

Sinon pour ne pas laisser un doute dans l'esprit des gens intéressés, la formule ( dérivée de Poincaré - merci à lui ) fournit effectivement la valeur de 540 dans le cas de 6 positions de boules, 3 couleurs, et 2 emplacements de même couleur.
Sa décomposition en " +/- " : 720 - 270 + 90 .
Dans ce cas, n est pile divisible par d, il est alors rassurant de constater que dans le dernier terme sommatoire, $0^0 = 1$ . Ce qui m'épate toujours...
C'est cette valeur de 540 que donnait son programme d'après un des posts, qui a donc de très fortes chances d'être juste.

Après,sans vouloir mettre de l'huile sur le feu, le procédé de ratisser à plusieurs râteliers n'est effectivement pas correct du tout.
Je suis contrit d'avoir répondu alors qu'il ne fallait pas, mais le débat était fortement engagé quand je l'ai su.

A quand le site "monomaths" unique sur terre et sur mer, et dans le cosmos, au travers duquel tout un chacun aura la seule possibilité de poster ?
Cela évitera ces désagréments effectivement particulièrement pénibles.

Bonne nuit

A.

bridgslam · 10-12-2022 10:48:06

Bonjour,

Sinon j'ai essayé d'imaginer un codage des configurations qui permettent d' "écarter" entre elles les parties $E_i$ en des parties $F_i$ disjointes entre elles de façon analogue à ce qu'on fait pour faire d'une réunion quelconque une somme disjointe, afin d'effectuer au final une simple somme directe, mais ça ne me saute pas aux yeux.
Le champ d'investigation reste donc encore ouvert pour simplifier les choses.
A.

Dernière modification par bridgslam (10-12-2022 11:28:00)

Franck D. · 10-12-2022 16:57:20

Bonjour @bridgslam,

j'ai fait le test de ta première proposition si on impose que $d$ soit majorant càd aucune couleur n'est répétée plus de d fois. Pour cela j'ai considéré la fonction :
$\sum _{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor } \binom{r}{k} \left(\prod _{m=0}^{k-1} \binom{n-m
d}{d}\right) A(n-k d,(r-k) (d-1))$

je l'ai testé contre un programme brute force qui compte le nombre de profils ayant au d boules de la même couleur et au plus $x\leq d$ boules de la même couleur pour le reste.

Parfois les résultats coïncident effectivement: (P = Programme, F=Formule)
r=3; n=5; d=3 P=F= 120
r=3; n=7;d=4 P=F= 840

mais d'autre fois non
r=3; n=6; d=3 P=420 - F=480
r=3; n=7; d=3 P=1050 - F=1470

Bien sur j'ai pu faire une erreur de programmation mais j'ai vérifié attentivement avant d'envoyer ce post.
Ma conclusion est que c'est formule est partiellement vraie (sans vraie compétence poussée).

Encore merci de l'intérêt porté à mon problème.
Franck
En particulier je ne comprends pas le produit (r-k) (d-1) dans A(n-k d,(r-k) (d-1))

Franck D. · 10-12-2022 17:18:02

Bonjour Yoshi,
étant novice dans les forums de mathématiques, j'ignorais que les questions scientifiques devaient rester captive d'une communauté, dont l'échange est par ailleurs est riche. Clairement, ce protocole s'oppose à ma conception de la science et de ces questions où la diffusion la plus large me semble être le bon procédé et éthique. Pourquoi conserver une question scientifique à quelques uns ? J'en prends cependant note pour mes questions futures sans en partager son esprit.

Je souhaiterai par ailleurs revenir sur les intentions outrancières qui m'ont été prêtées dans votre message, en particulier celle de la recherche d'esclave et l'attitude consumériste. J'ignorais que demander de l'aide à plus compétent que soit relevait soit de l'esclavage, soit de la consommation. Ce n'est pas ma vision qu'elle soit dans les forums ou pour notre système éducatif. En effet, transposé à l'Education, cela signifie que tous les élèves sont des consommateurs car ils souhaitent apprendre de plus compétents qu'eux ? Je passe sur la transposition de l'esclave par respect des enseignants.

Enfin pour votre métaphore sur la réaction du prof face à l'attitude de l'élève posant la même question à un autre prof aussi, je pense que cela dépend de l'état d'esprit du prof. Soit il comprend que la question de l'élève lui importe et le félicite de sa curiosité et de sa détermination à trouver une réponse car le cas est vraisemblablement rare. Si il est un pédagogue accompli, il consulte l'autre prof pour la réponse. Soit il confond savoir et pouvoir (sur les élèves) et le prend effectivement mal car il interprète cet acte comme un reniement de ce pouvoir et de son savoir. Ma réponse est qu'il s'agit d'une question de point de vue et je préfère la première qui indique un prof pédagogue et confiant en son savoir.

En résumé, Je cherchais une réponse à cette question qui m'importe en l'adressant largement comme l'on adresse une question scientifique à l'ensemble d'une communauté, aucun esclave à chercher car il n'y a pas d'obligation de répondre ...

Ma conclusion de cet échange est qu'il apparait que les forums de math se concurrencent en réputation. Est-ce bon pour les mathématiques et la science ?

Je profite enfin de ce message pour encore remercier sincèrement les personnes m'ayant répondu et qui m'ont fait avancer dans une question qui semble demeurer encore ouverte.

Cordialement
Franck

yoshi a écrit :

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 -

Dernière modification par Franck D. (10-12-2022 18:30:03)

bridgslam · 10-12-2022 17:40:39

Bonjour,

De rien Franck, c'est vrai que la question initiale (une fois bien interprétée, ce qui m'a fait défaut au départ ) est aussi plus simple (si on peut dire) que celle qui concerne un d maximum.
Si tu veux mettre à profit cette application assez directe du crible de Poincaré, une autre concerne sur ce même site le dénombrement des mains sans chicane au bridge pas de trou dans une couleur, c'est un peu le même principe, peut-être même un peu plus facile, et un bon exercice d'entrainement à mon avis.

https://www.bibmath.net/forums/viewtopic.php?id=14556

Je me repencherai si j'ai un peu de temps la semaine prochaine sur l'autre question ( d maximum) pour voir si j'ai fait une erreur.

Je suis en ce moment sur des questions de topologie, avec plus ou moins de bonheur, pour ne pas dire de confusion, et je quitte l'analyse combinatoire pour quelque temps, avant d'y revenir prochainement car c'est souvent ludique ( comme ton sujet ).

Pourquoi t'a t-on posé ce sujet ( pas élémentaire) , tu es dans un cursus informatique ou mathématique ?
Désolé pour l'échauffement sur le multi-postage, c'est vrai que ce n'est pas du tout de mise.

Bonne soirée

A.

Franck D. · 10-12-2022 18:28:59

bonjour bridgslam,
je vais creuser le crible de point carré. Mon cursus est celui d'un informaticien avec des enclaves théoriques, donc vers les maths.

Ce sujet s'est posé à partir d'une question concernant la formation de communautés dans un graphe càd une partition des sommets d'un graphe, où chaque sommet possède une propriété assimilée à une couleur.

La question où d est un maximum m'intéresse aussi à présent cad on cherche un profil ayant $d$ éléments de la même couleur et aucun groupement de même couleur le dépasse.

Dans ta solution je bloque malheureusement sur l'arrangement et plus spécifiquement sur le produit (r-k)(d-1) que j'ai du mal à interpréter couplé à l'injection.

Franck

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

bridgslam · 10-12-2022 19:57:46

Bonsoir,

Ok j'essaierai de faire le point lundi en revoyant aussi "ma copie" et si je confirme j'essaierai de t'en faire part clairement (autant que possible).
Une erreur est toujours possible sur les dénombrements délicats.
Par-contre sur le problème initial la formule est juste.
Je ne pensais pas non plus que c'était couplé avec une question de graphe.

Sinon il s'agit de Poincaré Henri, grand mathématicien français, et qui a touché avec grand bonheur à d'autres sciences ( physique notamment).

Bonne soirée

A.

bridgslam · 11-12-2022 12:07:39

Bonjour,

J'ai fait un dénombrement direct pour le dénombrement avec d max dans le cas n=6, d=r=3.
Je procède en comptant d'abord les configurations comportant où une seule couleur réalise le maximum d.

Il y en a $3\binom{6}{3} . 6 $ , en effet une couleur parmi 3 étant choisie , il faut multiplier par le nombre de façons de choisir 3 positions parmi 6, et multiplier
par les manières d'affecter une des deux couleurs restantes à l'une des 3 positions vacantes, et deux à la dernière positions.

Il faut rajouter les configurations où on a deux couleurs de 3, il y en a $3\binom{6}{3}$.

En tout ça fait bien 420 sans faire tourner de programme, le vôtre donne donc le bon résultat en comparant à ma valeur.

Le souci dans les calculs d'arrangements où on s'octroie des jetons de couleurs est que je compte plusieurs fois les mêmes configurations ( les permutations au sein d'une même série de jetons de couleur commune étant équivalents ).

Il est possible que le dénombrement dans toute sa généralité fasse appel à une double somme alternée ( Poincaré pour un lot d'ensembles $E_i$ à définir, et rebelote Poincaré pour chacun des $E_i $ qui sont en fait chacun des réunions de parties $F_j$. Mais ça devient un peu complexe.
Ce dénombrement n'est vraiment pas simple en toute généralité, mais pour des valeurs "raisonnables" des paramètres vous pouvez toujours faire des calculs directs comme celui ci-dessus, et comparer aux résultats de vôtre programme ( ou dans l'ordre inverse...).
Une autre voie est peut-être une relation de récurrence en faisant varier par pas les paramètres, ce qui ne garantit pas une formule générale.

Après, il y a peut-être aussi une astuce en codant le problème différemment ou avec l'emploi d'une fonction auxiliaire simple.
J'y réfléchis, en tout cas c'est très intéressant.

A.

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

Franck D. · 11-12-2022 16:42:34

Bonjour @bridgslam,

La solution que j'ai trouvée à ce problème est finalement est la suivante. Le début est celui déjà établi qui évalue les différentes configurations à $d$ boules de même couleur, soit pour $k$ sous ensembles de boules de même couleurs: $\binom{r}{k} $ combinaison de couleur. Pour dénombrer les configurations intuitivement, je me fonde sur le dénombrement des permutations avec répétitions . En considérant que $n= d k$ on aurait donc $\frac{n!}{d!^k}$ permutations des séquences de $d$ boules de même couleurs, chaque séquence étant d'une couleur différente par définition.

Ceci sera complété ensuite par le dénombrement des boules restantes quand $n \neq d k$. On considère qu'il reste $n- kd$ boules dont il faut dénombrer les variations en sachant qu'aucun sous ensemble de même couleur est de taille $d$. Il reste $r-k$ couleurs disponibles définies de $1$ à $r-k$ pour simplifier. Une combinaison de boules restantes est définie par le profil (multiensemble) $(x_1,\cdots,x_{r-k})$ où $x_i$ est le nombre de boules de couleur $i$. Cette combinaison vérifie $ P= \sum _{i=1}^{r-k} x_i=n-k d \land x_i \neq d$.

Toutes permutations d'une telle combinaison sont aussi à dénombrer. Cette configuration répétant les couleurs, on a donc: $\frac{n-k d!}{ x_1! x_2! \cdots x_{r-k}!}$ permutations possibles. On énumèrera donc toutes les différentes combinaisons vérifiant $P$ dont on sommera les permutations. Ceci donne finalement la formule suivante:

$ \sum _{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor } \binom{r}{k}\frac{n!}{d!^k} \sum _{p \in \Lambda_k}
\frac{1}{\prod _{j \in p} j!} $

avec
$\Lambda_k = \{(x_1,\cdots,x_{r-k}) | \sum _{i=1}^{r-k} x_i=n-k d \land x_i \neq d\}$

Si on veut définir $d$ comme un borne supérieure, la condition sur $x_i$ devient $x_i<d$ au lieu de $x_i \neq d$, soit

$\Lambda_k = \{(x_1,\cdots,x_{r-k}) | \sum _{i=1}^{r-k} x_i=n-k d \land x_i < d\}$.

J'ai vérifié empiriquement sa correction et j'atteste de sa véracité (au moins sur les 100 exemples testés :-) )

Le problème est que l'énumération exhaustive de toutes les sommes vérifiant $\sum _{i=1}^{r-k} x_i=n-k d \land x_i \neq d$ est exponentielle et donc malheureusement la formule peut être calculée uniquement pour $n,r,d$ petit. A travailler encore de ce fait. Peut être existe-t-il une formulation alternative évitant cette limitation ?

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

bridgslam · 11-12-2022 17:39:33

Bonsoir,

Une autre façon de procéder, quitte à utiliser l'informatique (sans difficulté) consiste à considérer les nombres $X_n^r (d)$ qui représentent les configurations pour n positions, r couleurs, et max = d.
On peut obtenir toutes les valeurs en partant de d = 1 et une formule simple pour passer au suivant etc.

La relation de passage tient au fait que si on a une configuration avec c couleurs pleines (à d) exactement, on peut facilement voir que pour les positions et couleurs restantes, cela revient à prendre le même problème avec d-1, d-2 ,... 1 , et ces parties sont bien disjointes.

Alors $X_n^r (1) = A_r^n$ éventuellement nul si r < n.

Puis $X_n^r (2) = \binom{r}{1}\binom{n}{2} X_{n-2}^{r-1}(1) + \binom{r}{2}\binom{n}{2}\binom{n-2}{2} X_{n-4}^{r-2}(1) + ... $

Ensuite on passe à d=3 sans difficulté excessive( on doit juste descendre avec X(2) et X(1) ) avec le même principe, puisque une fois les groupes de 3 choisis,
les autres seront soit à un max de 2, soit un max de 1.

Informatiquement c'est dans la poche, et permet de calculer par incrément de 1 sur d, de proche en proche.

C'est un type de calcul, en quelque sorte par récurrence forte, que l'on retrouve aussi par exemple autour des questions touchant aux nombres de Catalan, par exemple.

A.

Dernière modification par bridgslam (11-12-2022 17:49:09)

Franck D. · 11-12-2022 18:24:29

Quelle est la formulation générale de $X_n^r(d)$ ? je n'arrive pas à l'inférer des exemples. Merci
Franck

bridgslam · 11-12-2022 18:32:23

Bonsoir,

Je n'ai pas de formule générale selon cette approche, on déduit juste la valeur pour d à partir de celles calculées pour d-1, d-2, ...,1.
X(2) se calcule à partir de X(1), X(3) à partir de X(2) et X(1), etc.

Un système en poupées gigognes mais qui est peut-être plus simple à utiliser informatiquement qu'un formule générale.

A.

Franck D. · 11-12-2022 21:13:00

D accord mais connais tu la définition récursive ?

bridgslam · 12-12-2022 09:56:20

Bonjour,

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

On calcule ainsi de proche en proche tous les nombres fonctions de (d).

Bonne journée
A.

Franck D. · 12-12-2022 18:11:43

Bonjour bridgslam,

j'ai vérifié (programmé) aujourd'hui ta proposition concernant le crible de Poincaré, sur le problème en n’imposant pas de contrainte de borne sur $d$, soit:

$\sum _{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor } (-1)^{k-1} \binom{r}{k} \left(\prod _{i=0}^{k-1} \binom{n-i d}{d}\right)
(r-k)^{n-k d}$

La formule est juste aussi ! :-)

Elle donne une solution alternativement à ce problème dont la complexité du calcul est polynomiale et évolue quadratiquement $\mathcal{O}(n) =\left(\frac{n}{d}\right)^2$.

Merci encore de ton intérêt, de tes réponses, et de m avoir fait découvrir le crible de Poincaré qui est un théorème puissant pour la combinatoire.

Franck

Dernière modification par Franck D. (13-12-2022 00:05:38)

bridgslam · 13-12-2022 09:26:46

Bonjour,

De rien, bonne chance sur tes futurs problèmes combinatoires, il y a pleins d' horizons splendides à découvrir.

Bonne journée
A.

bridgslam · 16-12-2022 09:28:40

Bonjour,

Sinon pour le problème avec max = d à atteindre dans chaque configuration de n boules et r couleurs disponibles, on a le résultat suivant, en procédant par différence, à savoir qu'on soustrait des configurations d'au plus d boules de mêmes couleurs celles d'au plus d-1 boules de mêmes couleurs:

$\mathcal{C} = \{ (x_1,...,x_r) \in \mathbb{N}^r | \sum_i x_i = n , max_{1 \le i \le r} (x_i) = d \}$ et en notant $!c = \prod_{i=1}^r x_i ! $

alors le dénombrement cherché est $\large n! \sum_{c \in \mathcal{C} } \frac {1}{ !c }$.

L'expression est simple car différence de deux polynômes en r variables en (1, 1, ..., 1) , incluant tous les deux la valeur $r^n$ qui s'élimine donc par différence.

Ainsi dans le cas n = 6, d = r = 3 on a 6 3-uplets distincts (1,2,3) et 3 3-uplets distincts (0, 3 ,3 ) ce qui nous laisse avec la valeur:

$ 6! ( \frac{6}{1!2!3!} + \frac{3}{0!3!3!} ) = 7!/12 = 420 $ possibilités.

Avec 4 couleurs (r) , 6 positions (n) , et un max de 3 couleurs identiques à chaque configurations (d) , sauf erreur cela donne 2040 configurations.

Si r=3; n=7; d=3 la valeur 1050 évaluée par Franck est confirmée aussi ( les triplets sont de type (1,3,3) au nombre de 3 ou de type (2,2,3) au nombre de 3
ce qui donne 7!( 3/(3!3!) + 3/(2!2!3!) ) = 1050.

Informatiquement l'ensemble $\mathcal{C} $ est relativement rapide à parcourir, je pense.

A.

Dernière modification par bridgslam (16-12-2022 10:22:19)

Forum de mathématiques - Bibm@th.net

#26 08-12-2022 20:31:26

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

#27 08-12-2022 21:21:05

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

#28 08-12-2022 22:57:52

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

#29 10-12-2022 10:48:06

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

#30 10-12-2022 16:57:20

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

#31 10-12-2022 17:18:02

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

#32 10-12-2022 17:40:39

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

#33 10-12-2022 18:28:59

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

#34 10-12-2022 19:57:46

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

#35 11-12-2022 12:07:39

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

#36 11-12-2022 16:42:34

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

#37 11-12-2022 17:39:33

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

#38 11-12-2022 18:24:29

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

#39 11-12-2022 18:32:23

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

#40 11-12-2022 21:13:00

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

#41 12-12-2022 09:56:20

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

#42 12-12-2022 18:11:43

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

#43 13-12-2022 09:26:46

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

#44 16-12-2022 09:28:40

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

Pied de page des forums