A334613 Number of distinct graceful labelings of bipartite graphs with n vertices and n-1 edges.

1, 1, 1, 2, 7, 28, 151, 907, 6467, 51151, 458478, 4455476, 48162974, 557022350, 7020022164, 94129389215, 1357181821028, 20661645476348

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<=k<n. (Altogether (n-1)!/2 possibilities.) If the resulting graph has no odd cycles, this is a graceful labeling of a bipartite graph.

Links

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

Example

For example, the seven labelings for n=5 are:
  1--5, 2--5, 1--3, 2--3;
  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.
The first of these is the four-cycle plus an isolated vertex; the other six are the trees in A337274.

Crossrefs

Cf. A337274.

Sequence in context: A307594 A362084 A296726 * A365559 A123026 A013011

Adjacent sequences: A334610 A334611 A334612 * A334614 A334615 A334616

Keyword

nonn,more

Author

Don Knuth, Sep 08 2020

Extensions

a(17)-a(18) from Bert Dobbelaere, Sep 11 2020

Status

approved