cp's OEIS Frontend

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.

%I A379905 #39 Feb 23 2025 09:26:59
%S A379905 0,0,0,1,3,8,30,222,1302,8442,63570,545473,5249163,55941128,653682990,
%T A379905 8597126190,117809490990,1730350233390,27183297753390,454752069221550,
%U A379905 8070074352360750,151403473011001710,2993918729983972590,62232717584055513822,1356493891878893498262
%N 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.
%C A379905 Permutations are ranked in lexicographic order with the identity permutation as rank 0.
%C A379905 The tree is complete when n = 2^k - 1.
%C A379905 Also the tree has A070939(n) levels and the tree height is floor(log_2(n)).
%H A379905 Rosetta code, <a href="https://rosettacode.org/wiki/Permutations/Rank_of_a_permutation">Permutations/Rank of a permutation</a>.
%e A379905 For n = 5, the tree is
%e A379905       0
%e A379905      / \
%e A379905     1   2
%e A379905    / \
%e A379905   3   4
%e A379905 Pre-order traversal is vertices {0,1,3,4,2} and among the permutations of 0..4 this has rank a(5) = 3.
%t A379905 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 *)
%o A379905 (Python)
%o A379905 from binarytree import Node, build
%o A379905 from sympy.combinatorics import Permutation
%o A379905 a = lambda n: Permutation([node.value for node in build(list(range(n))).preorder]).rank()
%o A379905 print([a(n) for n in range(1,26)])
%Y A379905 Cf. A000225, A000523, A070939, A380856
%K A379905 nonn
%O A379905 1,5
%A A379905 _Darío Clavijo_, Jan 05 2025