A237426 - OEIS

%I #67 Jul 25 2022 14:55:31

%S 1,3,12,28,48,240,944,5344,23408,133808,751008,5222768,37898776,

%T 292271304,2346665448,20499852656

%N Number of distinct edge-magic total labelings of path P_n.

%H Mukkai S. Krishnamoorthy, Allen Lavoie, Ali Dasdan, and Bharath Santosh, <a href="http://arxiv.org/abs/1402.2878">Number of unique Edge-magic total labelings on Path P_n</a>, arXiv:1402.2878 [math.CO], 2014.

%e From _Gheorghe Coserea_, May 18 2018: (Start)

%e For n=2 the a(2)=12 solutions are:

%e [1, 4, 5, 2, 3] [2, 5, 1, 3, 4]

%e [1, 4, 5, 3, 2] [2, 5, 1, 4, 3]

%e [1, 5, 3, 2, 4] [3, 2, 5, 1, 4]

%e [1, 5, 3, 4, 2] [3, 4, 1, 2, 5]

%e [2, 3, 5, 1, 4] [4, 2, 3, 1, 5]

%e [2, 4, 3, 1, 5] [4, 3, 1, 2, 5]

%e The solution [1, 4, 5, 2, 3] is an encoding of the following labeling of P_2:

%e 1  4  5  2  3

%e o-----o-----o

%e Vertices are labeled 1, 5, 3 while edges are labeled 4, 2 respectively; the magic constant of labeling h is 10 since h = 1+4+5 = 5+2+3. Notice that the author uses here the notation P_n for the path graph with n+1 vertices.

%e In general, for P_n the magic labeling constant h satisfies 3*(n+1) - floor(n/2) <= h <= 3*(n+1) + floor(n/2).

%e If n=2*k the lower bound for h is 5*k+3 and the following path graph has h=5k+3:

%e     k+1   k+2    2k  2k+1

%e      o     o  .. o     o

%e       \   /\      \   /

%e        \ /  \      \ /

%e         o    o  ..  o

%e         1    2      k

%e Notice that the vertices labels are given by the perfect shuffle of [k+1..2k+1] and [1..k] while edge labels are 4k+1,4k,...,2k+2 respectively.

%e If n=2*k+1 the lower bound for h is 5*k+6 and the following path graph has h=5k+6:

%e     1  2       k  k+1

%e     o  o   ..  o  o

%e     | /|      /| /|

%e     |/ |/      |/ |

%e     o  o  ..   o  o

%e    k+2  k+3   2k+1 2k+2

%e Notice that the vertices labels are given by the perfect shuffle of [1..k+1] and [k+2..2k+2] while edge labels are 4k+3,4k+2,...,2k+3 respectively.

%e (End)

%o (Python)

%o from itertools import permutations

%o print("0"," ","1")

%o print("1"," ","3")

%o for j in range(5,27,2):

%o     x = list(range(1,j+1))

%o     sum2 = 0

%o     for a in permutations(x):

%o         x = list(a)

%o         sum1 = x[0]+x[1]+x[2]

%o         d = 1

%o         for i in range(2,j-2,2):

%o             if (sum1== x[i]+x[i+1]+x[i+2]):

%o                 d = 1

%o             else:

%o                 d = 0

%o                 break

%o         if (d==1):

%o             if (a[0]<a[j-1]):

%o                 sum2 = sum2+1

%o     print((j-1)//2, " ", sum2)

%o (MiniZinc)

%o % filename: magicpn.mzn: generate solutions of size n

%o % usage: minizinc -a --soln-sep "" --search-complete-msg "" -D"n=5;" magicpn.mzn

%o include "globals.mzn";

%o int: n;

%o int: lo = 3*(n+1) - n div 2;

%o int: hi = 3*(n+1) + n div 2;

%o array[1..2*n+1] of var 1..2*n+1: x;

%o var lo..hi: h; % aka magic constant of labeling; lo/hi are tight bounds

%o constraint alldifferent(x);

%o constraint x[1] <= x[2*n+1];

%o constraint forall([h = x[2*i-1] + x[2*i] + x[2*i+1] | i in 1..n]);

%o solve satisfy;

%o output [show(x)];

%o % _Gheorghe Coserea_, May 18 2018

%Y Cf. A145692 (Edge-magic labelings of cycles C_n).

%K nonn,more

%O 0,2

%A _Mukkai S. Krishnamoorthy_, Feb 07 2014

%E a(15) from _Max Alekseyev_, Jul 25 2022