A379905 Rank of the permutation resulting from a pre-order traversal of a binary tree which is complete except for the final row and has vertices numbered 0 to n-1.

0, 0, 0, 1, 3, 8, 30, 222, 1302, 8442, 63570, 545473, 5249163, 55941128, 653682990, 8597126190, 117809490990, 1730350233390, 27183297753390, 454752069221550, 8070074352360750, 151403473011001710, 2993918729983972590, 62232717584055513822, 1356493891878893498262

Offset

1,5

Comments

Permutations are ranked in lexicographic order with the identity permutation as rank 0.

The tree is complete when n = 2^k - 1.

Also the tree has A070939(n) levels and the tree height is floor(log_2(n)).

Links

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

Rosetta code, Permutations/Rank of a permutation.

Example

For n = 5, the tree is
      0
     / \
    1   2
   / \
  3   4
Pre-order traversal is vertices {0,1,3,4,2} and among the permutations of 0..4 this has rank a(5) = 3.

Mathematica

a[n_Integer]:=Module[{res={}, data, len}, data=Range[n]; len=Length[data]; Which[MemberQ[{1, 2, 3}, n], 0, n==4, 1, True, DepthFirstScan[TreeGraph[Table[Floor[j/2]->j, {j, 2, len}]], 1, {"PrevisitVertex"->(AppendTo[res, #]&)}]; ResourceFunction["PermutationIndex"][res]-1]]; a/@Range[1, 25] (* Shenghui Yang, Feb 15 2025 *)

Prog

(Python)
from binarytree import Node, build
from sympy.combinatorics import Permutation
a = lambda n: Permutation([node.value for node in build(list(range(n))).preorder]).rank()
print([a(n) for n in range(1, 26)])

Crossrefs

Cf. A000225, A000523, A070939, A380856

Sequence in context: A066304 A298456 A145776 * A066165 A323775 A360605

Adjacent sequences: A379902 A379903 A379904 * A379906 A379907 A379908

Keyword

nonn

Author

Darío Clavijo, Jan 05 2025

Status

approved