A393155 Number of involution pairs of graceful Prüfer codes on n vertices with both codes in the first half of the lexicographic order.

0, 0, 0, 1, 2, 20, 61, 469, 2643, 20483, 140228, 1241978

Offset

3,5

Comments

A graceful Prüfer code of length n-2 is a sequence over {0,1,...,n-1} corresponding to a gracefully labeled tree on n vertices. Each such code belongs to an involution pair obtained by applying the natural involution induced by relabeling the underlying tree. The lexicographic rank of a Prüfer code is taken among all n^(n-2) sequences of length n-2 over {0,1,...,n-1}, ordered lexicographically. Let H = n^(n-2)/2. This sequence counts involution pairs (c,c') such that rank(c) < H and rank(c') < H. In other words, each counted pair is lying entirely in the first half of the space of codes.

References

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

Links

Table of n, a(n) for n=3..14.

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

Formula

a(n) = A337274(n) - A393154(n) - A393156(n).

Example

The first involution pair of graceful Prüfer codes lying entirely in the first half appears for a tree with 6 vertices. It corresponds to two graceful labelings of a path: 3-5-0-4-1-2 (Prüfer code: 1,4,5,0) and 2-0-5-1-4-3 (Prüfer code: 0,5,4,1). These two codes form an involution pair obtained by exchanging the roles of the vertices using the formula f(v)=n-1-v.

Crossrefs

Cf. A033472, A337274, A393154, A393156.

Sequence in context: A133217 A001504 A192351 * A136905 A230644 A183907

Adjacent sequences: A393152 A393153 A393154 * A393156 A393157 A393158

Keyword

nonn,hard,more

Author

Igor Blokhin, Feb 03 2026

Status

approved