# Searching for a proof of the pattern and identification of integer coefficients for the A329369

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?