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

0, 1, 2, 8, 33, 177, 950, 5972, 41124, 302169, 2462651, 21078452

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. In other words, each counted pair is laying in the second half of the lexicographic 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) - A393155(n) - A393154(n).

Example

The first involution pair of graceful Prüfer codes lying entirely in the second half appears for a tree with 4 vertices. It corresponds to two graceful labelings of a path: 3-0-2-1 (Prüfer code: 2,0) and 0-3-1-2 (Prüfer code: 3,1).

Crossrefs

Cf. A033472, A337274, A393154, A393155.

Sequence in context: A391122 A030977 A030821 * A236382 A390201 A393725

Adjacent sequences: A393153 A393154 A393155 * A393157 A393158 A393159

Keyword

nonn,hard,more

Author

Igor Blokhin, Feb 04 2026

Status

approved