- Let $a(n)$ be A329369 (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(2^n(2k+1)-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, A062253, A062254, A062255.
- 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(2^n(2k+1)-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. 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?