cp's OEIS Frontend

A329369 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)...b(1)b(0) (0 <= k < m-1) is the binary expansion of n.

%I A329369 #224 Jun 25 2025 19:49:11
%S A329369 1,1,3,1,7,3,7,1,15,7,17,3,31,7,15,1,31,15,37,7,69,17,37,3,115,31,69,
%T A329369 7,115,15,31,1,63,31,77,15,145,37,81,7,245,69,155,17,261,37,77,3,391,
%U A329369 115,261,31,445,69,145,7,675,115,245,15,391,31,63,1,127,63
%N A329369 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)...b(1)b(0) (0 <= k < m-1) is the binary expansion of n.
%C A329369 Another version of A152884.
%C A329369 The excedance set of a permutation p of {1,2,...,m} is the set of indices i such that p(i) > i; it is a subset of {1,2,...,m-1}.
%C A329369 Great work on this subject was done by R. Ehrenborg and E. Steingrimsson, so most of the formulas given below are just their results translated into the language of the sequences which are related to the binary expansion of n.
%C A329369 Conjecture 1: equivalently, number of open tours by a biased rook on a specific f(n) X 1 board, which ends on a white cell, where f(n) = A070941(n) = floor(log_2(2n)) + 1 and cells are colored white or black according to the binary representation of 2n. A cell is colored white if the binary digit is 0 and a cell is colored black if the binary digit is 1. A biased rook on a white cell moves only to the left and otherwise moves only to the right. - _Mikhail Kurkov_, May 18 2021
%C A329369 Conjecture 2: this sequence is an inverse modulo 2 binomial transform of A284005. - _Mikhail Kurkov_, Dec 15 2021
%H A329369 Mikhail Kurkov, <a href="/A329369/b329369.txt">Table of n, a(n) for n = 0..8191</a>
%H A329369 Max Alekseyev, <a href="https://mathoverflow.net/a/474668/231922">Recursion for the sum with Stirling numbers of both kinds</a>, answer to question on MathOverflow (2024).
%H A329369 R. Ehrenborg and E. Steingrimsson, <a href="http://dx.doi.org/10.1006/aama.1999.0671">The excedance set of a permutation</a>, Advances in Appl. Math., 24, 284-299, 2000.
%H A329369 Peter J. Taylor, <a href="https://mathoverflow.net/a/470752/231922">Correctness of the algorithm for the A329369, A347205 and related sequences</a>, answer to question on MathOverflow (2024).
%F A329369 a(2n+1) = a(n) for n >= 0.
%F A329369 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).
%F A329369 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).
%F A329369 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).
%F A329369 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)).
%F A329369 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))).
%F A329369 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.
%F A329369 Sum_{k=0..2^n-1} a(k) = (n+1)! for n >= 0.
%F A329369 a((4^n-1)/3) = A110501(n+1) for n >= 0.
%F A329369 a(2^2*(2^n-1)) = A091344(n+1),
%F A329369 a(2^3*(2^n-1)) = A091347(n+1),
%F A329369 a(2^4*(2^n-1)) = A091348(n+1).
%F A329369 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).
%F A329369 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
%F A329369 From _Mikhail Kurkov_, Jan 23 2023: (Start)
%F A329369 The formulas below are not related to R. Ehrenborg's and E. Steingrimsson's work.
%F A329369 Conjecture 3: a(n) = A357990(n, 1) for n >= 0.
%F A329369 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).
%F A329369 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)
%F A329369 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
%F A329369 From _Mikhail Kurkov_, Jul 10 2024: (Start)
%F A329369 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.
%F A329369 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)).
%F A329369 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)].
%F A329369 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).
%F A329369 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).
%F A329369 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.
%F A329369 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).
%F A329369 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).
%F A329369 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).
%F A329369 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.
%F A329369 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).
%F A329369 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)
%F A329369 From _Mikhail Kurkov_, Jan 27 2025: (Start)
%F A329369 The formulas below are not related to R. Ehrenborg's and E. Steingrimsson's work.
%F A329369 Conjecture 7: A008292(n+1,k+1) = Sum_{i=0..2^n-1} [A000120(i) = k]*a(i) for n >= 0, k >= 0.
%F A329369 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.
%F A329369 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).
%F A329369 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).
%F A329369 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)
%F A329369 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
%e A329369 a(1) = 1 because the 1st excedance set is {m-1} and the permutations of {1,2,...,m} with such excedance set are 21, 132, 1243, 12354 and so on, i.e., for a given m we always have 1 permutation.
%e A329369 a(2) = 3 because the 2nd excedance set is {m-2} and the permutations of {1,2,...,m} with such excedance set are 213, 312, 321, 1324, 1423, 1432, 12435, 12534, 12543 and so on, i.e., for a given m we always have 3 permutations.
%e A329369 a(3) = 1 because the 3rd excedance set is {m-2, m-1} and the permutations of {1,2,...,m} with such excedance set are 231, 1342, 12453 and so on, i.e., for a given m we always have 1 permutation.
%p A329369 g:= proc(n) option remember;  2^padic[ordp](n, 2) end:
%p A329369 a:= proc(n) option remember; `if`(n=0, 1, (h-> a(h)+
%p A329369      `if`(n::odd, 0, (t-> a(h-t)+a(n-t))(g(h))))(iquo(n, 2)))
%p A329369     end:
%p A329369 seq(a(n), n=0..100);  # _Alois P. Heinz_, Jan 30 2023
%t A329369 a[n_] := a[n] = Which[n == 0, 1, OddQ[n], a[(n-1)/2], True, a[n/2] + a[n/2 - 2^IntegerExponent[n/2, 2]] + a[n - 2^IntegerExponent[n/2, 2]]];
%t A329369 a /@ Range[0, 65] (* _Jean-François Alcover_, Feb 13 2020 *)
%o A329369 (PARI) upto(n) = my(A, v1); v1 = vector(n+1, i, 0); v1[1] = 1; for(i=1, n, v1[i+1] = v1[i\2+1] + if(i%2, 0, A = 1 << valuation(i/2, 2); v1[i/2-A+1] + v1[i-A+1])); v1 \\ _Mikhail Kurkov_, Jun 06 2024
%Y A329369 Cf. A000120, A000523, A001511, A007814, A008292, A023416, A036987, A053645, A062253, A062254, A062255, A063250, A080791, A091344, A091347, A091348, A110501, A136126, A152884 (lexicographic order), A173018, A329718, A344902, A344947, A357990, A358612, A373183, A379817.
%Y A329369 Similar recurrences: A006014, A124758, A217924, A243499, A284005, A290615, A341392, A347204, A347205.
%Y A329369 Cf. A360288.
%K A329369 nonn,base,look
%O A329369 0,3
%A A329369 _Mikhail Kurkov_, Nov 12 2019