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

Une partie de ma première réponse

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

Deuxième réponse

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.


Rectificatif

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


















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014