Dénombrement et modulo

[beagle]

Soit n poissons indiscernables à mettre dans k aquariums dits cernables eux car numérotés de 1 à k, avec n supérieur à k.
Toutes les possibilités de "rangements" sont possibles, la seule chose étant de ne pas laisser de poissons sans aquarium, pauvres bètes.
On appelle D(n,k) le nombre de possibilités de classer ces n poissons dans k aquariums.

La question est simple, trouver: D(n,k) modulo k.

[Ben314]

La valeur de D(n,k) n'est pas super dure à obtenir (c'est un grand classique) :

Si est un nombre premier, c'est fastoche :
Si n'est pas premier... je sais pas trop, mais on doit pouvoir arriver à dire des trucs en utilisant la formule qui donne l'exposant d'un nombre premier p dans n! (la "valuation p-adique")
A voir...

[beagle]

Je ne connaissais pas la formule ,
j'avais soupçonné Chan d'utiliser une formule comme cela mais je ne savais pas que c'était un classique:
http://www.maths-forum.com/5-godets-15-pions-148210.php

alors j'ai fait l'exo à la mano, et pendant ces longs moments (pas trop quand mème),
j'ai pensé à généraliser,
mais voui j'ai été un peu vite à la généralisation, cela ne marche que pour k premier, le 1 ou 0.

Avec k premier mon D(n,k) est la somme d'une foultitude de trucs qui sont du C(i, k)x...,
quand n pas multiple de k, alors tous les C (i,k) sont des multiples de k
quand n multiple de k alors on a en plus UNE solution en C(k,k)=1
c'est le cas de l'exo cité en ref: 3+3+3+3+3 est C(5,5)

pour l'exo de hammana,
on calcule le nombre de combi où le max est 3,4,5,6,7,8,9,10,11,12,13,14,15
3(1), 4(120),5(530), 6(800), 7 (735), 8(600),9(420), 10(320), 11(175),12(100),13(50),14(20),15(5).
c'est en fait assez vite fait,
mais on se lasse un peu , alors on pense à l'exo suivant,

un peu vite, scusez pour quand c'est pas premier,
c'est Ben314 qui le fait...

[Ben314]

La formule donnant le D(n,k), il y a des tas de façon de la trouver, dont une est particulièrement simple (c'est resté gravé dans ma mémoire vu que la première fois que je suis tombé là dessus, j'ai aussi noirci beaucoup de papier avant de me rendre compte que tout se simplifiait "miraculeusement")

En fait le problème revient à trouver le nombre de k-uplets d'entiers naturels tels que la somme fasse n ( est le nombre de poissons dans l'aquarium 1, etc...)
Une façon (super astucieuse) de voir le truc, c'est, sur une ligne d'une feuille de papier quadrillé, de laisser cases blanches puis de noircir la suivante, puis de laisser cases blanches puis de noircir la suivante, etc...
Au total, tu as utilisé une longueur de cases et tu en as noirci .
Il reste à se convaincre qu'il y a bijection entre les k-uplets de somme n et les lignes de n+k-1 cases dont k-1 sont noircies pour en déduire que le nombre de solution, ben c'est le nombre de façon de noircir k-1 cases parmi n+k-1.

[beagle]

Je regarderai cela, merci Ben.
avant de faire le bourrin j'ai un peu essayé de trouvé comment ruser, mais pas abouti
et les calculs à la mano était simples en fait ...

en pédagogie c'est l'objectif obstacle je crois , un truc du genre,
pour faire changer la stratégie tu mets le truc de l'ancienne stratégie en échec car trop chi...t,
obligeant l'élève à trouver une nouvelle stratégie.

Bon ceci dit j'aurais pu me prendre l'obstacle dans la tronche , je crois bien, et arréter là.

[MMu]

Avec pions dans la première case il y a rangements possibles pour les autres pions.

avec les conditions initiales .
La solution est évidemment unique et il suffit de vérifier que satisfait.. :zen: