[seqfan] Re: A019298 and interesting identity.

David Seal david.j.seal at gwynmop.com
Wed Sep 13 15:43:21 CEST 2017


> 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.
> ... 
> and consider the following array A starting as:
> 
> { 1, 1,  1,   1,    1,     1,     1,      1,       1,        1,         1,
> ...},
> { 2, 1,  3,   4,    7,    11,    18,     29,      47,       76,       123,
> ...},
> { 3, 2,  6,  11,   26,    57,   129,    289,     650,     1460,      3281,
> ...},
> { 4, 2, 10,  23,   70,   197,   571,   1640,    4726,    13604,     39175,
> ...},
> { 5, 3, 15,  42,  155,   533,  1884,   6604,   23219,    81555,    286555,
> ...},
> { 6, 3, 21,  69,  301,  1223,  5103,  21122,   87677,   363606,   1508401,
> ...},
> { 7, 4, 28, 106,  532,  2494, 11998,  57271,  274132,  1310974,   6271378,
> ...},
> { 8, 4, 36, 154,  876,  4654, 25362, 137155,  743724,  4029310,  21836366,
> ...},
> { 9, 5, 45, 215, 1365,  8105, 49347, 298184, 1806597, 10936124,  66220705,
> ...},
> {10, 5, 55, 290, 2035, 13355, 89848, 599954, 4016683, 26868719, 179784715,
> ...},
> ....
> ...
> It appears, for k >= 3, that column k of A is the sequence {Y_k(n-1)}. (At
> least for columns k = 3..8, respectively, the terms match those in A019298,
> A006325, A244497, A244879, A244873, A244880, respectively.)
> 
> Can anyone prove or disprove this conjecture?

It isn't true, but something closely related looks as though it is. The problem is that A244879 and A244880 are mis-described. Specifically, they are not the numbers of sum-n magic labellings of the prism graphs K_6 = I X C_6 and K_8 = I X C_8, but of the 'looped cycles' LOOP X C_6 and LOOP X C_8, where LOOP is the graph with a single vertex and a single looped edge joining that vertex to itself.

Similarly, A006325 (with an offset of 1) is not the numbers of sum-n magic labellings of K_4 = I X C_4, but of LOOP X C_4. K_4 is the cube graph, and its numbers of sum-n magic labellings are given (again with an offset of 1) in A061927.

I think the problem probably arose from overgeneralising the fact (indicated in my previous post) that for odd k, sum-n magic labellings of I X C_k have matching labels on the outer and inner k-cycles, and so correspond directly with sum-n magic labellings of LOOP X C_k. So for odd k, the sequences for LOOP X C_k and I X C_k are identical - but the same is not true for even k.

R. P. Stanley's "Examples of Magic Labelings" notes https://oeis.org/A002721/a002721.pdf (linked to by many of these sequences) show the k = 5, 6, 7 and 8 cases on pages 5, 27, 21 and 28 respectively. Page 27 does state the fact that the sequences are different for even k, but shows both the LOOP X C_6 and the I X C_6 graphs and only explicitly exhibits one sequence - the I X C_6 sequence is expressed by a formula applied to the LOOP X C_6 sequence.

Anyway, the result is that your conjecture as stated is definitely false for even k, but it does look to be true for odd k, and if you change the definition of Y_k(n) to use LOOP X C_k rather than I X C_k, it looks to be true for all k. That's still a conjecture - I can't offer you a proof or disproof - but at least there's a chance of finding a proof for it!

I will start editing the sequences concerned shortly.

Best regards,

David


More information about the SeqFan mailing list