Dénombrement pour n-uplet

[mlelorra]

Bonjour

Décidément, les années ne m'aident pas... après une question de dérivés et gradient, me voici avec un dénombrement que je n'arrive pas à faire sur un n-uplet

J'aimerais trouver le nombre de combinaisons possibles d'un n-uplet respectant les consignes suivantes
- le n-uplet est constitué n variables de (x1, x2, ..., xn)
- x1, x2, ..., xn sont entiers multiples de k
- les n variables sont liées par la loi min <= x1 <= x2 <= ... <= xn-1 <= xn <= max

J'aimerais arriver à déterminer ce nombre de combinaisons avec une formule du type
nombre de combinaison = f(n, max, min, k)

Je n'arrive pas à trouver une fonction exacte pour tous les cas triviaux que je pose et je n'ai encore moins de démonstration qui puisse me garantir qu'une telle fonction soit bonne
--> qqn pourrait-il SVP m'aider ?

Merci

[Anonyme]

@mlelorra

Pas évident comme exo !!

Moi je commencerais par étudier le cas le plus simple :

1) C'est à dire le cas où les x1 x2 x3 ... xn sont tous distincts
et je calculerais : Combien a-t-on de combinaisons ?


PUIS
2) Après j'étudierais le cas où et tel que
et je calculerais : Combien a-t-on de combinaisons ?


...etc...


Désolé : je ne "vois" pas d'autre méthode...

[mlelorra]

@mlelorra

Pas évident comme exo !!

Moi je commencerais par étudier le cas le plus simple :

1) C'est à dire le cas où les x1 x2 x3 ... xn sont tous distincts
et je calculerais : Combien a-t-on de combinaisons ?


PUIS
2) Après j'étudierais le cas où et tel que
et je calculerais : Combien a-t-on de combinaisons ?


...etc...


Désolé : je ne "vois" pas d'autre méthode...

Argh c'est la version empirique que je n'arrive pas à boucler...

[nodjim]

Il y a un raisonnement particulier à avoir pour trouver le résultat. Perso, la 1ère fois que j'ai eu à faire ça, j'ai séché....

[mlelorra]

Il y a un raisonnement particulier à avoir pour trouver le résultat. Perso, la 1ère fois que j'ai eu à faire ça, j'ai séché....

merci Nodjim... mais pourriez vous SVP me dire quel est ce raisonnement particulier ? là, ça fait 4h que je sèche sur la question...

[Anonyme]

Récurrence ?

[nodjim]

Bon déja il faut cerner ce que les contraintes "max,min, mutiples de k" imposent. A partir de ces 3 données, combien d'emplacements possibles sont ils disponibles ?
Par exemple, entre 15 et 48, combien y a t'il de multiples de 7 ? En déduire une formule générale.

[mlelorra]

Bon déja il faut cerner ce que les contraintes "max,min, mutiples de k" imposent. A partir de ces 3 données, combien d'emplacements possibles sont ils disponibles ?
Par exemple, entre 15 et 48, combien y a t'il de multiples de 7 ? En déduire une formule générale.

j'avais commencé cette piste en tentant un truc du genre "partie entière de [(max - min) / k]" ce qui donnait 4 pour le cas d'exemple

Extrapolant là dessus (même si ce n'est pas exact totalement), il me reste cette valeur et le n... de là, j'ai fait des dizaines de combinaison "à la main" pour trouver une règle ... mais je m'y suis perdu


ps: j'ai mis que ce n'est pas exact totalement car si on prend les exemples "combien de multiples de 7 entre 7 et 14 ?" j'obtiendrais 1 avec ma formule alors que je dois obtenir 2...

[nodjim]

Attention, puisqu'entre 21 et 49, (49-21)=28/7=4 mais il y a 5 possiblités (21,28,35,42,49). Donc à affiner.
Maintenant, il faut bien comprendre que la différence avec les combinaisons sans répétitions, c'est que ça offre des emplacements supplémentaires fictifs.
Par exemple , pour 5 emplacements, avec n=3, on a
1 1 1
1 1 2
etc..
Ce 1 1 1 possible, c'est comme si les 2 as qui suivent le 1er as étaient des emplacements fictifs possibles. C'est à dire qu'au lieu d'avoir 5 emplacements, c'est comme si tu en avais 2 de plus, c'est à dire 7.
Réfléchis à ça et vérifie si ça marche avec ce que tu as pu faire à la main.

[mlelorra]

Attention, puisqu'entre 21 et 49, (49-21)=28/7=4 mais il y a 5 possiblités (21,28,35,42,49). Donc à affiner.
Maintenant, il faut bien comprendre que la différence avec les combinaisons sans répétitions, c'est que ça offre des emplacements supplémentaires fictifs.
Par exemple , pour 5 emplacements, avec n=3, on a
1 1 1
1 1 2
etc..
Ce 1 1 1 possible, c'est comme si les 2 as qui suivent le 1er as étaient des emplacements fictifs possibles. C'est à dire qu'au lieu d'avoir 5 emplacements, c'est comme si tu en avais 2 de plus, c'est à dire 7.
Réfléchis à ça et vérifie si ça marche avec ce que tu as pu faire à la main.

J'ai bien vu pour l'affinage nécessaire sur la fonction liant les min / max et les possibilités.

Quoiqu'il en soit, je suis désolé pour la suite mais le coup des emplacements fictifs me dépassent... :marteau:

[nodjim]

Si ça peut t'aider, un extrait de Wiki sur les combis à répétition.
Problème :

Supposons avoir un ensemble de n éléments.

Combien de sous-ensembles de k éléments peut-on construire si l’on ne tient pas compte de l’ordre, et que l’on autorise les répétitions ?

Exemple :

Prenons n = 5 et k = 3 ; { 1 ; 2 ; 3 ; 4 ; 5 } est l’ensemble des 5 éléments.

Écrivons tous les sous-ensembles non ordonnés de trois éléments de { 1 ; 2 ; 3 ; 4 ; 5 } :

111 122 133 144 155 222 233 244 255 333 344 355 444 455 555
112 123 134 145 223 234 245 334 345 445
113 124 135 224 235 335
114 125 225
115

Pour compter ces sous-ensembles (il y en a 35 dans notre exemple !), on imagine qu’ils sont formés de combinaisons où les répétitions sont absentes.

Il faut donc trouver un moyen de transformer cette écriture…

Pour cela, on augmente de : 1 unité le chiffre des 2èmes colonnes, 2 unités le chiffre des 3èmes colonnes, … , k-1 unités le chiffre des kèmes colonnes.

123 134 145 156 167 234 245 256 267 345 356 367 456 467 567
124 135 146 157 235 246 257 346 357 457
125 136 147 236 247 347
126 137 237
127

Il est évident que le nombre d’éléments des deux listes est le même.

Mais la nature même des éléments a changé, puisque l’on utilise les chiffres allant de 1 à 7, et non plus de 1 à 5 comme au départ.

Notre collection de n objets est donc agrandie à n+k-1 objets.

Le nombre de combinaisons avec répétition de "k" objets pris parmi "n" est donc égale au nombre de combinaisons sans répétition de "k" objets pris parmi "n + k-1".

Ce nombre est :

[mlelorra]

Ca doit être la fatigue parce que jusqu'à "Il faut donc trouver un moyen de transformer cette écriture…", je comprends mais là suite...

pourquoi diable faut-il "augmenter" et pourquoi de 1 unité par colonne ? quel est le lien avec le 35 (ce que je cherche à déterminer en fonction de n et k) ?...

Encore désolé d'être aussi mauvais...

[mlelorra]

Ca doit être la fatigue parce que jusqu'à "Il faut donc trouver un moyen de transformer cette écriture…", je comprends mais là suite...

pourquoi diable faut-il "augmenter" et pourquoi de 1 unité par colonne ? quel est le lien avec le 35 (ce que je cherche à déterminer en fonction de n et k) ?...

Encore désolé d'être aussi mauvais...

J'ai trouvé l'article de Wikipédia sur les Combinaison avec répétition

Empiriquement la formule donné avec les factorielles semble tomber sur les mêmes résultats que ce que j'ai dénombré "à la main"... je vais donc m'en contenter !

Il me "suffit" maintenant d'arriver à mettre la bonne fonction liant le min, max et k (c'est pas gagné vu mon faible niveau...)

En tout cas, merci pour votre aide !