A342225 Total number of ordered graceful labelings of graphs with n edges.

1, 2, 4, 12, 40, 182, 906, 5404, 35494, 264178, 2124078, 18965372, 181080940, 1879988162, 20764521072, 246377199752, 3085635516364, 41182472709986, 577129788232678, 8552244962978250, 132591961730782524, 2161198867136837458

Offset: 1

Author

Don Knuth, Mar 06 2021

Keywords

• nonn
• more

Comments

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.

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

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

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

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

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

Examples

			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.)
		

References

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

Links

• S. I. El-Zanati, M. J. Kenig, and C. Vanden Eynden, Near α-labelings of bipartite graphs, Australasian Journal of Combinatorics, 21 (2000), 275-285.

Crossrefs

Cf. A000142, A005193, A334613.

Extensions

a(18)-a(22) from Bert Dobbelaere, Mar 09 2021