Nombre de carrés magiques (sommes lignes et colonnes égales à 2)

Description

fr.sci.maths en juillet 2001

> Trouver le nombre de carrés magiques de taille n à nombres entiers et de
> somme 2 (il y a donc soit des 0 des 1 ou de 2).
> Pas de sommes diagonales, uniquement horizontalement et verticalement

1,1,3,21,282,6210,202410,...
voir la suite A000681 de l'encyclopédie de Sloane des suites
d'entiers :
http://www.research.att.com/~njas/sequences/index2.html
(n X n matrices with nonnegative entries and every row and column
sum
2.)

Si p est le nombre de 2 de la matrice n x n, le nombre de manières
de les placer est (appelons le d(n, p))
d(n, p) = (C_n^p)^2  * p!

(C_n^p est le nombre de combinaisons de p éléments pris parmi n,
C_n^p = n!/(p! * (n-p)!))

il y a C_n^p choix des lignes, des colonnes et p! choix des 
matrices p x p (matrices ayant un et un seul nombre 2 par ligne, 
des 0 ailleurs)

On a donc : 
a(n) = sum(p =0...n, d(n, p) * u(n-p)) où u(k) est le nombre
de matrices k x k ayant deux 1 par ligne, par colonne, des 0
ailleurs,
voir A001499.

---------------- 
pour le calcul de u(n), on regarde la 1ère colonne,
on prend l'un des 1, il lui correspond
un autre 1 sur la même ligne dans une seconde colonne où se trouve
un second 1, ... jusqu'à revenir à l'élément 1 de départ,
on détermine ainsi une sous matrice de p lignes et colonnes
qui est une permutation des colonnes et des lignes 2...p
de la matrice suivante
11000000...0
01100000...0
00110000...0
..      ....
00000000  11
10000000  01
il y a C_n^p * C_(n-1)^(p-1) manières de placer cette sous_matrice
dans la matrice n x n (la première colonne est imposée)
et p(p-1)/2 * (p-1)*(p-2)*(p-2)*(p-3)*(p-3)*...*1
= p/2 * (p-1)! manières de la remplir
 
d'où u(n) = sum(p=0..n, C_n^p *C_(n-1)^(p-1)*p/2 *((p-1)!)^2 *
u(n-p)
 
programme GP/PARI :  (les indices des vecteurs partent de 1 et pas
-------------------    de 0, d'où les t[n+1] et a[n+1])
u = vector(20);
u[1]=1;
for(n=2,10, \
   (for(p=2,n, \
          u[n+1] = u[n+1] + \
           n!/(p!*(n-p)!) * (n-1)!/((p-1)!*(n-p)!)* \
           p * (((p-1)!)^2)/2 *u[n-p+1])))
for(i=0,10,print(u[i+1]) )
  
a=vector(20);
for(n=0,10, ( \
       for(p=0,n, a[n+1] = a[n+1] + \
                   (n!/(p!*(n-p)!))^2*p!*u[n-p+1])))
for(i=0,10,print(a[i+1]))
 
Résultats :
-----------
[jp@localhost sum2]$ cat un.gp | gp -q
1
0
1
6
90
2040
67950
3110940
187530840
14398171200
1371785398200
1
1
3
21
282
6210
202410
9135630
545007960
41514583320
3930730108200
 
Ce ne sont pas les expressions données dans l'encyclopédie de
Sloane, 
mais ce sont des solutions tout de même ; et on peut chercher à
les simplifier
 
J-P.

> et p(p-1)/2 * (p-1)*(p-2)*(p-2)*(p-3)*(p-3)*...*1
> = p/2 * (p-1)! manières de la remplir
>

la 1ère ligne est exacte, pas la seconde qui s'écrit :
= p/2 * ((p-1)!)^2 manières de la remplir

c'est d'ailleurs ce qui est utilisé dans le programme :

u[n+1] = u[n+1] + \
n!/(p!*(n-p)!) * (n-1)!/((p-1)!*(n-p)!)* \
p * (((p-1)!)^2)/2 *u[n-p+1])))
^^^^^^^^^^^^^^^^^^

J-P.

Compléments, documents, références, liens

n X n matrices with nonnegative entries and every row and column sum 2.
On-Line Encyclopedia of Integer Sequences!
Generating Functions   Simon Plouffe
The book "generatingfunctionology"   Herbert Wilf (Mathematics Books Available for Free Downloading).