3,2

Any labeled tree on n vertices admits a unique Prüfer code. A graceful labeling of a tree on n vertices assigns the labels {0, 1, ..., n-1} to the vertices such that the induced edge labels (absolute differences of endpoint labels) are exactly {1, 2, ..., n-1}. This sequence counts the Prüfer codes of gracefully labeled trees on n vertices with n-1 in the first position of the code.

Douglas B. West, Introduction to Graph Theory, Pearson Education Pte. Ltd, 2002, page 81.

Igor Blokhin, Graceful Prüfer Codes (Python repository).

For example, for a(4)=2:

By Cayley's formula, there are 4^(4-2)=16 distinct Prüfer codes, corresponding bijectively to the 16 labeled trees on 4 vertices.

Among these, only some labelings are graceful.

We enumerate all gracefully labeled trees on 4 vertices. There are A033472(4) = 4 in this case:

1) the star graph with the center labeled 0 and leaves labeled 1, 2 and 3. Prüfer code is (0, 0);

2) the star graph with the center labeled 3 and the leaves 0, 1 and 2. Prüfer code is (3, 3);

3) the path graph 2-1-3-0. Prüfer code is (3, 1);

4) the path graph 1-2-0-3. Prüfer code is (2, 0).

Then count how many of these Prüfer codes have the maximum label (which is 3 in this case) in the first position of the code, there are 2 such Prüfer codes: (3, 3) and (3, 1).

Cf. A033472.

Sequence in context: A057693 A053496 A079577 * A150078 A150079 A150080

Adjacent sequences: A392079 A392080 A392081 * A392083 A392084 A392085

nonn,hard,more

Igor Blokhin, Dec 30 2025

approved