cp's OEIS Frontend

A337274 Number of distinct graceful labelings of trees with n vertices.

%I A337274 #40 Sep 15 2020 06:35:03
%S A337274 1,1,1,2,6,20,82,376,2010,11788,77816,556016,4366814,36773666,
%T A337274 335394762,3251474116,33770466316,370474881290,4317182375632,
%U A337274 52861107601060,683129289079532,9234228045432682,131059243976153410
%N A337274 Number of distinct graceful labelings of trees with n vertices.
%C A337274 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.
%H A337274 David Anick, <a href="https://doi.org/10.1016/j.dam.2015.05.031">Counting graceful labelings of trees: a theoretical and empirical study</a>, Discrete Applied Mathematics 198 (2016), 65-81.
%F A337274 If n>3, a(n) = A033472(n)/2.
%e A337274 For example, the six labelings for n=5 are:
%e A337274   1--5, 2--5, 1--3, 3--4;
%e A337274   1--5, 2--5, 1--3, 4--5;
%e A337274   1--5, 2--5, 2--4, 2--3;
%e A337274   1--5, 2--5, 2--4, 3--4;
%e A337274   1--5, 2--5, 3--5, 3--4;
%e A337274   1--5, 2--5, 3--5, 4--5.
%e A337274 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.
%o A337274 (PARI) \\ After David Anick's C program GLs
%o A337274 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));
%o A337274   nn = n-1; n1 = n+1; w[n1] = 1; w[n] = 2; t[1] = n; t[2] = nn; m = nn - 1;
%o A337274   while (a[nn]==0,
%o A337274     for (jj=n1-m, n,
%o A337274       u = a[n1-jj]; v = u + n1 - jj;
%o A337274       z = w[u+1]; while (z > 0, u = r[z]; z = w[u+1]);
%o A337274       z = w[v+1]; while (z > 0, v = r[z]; z = w[v+1]);
%o A337274       if (v == u, j=jj; break);
%o A337274       if (v > u, w[v+1] = jj; r[jj] = u; t[jj] = v,
%o A337274                  w[u+1] = jj; r[jj] = v; t[jj] = u);
%o A337274       j=jj+1
%o A337274     );
%o A337274     if (j > n, count++; w[t[n]+1] = -1 );
%o A337274     if (j >= n, a[1]++; if (a[1] < nn, m = 1; next );
%o A337274                 a[1] = 0; j = nn; w[t[nn]+1] = -1 );
%o A337274     m = n1 - j; a[m]++;
%o A337274     while (a[m]> n-m, a[m]=0; a[m++]++; w[t[n1-m]+1]=-1)
%o A337274   ); count};
%o A337274 for(k=1,12,print1(a337274(k),", ")) \\ _Hugo Pfoertner_, Sep 04 2020
%Y A337274 Cf. A000055, A033472.
%K A337274 nonn,more
%O A337274 1,4
%A A337274 _Don Knuth_, Sep 03 2020
%E A337274 a(18)-a(19) from _Bert Dobbelaere_, Sep 06 2020
%E A337274 a(20)-a(23) (from A033472) from _Joerg Arndt_, Sep 15 2020