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