Please see the update given below. Everything you need to know from the old version of the question are the functions $a(n), \ell(n), s(n), t(n), r(n)$.
- 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
$$ \ell(n) = \left\lfloor\log_2 n\right\rfloor, \\ \ell(0) = -1 $$
Let $s(n)$ be A090996 (i.e., number of leading $1$'s in binary expansion of $n$). Here $s(n)=k$ for $n=2^k-1$, $s(n)=s\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$ otherwise.
Let $t(n)$ be be A087734. Here
$$ t(n) = 2t\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + n\bmod 2 - [n = 2^k - 1], \\ t(0) = t(1) = 0 $$
Here square bracket denotes Iverson bracket.
- Let $r(n)$ be A279209 (i.e., length of first run of $0$'s in binary expansion of $n$).
To explain the relationship between these three sequences, it can be noted that
$$ n = t(n) + (2^{s(n)}-1)2^{r(n)+\ell(t(n))+1} $$
Here the sequences are unique as a solution with the condition that $t(n)$ is minimal.
- Let $b(n)$ be an integer sequence such that (conjecturally) it can be represented using some unknown integer coefficient $L(n, k, m)$ defined for $n > 0, 0 \leqslant k < n, 1 \leqslant m \leqslant (k+1)$, namely $b(n) = 1$ for $n=2^k-1$, $b(n) = p(r(n), s(n)+1)$ otherwise. Here $p(n, k) = kp(n-1, k) + p(n-1, k-1)$ for $n > 0, 1 < k \leqslant (s(n) + 1)$ with
$$ p(0, k) = \sum\limits_{i=1}^{k} b(t(n) + (2^{i-1} - 1)2^{\ell(t(n))+1})L(s(n), k-1, i) $$
for $1 \leqslant k \leqslant s(n)$ with $p(0, s(n)+1) = b(t(n) + (2^{s(n)} - 1)2^{\ell(t(n))+1})$ and $p(n, 1) = p(0,1)$.
- Note that (conjecturally) $L(n, k, m)$ can be represented as
$$ L(n, k, m) = \frac{(n-k)!}{(2n-k-m+1)!}\left(\prod\limits_{i=0}^{n-m+1} (m+i)\right)\left(\sum\limits_{i=0}^{n-k-1} m^iW(n-k, k+1, i+1)\right) $$
Here $W(n, k, m)$ are some unknown integer coefficients defined for $n > 0, k \geqslant 0, 1 \leqslant m \leqslant n$.
- Note that (conjecturally)
$$ W(n, k+1, n) = (2n + k)! [z^{2n+k}] \frac{(e^z-z-1)^n}{n!} $$
I conjecture that $$b(n)=a(n).$$
I also conjecture that if we change values of $b(n)$ for $n=2^k-1$ to $b(n) = a(2^m(2^k-1)+q)$, then formula for otherwise case (I mean $b(n) = p(r(n), s(n)+1)$) gives $b(n) = a(2^mn+q)$.
Finally, I conjecture that
$$ \frac{1}{(n-k)!}\sum\limits_{i=1}^{k+1} L(n,k,i)(-1)^{k-i+1} = \binom{n+k}{k} $$
Here is the PARI/GP program to check it numerically:
T(n, k) = my(A = 2*n+1, B, C, v1, v2); v1 = []; while(A > 0, B=valuation(A, 2); v1=concat(v1, B+1); A \= 2^(B+1)); v1 = Vecrev(v1); A = #v1; v2 = vector(A, i, 1); for(i=1, A-1, B = A-i; for(j=1, B, C = B-j+k+1; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
a(n) = T(n, 1)
c1(n, m, q) = my(L = if(m == 0, -1, logint(m, 2))); m + ((1 << q) - 1) << (L + n)
c2(n, m, q, k) = if(k == 0, a(c1(n, m, q)), c2(n+1, m, q, k-1) - (q-k+2)*c2(n, m, q, k-1))
c3(q, k) = if(q-k<=0, 0, my(M1, M2); M1 = matrix(k+1, k+1, i, j, c2(1, 2^(i-1), j-1, 0)); M2 = matrix(k+1, 1, i, j, c2(1, 2^(i-1), q, q-k)); M3 = matsolve(M1, M2); v1 = vector(k+1, i, 0); for(i=1, k+1, v1[i] = M3[i, 1]); v1)
s(n) = if(n==0, 0); my(b = binary(n), r = #b); for(i=2, #b, if(!b[i], return(i-1))); r
t(n) = my(A = 1 << s(n) - 1, B = 1, C = n%(A*B), D = 1 << (if(C == 0, -1, logint(C, 2)) + 1), E = (n - C)/(A*B)); while(!(B == D && E == 2^logint(E, 2)), B *= 2; C = n%(A*B); D = 1 << (if(C == 0, -1, logint(C, 2)) + 1); E = (n - C)/(A*B)); C
vv1 = vector(10, i, a(2^1000000*(2^(i-1)-1)+12345678))
vv2 = vector(10, i, vector(i, j, c3(i, j-1)))
b(n) = my(A = logint(n+1, 2)); if((n+1) == 1 << A, vv1[A+1], my(A = s(n), B = t(n), C = if(B == 0, -1, logint(B, 2)), D = 1 << (C+1), E = D*((1 << A) - 1), F = logint((n - B)/E, 2), G = b(B+E), v1); v1 = vector(A, i, b(B+D*((1 << (i-1)) - 1))); v2 = vv2[A]; for(i=1, A, v2[i] = sum(j=1, i, v1[j]*v2[i][j])); v2 = concat(v2, G); for(i=1, F, forstep(j=A+1, 2, -1, v2[j] *= j; v2[j] += v2[j-1])); v2[A+1])
test(n) = b(n) == a(2^1000000*n+12345678)
for(i = 1, 299, print(test(i)))
You can also try to print
for(i = 1, 299, print(b(i)==0))
for(i = 1, 299, print(a(2^1000000*i+12345678)==0))
separately to compare the speed. Note that memoization is not useful here since values are too big, so computing $b(n)$ using recursion is much faster.
UPD: here is a new version of the main question where I reassign some functions.
- Let $W(n, k, m)$ be an integer coefficients defined for $0 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n < 0$ or $k < 0$ such that
$$ W(n, k, m) = (k+m)W(n-1, k, m) + (n-k)W(n-1, k-1, m) + [m > 1]W(n, k, m-1), \\ W(0, 0, m) = 1 $$
For the related sequences in OEIS, see A173018, A062253, A062254, A062255.
- Let $L(n, k, m)$ be an integer coefficients defined for $n > 0, 0 \leqslant k \leqslant n, 0 \leqslant m \leqslant k$ such that
$$ L(n, k, m) = (n-k)!W(n-m, k-m, m+1) $$
- Let $b(n)$ be an integer sequence such that $b(n) = 1$ for $n=2^k-1$,
$$ \sum\limits_{i=0}^{s(n)} \frac{p(n, s(n)-i)}{i!}\sum\limits_{j=0}^{i} (s(n)-j+1)^{r(n)}\binom{i}{j}(-1)^j $$
otherwise where
$$ p(n, k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k, i) $$
for $0 \leqslant k \leqslant s(n)$.
I conjecture that if $b(n) = a(2^m(2^k-1)+q)$ for $n = 2^k - 1$, then we can recursively produce $a(2^mn+q) = b(n)$ using the otherwise case given above.
Here is the PARI/GP program to check it numerically:
T(n, k) = my(A = 2*n+1, B, C, v1, v2); v1 = []; while(A > 0, B=valuation(A, 2); v1=concat(v1, B+1); A \= 2^(B+1)); v1 = Vecrev(v1); A = #v1; v2 = vector(A, i, 1); for(i=1, A-1, B = A-i; for(j=1, B, C = B-j+k+1; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
a(n) = T(n, 1)
s(n) = my(L = logint(n, 2), A = 1 << (L+1) - n - 1); L - if(A == 0, -1, logint(A, 2))
t(n) = my(L = logint(n, 2), A = L - s(n) + 1); n - 1 << (L+1) + 1 << A
r(n) = my(A = t(n)); logint((n-A)/((1 << s(n)) - 1) >> (if(A == 0, -1, logint(A, 2)) + 1), 2)
W(n, k, m) = if(n < 0 || k < 0, 0, if(n == 0 && k == 0, 1, (k+m)*W(n-1, k, m) + (n-k)*W(n-1, k-1, m) + if(m>1, W(n, k, m-1))))
L(n, k, m) = (n-k)!*W(n-m, k-m, m+1)
b(n) = my(A = logint(n+1, 2)); if((n+1) == 1 << A, a(2^100*n+123456), sum(i=0, s(n), p(n, s(n)-i)/i!*sum(j=0, i, (s(n)-j+1)^r(n)*binomial(i, j)*(-1)^j)))
p(n, k) = sum(i=0, k, b(t(n)+(2^i-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1))*L(s(n), k, i))
test(n) = b(n) == a(2^100*n+123456)
Is there a way to prove it?
