|
| |
|
|
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.
|
|
23
|
|
|
|
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, 7, 115, 15, 31, 1, 63, 31, 77, 15, 145, 37, 81, 7, 245, 69, 155, 17, 261, 37, 77, 3, 391, 115, 261, 31, 445, 69, 145, 7, 675, 115, 245, 15, 391, 31, 63, 1, 127, 63
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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}.
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.
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 [verification needed]
Inverse modulo 2 binomial transform of A284005. Combinatorial interpretation: note that binomial(n, k) mod 2 = 1 if k belongs to A295989(n, j) which is all possible numbers resulting from changing ones to zeros in binary expansion of n. Write out all open tours by a biased rook from A284005 (see the "Comments on A284005" for definition) for those numbers, exclude tours which have a duplicate and you will get open tours by a biased rook from A329369. - Mikhail Kurkov, Dec 15 2021 [verification needed]
|
|
|
LINKS
|
|
|
|
FORMULA
|
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. Also 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).
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 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 [verification needed]
The formulas below are not related to R. Ehrenborg's and E. Steingrimsson's work.
a(n) = A357990(n, 1) for n >= 0. With some simplifications, this is possibly the best way to compute a(n) using only wt(n+1)*(wt(n+1) - 1)/2 operations where wt(n) = A000120(n).
a(n) = Sum_{k=1..wt(n) + 2} k!*A358612(n, k)*(-1)^(wt(n) - k + 2) for n >= 0 where wt(n) = A000120(n).
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) [verification needed]
|
|
|
EXAMPLE
|
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.
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.
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.
|
|
|
MAPLE
|
g:= proc(n) option remember; 2^padic[ordp](n, 2) end:
a:= proc(n) option remember; `if`(n=0, 1, (h-> a(h)+
`if`(n::odd, 0, (t-> a(h-t)+a(n-t))(g(h))))(iquo(n, 2)))
end:
|
|
|
MATHEMATICA
|
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]]];
|
|
|
PROG
|
(PARI) a(n)=my(n=(n+1)/2^valuation(n+1, 2)-1, wt=hammingweight(n), v=[], A=0); if(n==0, 1, for(i=0, logint(n, 2), if(bittest(n, i), v=concat(v, A); A=0, A++)); sum(j=0, 2^wt-1, (-1)^(wt - hammingweight(j))*prod(k=0, wt-1, (1 + hammingweight(j\2^k))^(v[k+1] + 1)))) \\ Mikhail Kurkov, Oct 12 2022 [verification needed]
(PARI) a(n)=my(n=(n+1)/2^valuation(n+1, 2), A=n, B, C, v=[], v1); while(A>0, B=valuation(A, 2); v=concat(v, B+1); A\=2^(B+1)); v=Vecrev(v); A=#v; if(n==1, 1, v1=vector(A, i, A-i+1); for(i=1, A-1, B=A-i; for(j=1, B, C=B-j+2; v1[j]=v1[j]*C^v[B] - v1[j+1]*(C-1)^v[B])); v1[1]) \\ much faster prog \\ Mikhail Kurkov, Jan 23 2023 [verification needed]
|
|
|
CROSSREFS
|
Cf. A000120, A001511, A007814, A035327, A036987, A053645, A054429, A059893, A063250, A091344, A091347, A091348, A110501, A136126, A152884 (lexicographic order), A290255, A329718, A344902, A344947, A357990, A358612.
|
|
|
KEYWORD
|
nonn,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
