A337274 Number of distinct graceful labelings of trees with n vertices.
1, 1, 1, 2, 6, 20, 82, 376, 2010, 11788, 77816, 556016, 4366814, 36773666, 335394762, 3251474116, 33770466316, 370474881290, 4317182375632, 52861107601060, 683129289079532, 9234228045432682, 131059243976153410
Offset: 1
Comments
Examples
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.Links
Crossrefs
Programs
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}; for(k=1,12,print1(a337274(k),", ")) \\ Hugo Pfoertner, Sep 04 2020Formula
Extensions