OFFSET
3,3
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 (or vice versa). In other words, each counted pair is split between the two halves of the lexicographic space.
REFERENCES
Douglas B. West, Introduction to Graph Theory, Pearson Education, 2002, page 81.
LINKS
Igor Blokhin, Graceful Prüfer Codes (Python repository).
EXAMPLE
For n = 4, Prüfer codes have length 2 and are ordered lexicographically among all 4^2 = 16 sequences. The code (0,0) corresponds to the star K_{1,3} with center at vertex 0 and leaves {1,2,3}.
Similarly, the code (3,3) corresponds to the star with center at vertex 3 and leaves {0,1,2}.
These two codes form an involution pair obtained by exchanging the roles of the vertices using the formula f(v)=n-1-v. The lexicographic rank of (0,0) is 0, which lies in the first half {0,...,7}, while the rank of (3,3) is 15, which lies in the second half {8,...,15}.
Hence this pair is split between the two halves and contributes 1 to a(4).
The first value is a(3), because there is no Prüfer codes for trees with 1 or 2 vertices.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Igor Blokhin, Feb 03 2026
STATUS
approved