* Let $a(n)$ be [A329369][1] (i.e, number of permutations of ${1,2,...,m}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \leqslant k < m-1$) is the binary expansion of $n$). Here

$$
a(2^m(2k+1)) = \sum\limits_{j=0}^{m}\binom{m+1}{j}a(2^jk), \\
a(0) = 1
$$

* Another way to define $a(n)$ through itself is the following:

$$
a(2^m((2k+1)2^n-1)) = \sum\limits_{i=0}^{m} \left(\sum\limits_{j=0}^{m-i}a(2^{j+1}k)L_1(m, m-i, j)\right)\frac{1}{i!}\sum\limits_{q=0}^{i}(m-q+1)^n\binom{i}{q}(-1)^q, \\
a(0) = 1
$$

where

$$
L_1(n, k, m) = (n-k)!W_1(n-m, k-m, m+1)
$$

and where

$$
W_1(n, k, m) = (k+m)W_1(n-1, k, m) + (n-k)W_1(n-1, k-1, m) + [m > 1]W_1(n, k, m-1), \\
W_1(0, 0, m) = 1
$$

For the related sequences in OEIS, see [A173018][2], [A062253][3], [A062254][4], [A062255][5].

* Suppose that we slightly correct formula for $W_1(n,k,m)$ to get $W_2(n,k,m)$:

$$
W_2(n, k, m) = (k+m+1)W_2(n-1, k, m) + (n-k)W_2(n-1, k-1, m) + [m > 1]W_2(n, k, m-1), \\
W_2(0, 0, m) = 2
$$

Also

$$
L_2(n, k, m) = (n-k)!W_2(n-m, k-m, m+1)
$$

* Let $b(n)$ be an integer sequence such that

$$
b(2^m((2k+1)2^n-1)) = \sum\limits_{i=0}^{m} \left(\sum\limits_{j=0}^{m-i}b(2^{j+1}k)L_2(m, m-i, j)\right)\frac{1}{i!}\sum\limits_{q=0}^{i}(m-q+1)^n\binom{i}{q}(-1)^q, \\
b(0) = 1
$$

* Let $c(n)$ be [A000153][6]. Here

$$
c(n) = nc(n-1) + (n-2)c(n-2), \\
c(0) = 0, c(1) = 1
$$ 

* Let

$$
s(n) = \sum\limits_{i=0}^{2^n-1} b(i)
$$

I conjecture that

$$
s(n)=c(n+1).
$$

Here is the *PARI/GP* program to check it numerically:

    W2(n, k, m) = if(n < 0 || k < 0, 0, if(n == 0 && k == 0, 1, (k+m+1)*W2(n-1, k, m) + (n-k)*W2(n-1, k-1, m) + if(m>1, W2(n, k, m-1))))
    L2(n, k, m) = (n-k)!*W2(n-m, k-m, m+1)
    f(n,m,k) = sum(i=0, m, sum(j=0, m-i, b(2^(j+1)*k)*L2(m, m-i, j))/i!*sum(q=0, i, (m-q+1)^n*binomial(i, q)*(-1)^q))
    b(n) = if(n == 0, 1, my(A = valuation(n, 2), n = n >> A, B = valuation(n+1, 2), C = (n+1) >> (B+1)); f(B, A, C))
    c(n) = if(n < 2, n, n*c(n-1) + (n-2)*c(n-2))
    s(n) = sum(i = 0, 2^n - 1, b(i))
    test(n) = s(n) == c(n+1)

Is there a way to prove it?


  [1]: https://oeis.org/A329369
  [2]: https://oeis.org/A173018
  [3]: https://oeis.org/A062253
  [4]: https://oeis.org/A062254
  [5]: https://oeis.org/A062255
  [6]: https://oeis.org/A000153