The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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<=k3, a(n) = A033472(n)/2. 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 = n; t = 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++; if (a < nn, m = 1; next );                 a = 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 2020 CROSSREFS Cf. A000055, A033472. Sequence in context: A177475 A118476 A260788 * A115084 A177476 A266600 Adjacent sequences:  A337271 A337272 A337273 * A337275 A337276 A337277 KEYWORD nonn,more AUTHOR Don Knuth, Sep 03 2020 EXTENSIONS a(18)-a(19) from Bert Dobbelaere, Sep 06 2020 a(20)-a(23) (from A033472) from Joerg Arndt, Sep 15 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 16 08:18 EDT 2021. Contains 347469 sequences. (Running on oeis4.)