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

Author

Darío Clavijo, Jan 05 2025

Keywords

• nonn

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)).

Examples

			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.
		

Links

• Rosetta code, Permutations/Rank of a permutation.

Crossrefs

Cf. A000225, A000523, A070939, A380856

Programs

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 *)

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)])