Skip to main content
3 of 3
added 12 characters in body
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24

Representing A329369 using A358612

  • Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\dotsc,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 $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). Here

$$ \operatorname{wt}(2n+1) = \operatorname{wt}(n) + 1, \\ \operatorname{wt}(2n) = \operatorname{wt}(n), \\ \operatorname{wt}(0) = 0 $$

  • Let $T(n,k)$ be an integer coefficients (A358612) such that

$$ T(2n+1, k) = kT(n, k) + T(n, k-1), \\ T(2n, k) = kT(n, k) + T(n, k-1) - \frac{T(2n, k-1) + T(n, k-1)}{k-1}, \\ T(n, 1) = T(0, 2) = 1 $$

  • Let

$$ R(n, m) = \sum\limits_{k=1}^{\operatorname{wt}(m)+2} k!k^nT(m, k)(-1)^{\operatorname{wt}(m)-k+2} $$

I conjecture that

$$ a(2^m(2^{(k+1)(n-m+1)} + 2q + 1)) = 2^{(k+1)(n-m)}(R(m, 2^k + q) + R(m, q)) - R(m, q). $$

for $1 \leqslant m \leqslant n$, $k \geqslant 0$, $0 \leqslant q < 2^k$.

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

a(n) = 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+2; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
row(n) = my(A, v1, v2); v1 = [1, 1]; if(n == 0, v1, forstep(i=logint(n, 2), 0, -1, A = bittest(n, i); v2 = vector(#v1+A, i, 0); v2[1] = 1; for(j=2, #v2, v2[j] = j*if(j==#v1+1, 0, v1[j]) + v1[j-1] - if(A, 0, (v2[j-1] + v1[j-1])/(j-1))); v1 = v2); v1)
R(n, m) = my(v1); v1 = row(m); sum(i=1, #v1, i!*i^n*v1[i]*(-1)^(#v1-i))
test(n, k, q) = my(v1); v1 = vector(n, i, my(A = R(i, q)); a(2^i*(2^((k+1)*(n-i+1)) + 2*q + 1)) == 2^((k+1)*(n-i))*(R(i, 2^k + q) + A) - A); n == vecsum(v1)

Is there a way to prove it?

Notamathematician
  • 4.9k
  • 2
  • 11
  • 24