|
|
A337274
|
|
Number of distinct graceful labelings of trees with n vertices.
|
|
4
|
|
|
1, 1, 1, 2, 6, 20, 82, 376, 2010, 11788, 77816, 556016, 4366814, 36773666, 335394762, 3251474116, 33770466316, 370474881290, 4317182375632, 52861107601060, 683129289079532, 9234228045432682, 131059243976153410
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Consider vertices numbered 1 to n. Add the edges 1--n, 2--n, and either 1--(n+1-k), 2--(n+2-k), ... or k--n for 3<=k<n. (Altogether (n-1)!/2 possibilities.) If the resulting graph has no cycles, this is a graceful labeling of a tree.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For example, the six labelings for n=5 are:
1--5, 2--5, 1--3, 3--4;
1--5, 2--5, 1--3, 4--5;
1--5, 2--5, 2--4, 2--3;
1--5, 2--5, 2--4, 3--4;
1--5, 2--5, 3--5, 3--4;
1--5, 2--5, 3--5, 4--5.
There are three trees (A000055); the path P4 has two labelings, the graph K_{1,4} has one, the other ("chair" or "fork") has three.
|
|
PROG
|
(PARI) \\ After David Anick's C program GLs
a337274(N) = { if(N<4, return(1)); my (n=N-1, count, i, j, k, m, nn, n1, u, v, z, a=vectorsmall(N), r= vectorsmall(N), t=vectorsmall(N), w=vectorsmall(N, i, -1));
nn = n-1; n1 = n+1; w[n1] = 1; w[n] = 2; t[1] = n; t[2] = nn; m = nn - 1;
while (a[nn]==0,
for (jj=n1-m, n,
u = a[n1-jj]; v = u + n1 - jj;
z = w[u+1]; while (z > 0, u = r[z]; z = w[u+1]);
z = w[v+1]; while (z > 0, v = r[z]; z = w[v+1]);
if (v == u, j=jj; break);
if (v > u, w[v+1] = jj; r[jj] = u; t[jj] = v,
w[u+1] = jj; r[jj] = v; t[jj] = u);
j=jj+1
);
if (j > n, count++; w[t[n]+1] = -1 );
if (j >= n, a[1]++; if (a[1] < nn, m = 1; next );
a[1] = 0; j = nn; w[t[nn]+1] = -1 );
m = n1 - j; a[m]++;
while (a[m]> n-m, a[m]=0; a[m++]++; w[t[n1-m]+1]=-1)
); count};
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|