a(2n+1) = a(n) for n >= 0.
a(2n) = a(n) + a(n - 2^f(n)) + a(2n - 2^f(n)) for n > 0 with a(0) = 1 where f(n) =
A007814(n) (equivalent to proposition 2.1 at the page 286, see R. Ehrenborg and E. Steingrimsson link).
a(2^m*(2n+1)) = Sum_{k=0..m} binomial(m+1,k) a(2^k*n) = a(2^m*n) + a(2^(m-1)*(2n+1)) + a(2^(m-1)*(4n+1)) for m > 0, n >= 0 (equivalent to proposition 2.5 at the page 287, see R. Ehrenborg and E. Steingrimsson link).
a(2n) = a(2*g(n)) + a(2n - 2^h(n)) + a(2*g(n) + 2^h(n)) for n > 0 with a(0) = 1 where g(n) =
A053645(n), h(n) =
A063250(n) (equivalent to proposition 2.1 at the page 286, see R. Ehrenborg and E. Steingrimsson link).
a(2n) = 2*a(n + g(n)) + a(2*g(n)) for n > 0, floor(n/3) < 2^(floor(log_2(n))-1) (in other words, for 2^m + k where 0 <= k < 2^(m-1), m > 0) with a(0) = 1 (just a special case of the previous formula, because for 2^m + k where 0 <= k < 2^(m-1), m > 0 we have 2^h(n) = n - g(n)).
a(2n) = a(f(n,-1)) + a(f(n,0)) + a(f(n,1)) for n > 0 with a(0) = 1 where f(n,k) = 2*(f(floor(n/2),k) + n mod 2) + k*
A036987(n) for n > 1 with f(1,k) = abs(k) (equivalent to a(2n) = a(2*g(n)) + a(2n - 2^h(n)) + a(2*g(n) + 2^h(n))).
a(n) = Sum_{j=0..2^wt(n) - 1} (-1)^(wt(n) - wt(j)) Product_{k=0..wt(n) - 1} (1 + wt(floor(j/2^k)))^T(n,k) for n > 0 with a(0) = 1 where wt(n) =
A000120(n), T(n,k) = T(floor(n/2), k - n mod 2) for k > 0 with T(n,0) =
A001511(n) (equivalent to theorem 6.3 at page 296, see R. Ehrenborg and E. Steingrimsson link). Here T(n, k) - 1 for k > 0 is the length of the run of zeros between k-th pair of ones from the right side in the binary expansion of n. Conjecture 1: this formula is equivalent to inverse modulo 2 binomial transform of
A284005.
Sum_{k=0..2^n-1} a(k) = (n+1)! for n >= 0.
a((4^n-1)/3) =
A110501(n+1) for n >= 0.
More generally, a(2^m*(2^n-1)) = a(2^n*(2^m-1)) = S(n+1,m) for n >= 0, m >= 0 where S(n,m) = Sum_{k=1..n} k!*k^m*Stirling2(n,k)*(-1)^(n-k) (equivalent to proposition 6.5 at the page 297, see R. Ehrenborg and E. Steingrimsson link).
Conjecture 2: a(n) = (1 +
A023416(n))*a(g(n)) + Sum_{k=0..floor(log_2(n))-1} (1-R(n,k))*a(g(n) + 2^k*(1 - R(n,k))) for n > 1 with a(0) = 1, a(1) = 1, where g(n) =
A053645(n) and where R(n,k) = floor(n/2^k) mod 2 (at this moment this is the only formula here, which is not related to R. Ehrenborg's and E. Steingrimsson's work and arises from another definition given above, exactly conjectured definition with a biased rook). Here R(n,k) is the (k+1)-th bit from the right side in the binary expansion of n. -
Mikhail Kurkov, Jun 23 2021
The formulas below are not related to R. Ehrenborg's and E. Steingrimsson's work.
Conjecture 3: a(n) =
A357990(n, 1) for n >= 0.
Conjecture 4: a(2^m*(2k+1)) = Sum_{i=1..wt(k) + 2} i!*i^m*
A358612(k, i)*(-1)^(wt(k) - i) for m >= 0, k >= 0 where wt(n) =
A000120(n).
Conjecture 5: a(2^m*(2^n - 2^p - 1)) = Sum_{i=1..n} i!*i^m*(-1)^(n - i)*((i - p + 1)*Stirling2(n, i) - Stirling2(n - p, i - p) + Sum_{j=0..p-2} (p - j - 1)*Stirling2(n - p, i - j)/j! Sum_{k=0..j} (i - k)^p*binomial(j, k)*(-1)^k) for n > 2, m >= 0, 0 < p < n - 1. Here we consider that Stirling2(n, k) = 0 for n >= 0, k < 0. (End)
Conjecture 6: a(2^m*n + q) = Sum_{i=
A001511(n+1)..
A000120(n)+1}
A373183(n, i)*a(2^m*(2^(i-1)-1) + q) for n >= 0, m >= 0, q >= 0. Note that this formula is recursive for n != 2^k - 1. Also, it is not related to R. Ehrenborg's and E. Steingrimsson's work. -
Mikhail Kurkov, Jun 05 2024
a(2^m*(2^n*(2k+1) - 1)) = Sum_{i=1..m+1} a(2^i*k)*(-1)^(m-i+1)*Sum_{j=i..m+1} j^n*Stirling1(j, i)*Stirling2(m+1, j) for m >= 0, n >= 0, k >= 0 with a(0) = 1.
Proof: start with a(2^m*(2n+1)) = Sum_{k=0..m} binomial(m+1,k) a(2^k*n) given above and rewrite it as a(2^m*(2^n*(2k+1) - 1)) = Sum_{i=0..m} binomial(m+1, i) a(2^i*(2^(n-1)*(2k+1) - 1)).
Then conjecture that a(2^m*(2^n*(2k+1) - 1)) = Sum_{i=1..m+1} a(2^i*k)*f(n, m, i). From that it is obvious that f(0, m, i) = [i = (m+1)].
After that use a(2^m*(2^n*(2k+1) - 1)) = Sum_{i=0..m} binomial(m+1, i) Sum_{j=1..i+1} a(2^j*k)*f(n-1, i, j) = Sum_{i=1..m+1} a(2^i*k) Sum_{j=i-1..m} binomial(m+1, j)*f(n-1, j, i). From that it is obvious that f(n, m, i) = Sum_{j=i-1..m} binomial(m+1, j)*f(n-1, j, i).
Finally, all we need is to show that basic conditions and recurrence for f(n, m, i) gives f(n, m, i) = (-1)^(m-i+1)*Sum_{j=i..m+1} j^n*Stirling1(j, i)*Stirling2(m+1, j) (see
Max Alekseyev link).
a(2^m*(2k+1)) = a(2^(m-1)*k) + (m+1)*a(2^m*k) + Sum_{i=1..m-1} a(2^m*k + 2^i) for m > 0, k >= 0.
Proof: start with a(2^(m+1)*(2k+1)) = a(2^m*k) + (m+2)*a(2^(m+1)*k) + Sum_{i=1..m} a(2^(m+1)*k + 2^i).
Then use a(2^m*(4k+1)) = a(2^m*k) + (m+1)*a(2^(m+1)*k) + Sum_{i=1..m-1} a(2^(m+1)*k + 2^i).
From that we get a(2^(m+1)*(2k+1)) - a(2^m*k) - (m+2)*a(2^(m+1)*k) - a(2^(m+1)*k + 2^m) = a(2^m*(4k+1)) - a(2^m*k) - (m+1)*a(2^(m+1)*k).
Finally, a(2^(m+1)*(2k+1)) = a(2^(m+1)*k) + a(2^m*(2*k+1)) + a(2^m*(4k+1)) which agrees with the a(2^m*(2n+1)) = a(2^m*n) + a(2^(m-1)*(2n+1)) + a(2^(m-1)*(4n+1)) given above.
This formula can be considered as an alternative to a(2^m*(2n+1)) = Sum_{k=0..m} binomial(m+1,k) a(2^k*n). There are algorithms for both these formulas that allow you to calculate them without recursion. However, even though it is necessary to calculate binomial coefficients in the mentioned formula, the triple-looped algorithm for it still works faster (see
Peter J. Taylor link).
It looks like you can also change v2 in the mentioned algorithm to vector with elements a(2^m*(2^(i+
A007814(n+1)-1)-1) + q) to get a(2^m*n + q) instead of a(n). This may have common causes with formula that uses
A373183 given above. (End)
The formulas below are not related to R. Ehrenborg's and E. Steingrimsson's work.
Conjecture 7:
A008292(n+1,k+1) = Sum_{i=0..2^n-1} [
A000120(i) = k]*a(i) for n >= 0, k >= 0.
Conjecture 8: a(2^m*(2^n*(2k+1)-1)) = Sum_{i=0..m} Sum_{j=0..m-i} Sum_{q=0..i} binomial(m-i,j)*(m-j+1)^n*a(2^(q+1)*k)*L(m,i,q)*(-1)^j for m >= 0, n > 0, k >= 0 where L(n,k,m) = W(n-m,k-m,m+1) for n > 0, 0 <= k < n, 0 <= m <= k and where 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) for 0 <= k < n, m > 0 with W(0,0,m) = 1, W(n,k,m) = 0 for n < 0 or k < 0.
In particular, W(n, k, 1) =
A173018(n, k), W(n, k, 2) =
A062253(n, k), W(n, k, 3) =
A062254(n, k) and W(n, k, 4) =
A062255(n, k).
Conjecture 9: a(n) = b(n,wt(n)) for n >= 0 where b(2n+1,k) = b(n,k) + (wt(n)-k+2)*b(n,k-1), b(2n,k) = (wt(n)-k+1)*b(2n+1,k) for n > 0, k > 0 with b(n,0) =
A341392(n) for n >= 0, b(0,k) = 0 for k > 0 and where wt(n) =
A000120(n) (see
A379817).
More generally, a(2^m*(2k+1)) = ((m+1)!)^2*b(k,wt(k)-m) - Sum_{j=1..m} Stirling1(m+2,j+1)*a(2^(j-1)*(2k+1)) for m >= 0, k >= 0. Here we also consider that b(n,k) = 0 for k < 0. (End)
Conjecture 10: if we change b(n,0) =
A341392(n) given above to b(n,0) =
A341392(n)*x^n, then nonzero terms of the resulting polynomials for b(n,wt(n)) form c(n,k) such that a(n) = Sum_{k=0..
A080791(n)} c(n,k) for n >= 0 where c(n,k) = (Product_{i=0..k-1} (1 + 1/
A000120(floor(n/2^(
A000523(n)-i))))) * Sum_{j=max{0,k-
A080791(n)+
A080791(
A053645(n))}..
A080791(
A053645(n))} c(
A053645(n),j) for n > 0, k >= 0 with c(0,0) = 1, c(0,k) = 0 for k > 0. -
Mikhail Kurkov, Jun 19 2025
Comments