C (clang), 146 141 140 137 127 bytes

g(*n){return*n%8388607;}f(n,r,i,F,l){for(float b,a=r=0;F=a++<n;r+=l*F)for(b=i=l=0;b++<n;)g(&a)<g(&b)?l+=a>b,F*=++i:0;return r;}

Try it online!

-3 with some Boolean comparison shenanigans + -2 rearranging for associativity

-1 remembering I don't exactly have to *zero* the sign and exponent

-3 thanks to m90

-10 thanks to m90 realizing that it actually is shorter to calculate the factorial separately--to use the same loop! (and with some other tweaks on top)

Inaccurate for \$n>15\$ due to integer width. Good for all \$n \leq 23\$ if explicit 64-bit unsigned types added where appropriate.

I'm definitely not the best C golfer out there, but this idea was just too fun not to use... For porting my Jelly solution, C may not have any built-in functionality for converting an integer to a string representation of its binary digits to compare with a costly strcmp, but that's not to say it doesn't still have built-in functionality for left-aligning integers’ binary digits. Namely, representing them as floats.

Ungolfed, and with a higher failure threshold:

#include <stdint.h>

int32_t sort_key(int32_t* n) {
    int32_t significand = *n & (1 << 23) - 1;
    int32_t exponent = ((uint32_t) *n) >> 23;
    return significand + exponent;
}

uint64_t f(int n) {
    uint64_t rank = 0;
    for (float a = 1; a <= n; a++) {
	uint64_t factorial = 1;
        int index = 0;
        int lehmer = 0;
        for (float b = 1; b <= n; b++) {
            int32_t diff = sort_key((int32_t *)&a) - sort_key((int32_t *)&b);
            if (diff < 0) {
                index++;
		factorial *= index;
            }
            if (diff < 0 && a > b) {
                lehmer++;
            }
        }
        rank += lehmer * factorial;
    }
    return rank;
}

Try it online!

Ignoring irrelevant special cases, floating point represents numbers as essentially the product of a fixed-point real in \$[1, 2)\$ with an integer power of 2 by encoding the exponent of the power of 2 and the fractional part (the "significand") of the fixed-point real--this can also be thought of as the exponent encoding where to put the radix point within the significand's binary digits infinitely 0-padded to the left and right, hence the name "floating point". How and why the exponent works is entirely besides the point here, because all the solution does with its floats (single precision--the factorial-heavy solution outgrows 64-bit ints long before it outgrows 32-bit floats!) is discard the sign bit and exponent to compare the significands directly.

Single-precision float has one sign bit and 8 exponent bits, so type punning to int (conveniently implicit in the declaration of g! Which actually saves two bytes over a #define) then truncating/zeroing the upper 9 bits with &0x7fffff yields a constant offset from the significand as a signed integer (<<9 clobbers the exponent and sign just the same, but requires casting to unsigned for useful comparisons because the top bit of the significand ends up in the sign bit instead).

Unlike variable-length bit strings, floating-point significands don’t distinguish trailing zeroes, so in order to determine if node a precedes node b in the permutation, I formerly used a separate tiebreaker comparing the nodes themselves before m90 ingeniously suggested decrementing the modulus used for extracting the significand (so equivalently, %0x7fffff instead of &0x7fffff)—-so that rather than being discarded, the exponent bits above the significand get sent to the least significant bits instead! For each node a, the solution compares it with every node b, and: counts as i the true comparisons to determine a’s index from the right end of the permutation, counts as l the true comparisons for which it also holds that a > b (a’s corresponding term in the permutation’s Lehmer code), multiplies l by the factorial of i (for(;i;)l*=i--), and finally adds it to a running sum r across all a in order to compute the permutation’s rank as the factoradic valuation of its Lehmer code.

x86-64 machine code, 38 bytes

31 C0 31 F6 89 F9 D1 EE 72 FC F9 11 F6 39 FE 77 F5 F7 E1 11 D2 39 F2 72 FA 29 F2 01 D0 F3 0F B8 D2 29 D0 E2 E6 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes \$n\$ as a 32-bit integer in EDI and returns the rank as a 32-bit integer in EAX.

Initialisation; Advancement

The program will go through the pre-order traversal and, at each step, determine the rank of the current partial permutation among all partial permutations of the same length. To do this, at each step, multiply the rank by the number of unplaced values (as each of those values is a possible continuation), then add the index of the current value among the unplaced values.

Number the nodes starting from 1 rather than 0, so that the children of \$a\$ are \$2a\$ and \$2a+1\$ – adding one bit to the end of \$a\$'s bits.

To proceed through the pre-order traversal, first descend to a left child by adding a 0 bit to the end of the value. If this goes outside the \$n\$ tree by producing a value greater than \$n\$, then move forwards: ascend to parents until the ascension is from a left child, then descend to a right child – in numbers, remove all trailing 1 bits and the 0 bit before them, and add a 1 bit.

f:  xor eax, eax    # Set EAX to 0. EAX will hold the current partial permutation's rank.
    xor esi, esi    # Set ESI to 0. ESI will hold x, the current value for the traversal;
                    #  it will go from 0 to 1 in the first iteration.
    mov ecx, edi    # Set ECX to n. ECX will hold the number of unplaced values.
u:  shr esi, 1      # Shift x right 1 bit. The last bit goes into CF.
    jc u            # Jump back, to repeat, if that bit is 1.
    stc             # Set CF to 1.
n:  adc esi, esi    # Add x+CF to x, which appends CF to its bits.
                    #  When this instruction is reached from above, CF=1;
                    #  when later iterations jump here directly, CF=0.
    cmp esi, edi    # Compare x and n.
    ja u            # Jump back if x exceeds n.

Updating the rank

As mentioned earlier, to update the rank, multiply the rank by the number of unplaced values, then add the index of the current value among the unplaced values.

That index is equal to the number of nodes that have a lesser value than the current value but appear later in the pre-order traversal. For any node that appears later in the pre-order traversal, its value is less than the current value if and only if its depth is less than the current node's depth.

The number \$y\$ of later nodes at the same depth can be calculated by subtracting the current value \$x\$ from the total number of nodes at its depth and lesser depths, which is the first number of the form \$2^i-1\$ that is at least \$x\$. At each successive lower depth, the number of later nodes gets halved and rounded down.

Take the binary expansion \$y = \Sigma_i\ 2^i y_i\$. Because the bits stay separate, this allows the index to be calculated as \$\Sigma_i\ y_i(\Sigma_{j<i}\ 2^j) = \Sigma_i\ y_i(2^i - 1) = y - \Sigma_i\ y_i\$.

    mul ecx         # Multiply the rank in EAX by ECX; the result's high part goes into EDX.
                    # As long as the result remains within 32 bits, EDX is 0 and CF=0.
l:  adc edx, edx    # Add EDX+CF to EDX, which appends CF to its bits.
                    #  CF is 0 in the first iteration, and 1 in later iterations.
    cmp edx, esi    # Set flags from calculating EDX - x.
    jb l            # Jump back, to repeat, if EDX was less than x.
    sub edx, esi    # Subtract x from EDX to obtain y.
    add eax, edx    # Add y to the rank in EAX.
    popcnt edx, edx # Set EDX to the number of 1 bits in y.
    sub eax, edx    # Subtract that number from the rank in EAX.
    loop n          # Decrease ECX by 1 and jump if it's nonzero.
    ret             # Return. (The rank in EAX is the return value.)

Charcoal, 42 34 bytes

≔ＥＮ↨⊕ι²θ≔⁰ηＷ⁻θυ≔∧⊞Ｏυ⌊ι⁺×ηＬι⌕ι⌊ιηＩη

Try it online! Link is to verbose version of code. Explanation: Uses @UnrelatedString's observation.

≔ＥＮ↨⊕ι²θ

Generate the binary representations of the numbers 1..n.

≔⁰η

Start calculating the rank as if sorted.

Ｗ⁻θυ

While there are binary representations left to be ranked...

≔∧⊞Ｏυ⌊ι⁺×ηＬι⌕ι⌊ιη

... add the minimum to the list of representations that have been ranked, and then update the rank. This code was inspired by the Java code on the linked Rosetta Code page, but it's been rewritten to avoid having to sort the representations first, which in fact simplifies the code, since the number of remaining integers lower than the current integer is simply the position of the minimum representation in the list.

Ｉη

Output the final rank.

Python, 115 bytes

lambda n:[*permutations(range(n))].index((t:=lambda x:x<n and(x,)+t(2*x+1)+t(2*x+2)or())(0))
from itertools import*

Attempt This Online!

Python, ⁹³ 91 bytes

-2 bytes thanks to @Jonathan Allan by using the range [0, n] instead of [1, n]

lambda n:[*permutations(r:=range(n+1))].index((*sorted(r,key=bin),))
from itertools import*

Attempt This Online!

Port of Unrelated String's amazing answer

Python + SymPy, ¹¹¹ 88 bytes

-23 bytes thanks to @Jonathan Allan by switching to @Unrelated String's approach

lambda n:Permutation(sorted(range(n+1),key=bin)).rank()
from sympy.combinatorics import*

Attempt This Online!

Use of sympy was inspired by the program provided in A379905

Maple, 94 bytes

proc(n)sort(convert~([$n],binary),key=String);combinat:-rankperm(convert~(%,decimal,2))-1;end;

This is @Unrelated String's nice algorithm. Take [1,...,n], convert to binary, sort in string (lex) order, convert back to decimal, and find the rank (builtin).

Jelly, 8 4 bytes

BÞŒ¿

Try it online!

-4 because WHY exactly did I think Hamming weight was involved again??

Returns the rank 1-indexed, but the test harness converts to 0-indexed for convenience.

 Þ      Sort [1 .. n] by lexicographic comparisons of
B       their binary digits.
  Œ¿    Builtin permutation index.

Intuition:

If you label the nodes with \$[1, n]\$ instead of \$[0, n-1]\$, the labels at each "tier" of the tree all have the same length in bits:

                    1
                .../ \...
           ..../         \....
          /                   \
         10                   11
        /  \                 /  \
       /    \               /    \
      /      \             /      \
     /        \           /        \
   100        101       110        111
  /   \      /   \     /   \      /   \
1000 1001  1010 1011 1100 1101  1110 1111 

and not only that, but the tree is a prefix tree of the binary representations--the direct children of every node are labeled with precisely its label with either 0 or 1 appended. Hence, lexicographic comparison of the bits will sort correctly within each tier, sort all nodes after their immediate parents, and sort all nodes before later nodes than their parents in their parents' tier.