Enumération de matrices

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Sve@r

Bonjour à tous - J'ai trouvé ce problème sur un fofo de programmation

Trouver le nombre de matrices carrées binaires (composées uniquement de 0 et 1) de taille "n" où la somme de chaque ligne et chaque colonne est égale à un nombre "k"

Exemple: nombre de matrices de tailles 3 où la somme de chaque ligne/colonne est égale à 2 => réponse 6
0 1 1
1 0 1
1 1 0

0 1 1
1 1 0
1 0 1

1 0 1
0 1 1
1 1 0

1 0 1
1 1 0
0 1 1

1 1 0
0 1 1
1 0 1

1 1 0
1 0 1
0 1 1

D'un point de vue programmation, j'ai résolu le problème. Je pars de
0 1 1
0 1 1
0 1 1
Puis j'incrémente chaque ligne de 1 en 1 et je m'arrête en final ici
1 1 0
1 1 0
1 1 0
En ayant compté entre les deux chaque matrice qui convient

Maintenant je m'y intéresse d'un point de vue mathématique (trouver la formule qui donne directement le bon résultat) et là je sèche. Je suis resté bloqué sur la première ligne où j'arrive à trouver que pour distribuer "k" jetons parmi "n" emplacement il y a comb(k, n) possibilités. Mais ensuite il faut placer les lignes suivantes...

Voici le fofo où j'ai trouvé le problème: http://www.developpez.net/forums/sh...ad.php?t=481611

Merci à tous


Posted by: scelerat

Bon, deja pour k=n, c'est 1. Pour k=n-1, c'est facile, il y a n lignes possibles et on ne peut pas mettre deux fois la meme, donc c'est n!, le nombre d'arrangements de ces lignes. C'est aussi la meme chose pour k et n-k, en echangeant les 1 et les 0.
Je continue a reflechir.


Posted by: Sve@r

Citation:
Posté par scelerat
Bon, deja pour k=n, c'est 1. Pour k=n-1, c'est facile, il y a n lignes possibles et on ne peut pas mettre deux fois la meme, donc c'est n!, le nombre d'arrangements de ces lignes. C'est aussi la meme chose pour k et n-k, en echangeant les 1 et les 0.
Je continue a reflechir.


Joli. J'étais même pas arrivé au fait que pour k=n - 1 la solution était n! mais effectivement, mon programme me donne ça.

Ainsi il faut partir sur des évaluations de "k" au cas par cas ???

Le fait que ce soit le même résultat pour "n - 1" et "n - k" (et aussi pour 0 et n) me font penser à un échelonnement qui pourrait ressembler au triangle de Pascal...

Bon, voici pour aider quelques valeurs trouvées

Pour n=5 les valeurs k=0, 1, 4 ou 5 sont connues. et pour k=2 ou 3 on a 2040 matrices

Pour n=6
k=2 ou k=4 => 67950
k=3 => 297200

Pour n=7
k=2 ou 5 => 3110940
k=3 ou 4 => 68938800

Pour n=8
k=2 ou 6 => 187530840 (c'est marrant, ce chiffre me dit quelque chose => je l'ai déjà vu ailleurs)
k=3 ou 5 => 24046189440
k=4 => 116963796250


Posted by: scelerat

Citation:
Posté par Sve@r
Bon, voici pour aider quelques valeurs trouvées

Pour n=5 les valeurs k=0, 1, 4 ou 5 sont connues. et pour k=2 ou 3 on a 2040 matrices


Pour k=2, il me semble qu'on peut dire qu'on obtient toutes les matrices en faisant la somme de deux matrices k=1 n'ayant aucune ligne (ou colonne) identique. Quand on a choisi la premiere des deux, le nombre de choix pour l'autre est celui des derangements de la liste de ses lignes, soitd_n=n! \sum_0^n \frac{(-1)^i}{i!} .
On aurait donc n! \frac{d_n}{2} puisque chaque matrice k=1 est comptee 2 fois, mais de tete j'arrivais a 2640. pour n=5, k=2










-