- 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 $$
- Let $\nu_2(n)$ be A007814 (i.e., number of trailing zeros in the binary expansion of $n$). Here
$$ \nu_2(2n+1)=0, \\ \nu_2(2n) = \nu_2(n) + 1 $$
- Here is the conjectured algorithm to calculate $a(2n)$ without using binomial coefficients.
- Start with $A=2n, B, i=1$ and reserve $5$ vectors $t_1, t_2, t_3, t_4, t_5$.
- Then while $A>0$ apply $B:=\nu_2(A)$, $t_{1, i} = B$, $A:=2^B\left\lfloor\frac{A}{2^{B+1}}\right\rfloor$, $i:=i+1$. Also, let $\#t_i$ be a length of vector $t_i$.
- After that for $i$ from $1$ to $\#t_1$ apply $A:=t_{1,i}$, $t_2$ is a vector of length $A+1$ with elements $t_{2,j}=0$. Also, if $i=1$, then $t_3$ is a vector of length $A+1$ with elements $t_{3,j}=1$. After that, for all $i$ we have $t_4 = t_3$.
- After that (and staying in the cycle for $i$) for $j$ from $2$ to $A+1$ and for $k$ from $1$ to $2$ apply $t_{2,k} := t_{3,j+k-2}$. Then (staying in the cycle for $j$) for $k$ from $3$ to $j$ apply $t_{2,k} := t_{5,1} + (k-1)t_{5,2} + \sum\limits_{s=3}^{k-1} t_{5, s}$. But as you can see, $t_5$ still was not defined. It's ok for $j=2$. After that (and staying in the cycle for $j$) apply $t_5 := t_2$, $t_{4,j} := t_{2,1} + jt_{2,2} + \sum\limits_{s=3}^{j} t_{2, s}$.
- After that (while you left cycle for $j$ and staying in the cycle for $i$) if $i<\#t_1$ then $t_3$ is a vector of length $t_{1,i+1}+1$ with elements $t_{3,j} = t_{4,j+t_{1,i}-t_{1,i+1}}$.
- Finally, $a(2n)$ is the same as sum of all elements of the vector $t_2$ plus $At_{2,2}$.
Here is the PARI/GP program to check it numerically:
a(n) = if(n == 0, 1, my(A = valuation(n, 2), B = n >> (A+1)); sum(j=0, A, binomial(A+1, j)*a(B << j)))
a1(n) = {
my(A = (n+1) >>
valuation(n+1, 2) - 1);
if(A == 0, 1,
my(B, v1, v2, v3, v4, v5);
v1 = [];
while(A > 0,
B = valuation(A, 2);
v1 = concat(v1, B);
A = (A >> (B+1)) << B);
v1 = Vecrev(v1);
for(i=1, #v1,
A = v1[i];
v2 = vector(A+1, j, 0);
if(i==1,
v3 = vector(A+1, j, 1));
v4 = v3;
for(j=2, A+1,
for(k=1, 2,
v2[k] = v3[j+k-2]);
for(k=3, j,
v2[k] = v5[1] + (k-1)*v5[2]
+ sum(s=3, k-1, v5[s]));
v5 = v2;
v4[j] = v2[1] + j*v2[2]
+ sum(s=3, j, v2[s]));
if(i < #v1,
v3 = vector(v1[i+1]+1, j,
v4[j+v1[i]-v1[i+1]])));
vecsum(v2) + A*v2[2])
}
test(n) = a(n) == a1(n)
Is there a way to prove it?
