login
Total number of ordered graceful labelings of graphs with n edges.
2

%I #24 Mar 09 2021 03:05:13

%S 1,2,4,12,40,182,906,5404,35494,264178,2124078,18965372,181080940,

%T 1879988162,20764521072,246377199752,3085635516364,41182472709986,

%U 577129788232678,8552244962978250,132591961730782524,2161198867136837458

%N Total number of ordered graceful labelings of graphs with n edges.

%C Also the number of sequences l_0, l_1, ..., l_{n-1} such that 0 <= l_k <= k and such that l_j+n-j != l_k for 0 <= j,k < n.

%C Ordered graceful labelings were originally called "near alpha-labelings". They have also been called "gracious labelings" and "beta^+-labelings.

%C The corresponding number of "true" alpha-labelings is A005193(n).

%C The corresponding number of unrestricted graceful labelings is A000142(n).

%C The corresponding number of unrestricted graceful labelings of bipartite graphs is 2*A334613(n+1).

%C Hence A005193(n) <= a(n) <= 2*A334613(n+1) <= A000142(n).

%D D. E. Knuth, The Art of Computer Programming, Volume 4B, Section 7.2.2.3 will have an exercise based on this sequence.

%H S. I. El-Zanati, M. J. Kenig, and C. Vanden Eynden, <a href="https://ajc.maths.uq.edu.au/pdf/21/ocr-ajc-v21-p275.pdf">Near α-labelings of bipartite graphs</a>, Australasian Journal of Combinatorics, 21 (2000), 275-285.

%e For n=4 the a(4)=12 solutions l_0l_1l_2l_3 are 0000, 0001, 0011, 0012, 0020, 0022, 0101, 0103, 0111, 0112, 0122, 0123. (Of these, 0022 and 0103 are not counted by A005193.)

%Y Cf. A000142, A005193, A334613.

%K nonn,more

%O 1,2

%A _Don Knuth_, Mar 06 2021

%E a(18)-a(22) from _Bert Dobbelaere_, Mar 09 2021