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,2

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

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

Table of n, a(n) for n=1..22.

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

Example

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

Crossrefs

Cf. A000142, A005193, A334613.

Sequence in context: A033472 A134983 A330679 * A218144 A222919 A264760

Adjacent sequences: A342222 A342223 A342224 * A342226 A342227 A342228

Keyword

nonn,more

Author

Don Knuth, Mar 06 2021

Extensions

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

Status

approved