[seqfan] Re: A019298 and interesting identity.

[David Seal]

> For m >= 1, denote by S_m(n) the number of m X m symmetric matrices of
> nonnegative integers in which every row (and column) sums to n and, for k
> >= 3, let Y_k(n) denote the number of magic labelings (in nonnegative
> integers) of the prism graph Y_k (or I X C_k, depending on who defines it)
> with magic sum n.
> 
> Using Macmahan's omega operators in the "Omega" package for Mathematica
> (authored by Axel Riese), it was not hard to prove that
> 
> (1)  S_3(n) = Y_3(n), n = 0,1,2,...,
> 
> by showing that the sequences {S_3(n)} and {Y_3(n)} have the same
> generating function (see https://oeis.org/A019298). The graph Y_3 is the
> one on the top left in the image: http://mathworld.wolfram.com/
> images/eps-gif/PrismGraph_1000.gif.
> 
> Is there another argument, possibly geometric, that explains why (1) is
> true?

Yes. Suppose the magic labelling of Y_3 is:

               *
              /|\
             / | \
            / a|  \
           /   |   \
          /    *    \
         /b   / \   c\
        /   g/   \h   \
       /    /     \    \
      /   _*-------*_   \
     /  _-     i     -_  \
    / _-d             f-_ \
   /_-         e         -_\
  *-------------------------*

The fact that the labels on the edges incident at each vertex add up to n tells us that:

  a+b+c = n
  b+d+e = n
  c+e+f = n
  a+g+h = n
  d+g+i = n
  f+h+i = n

Negating some of those and adding, we get:

  +a +b +c                   =  n
     +b    +d +e             =  n
        -c    -e -f          = -n
  -a                -g -h    = -n
           -d       -g    -i = -n
                 +f    +h +i =  n
  -------------------------------
     2b            -2g       =  0

So g=b, and by symmetrical arguments, h=c and i=e. Therefore all magic labellings of Y_3 are of the form:

               *
              /|\
             / | \
            / a|  \
           /   |   \
          /    *    \
         /b   / \   c\
        /   b/   \c   \
       /    /     \    \
      /   _*-------*_   \
     /  _-     e     -_  \
    / _-d             f-_ \
   /_-         e         -_\
  *-------------------------*

But now the correspondence with symmetric matrices:

  ( a b c )
  ( b d e )
  ( c e f )

whose rows and columns add up to n is obvious.

A similar argument shows that magic labellings of Y_k have the same labels on the outer and inner k-cycles if n is odd, but it's easy to show that the same is not true for k even: for magic sum 2, for instance, label every inner k-cycle edge with 1 and alternate outer k-cycle edges with 2, and the remaining edges with 0. And for k odd, once we've established those label identities, we have 2k labels with k subsets adding up to n, while for the symmetric matrices we have k(k+1)/2 entries with k subsets adding up to n. So if k > 3, there are more degrees of freedom in the symmetric matrices than in the magic labelling, and so no reason to expect any correspondence between them. So for separate reasons, the analogue of the above argument breaks down for even k and for odd k > 3.

Best regards,

David