cp's OEIS Frontend

A060351 If the binary expansion of n has k bits, let S be the subset of [k-1] such that i is in S if the i-th bit of n is a 1 (with the first bit being the least significant bit); a(n) is the number of permutations of [k] with descent set S.

%I A060351 #88 Jan 07 2025 01:59:45
%S A060351 1,1,1,1,1,2,2,1,1,3,5,3,3,5,3,1,1,4,9,6,9,16,11,4,4,11,16,9,6,9,4,1,
%T A060351 1,5,14,10,19,35,26,10,14,40,61,35,26,40,19,5,5,19,40,26,35,61,40,14,
%U A060351 10,26,35,19,10,14,5,1,1
%N A060351 If the binary expansion of n has k bits, let S be the subset of [k-1] such that i is in S if the i-th bit of n is a 1 (with the first bit being the least significant bit); a(n) is the number of permutations of [k] with descent set S.
%C A060351 a(n) is the number of permutations in the symmetric group S_k such that n = 2^(k-1) + the sum of 2^(i-1), where i is a descent of the permutation and k = number of digits in the binary expansion of n.
%C A060351 If n=4m then a(n)-a(n+1)+a(n+2)-a(n+3) = 0. This follows from Theorem 10 of my paper arXiv:0801.0072v1. E.g., a(20)-a(21)+a(22)-a(23) = 9-16+11-4 = 0. - _Vladimir Shevelev_, Jan 07 2008
%C A060351 Denote by {n,k} the number of permutations of {0,1,...n} such that the binary expansion of k with n-1 digits (the expansion is allowed to begin with 0's) indicates a fixed distribution of "up"(1) and "down"(0) points. The numbers {n,k} are called "up-down coefficients" of permutations, since they have many similar properties to binomial coefficients C(n,k) (see Shevelev et al. references). The sequence lists the rows numbers {n,k} as a triangle read by rows (see example). - _Vladimir Shevelev_, Feb 13 2014
%D A060351 I. Niven, A combinatorial problem of finite sequences, Nieuw Arch. Wisk. (3) 16 (1968), 116-123.
%H A060351 Alois P. Heinz, <a href="/A060351/b060351.txt">Rows n = 0..14, flattened</a> (rows n=1..12 from Wouter Meeussen)
%H A060351 N. G. de Bruijn, <a href="https://pure.tue.nl/ws/files/2321535/597546.pdf">Permutations with given ups and downs</a>, Nieuw Arch. 18 (1970), 61-65.
%H A060351 Vladimir Shevelev, <a href="http://arxiv.org/abs/0801.0072">On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure</a>, arXiv:0801.0072 [math.CO], 2007-2010. See remarks following Theorem 22.
%H A060351 Vladimir Shevelev, <a href="http://www.emis.de/journals/INTEGERS/papers/m1/m1.Abstract.html">The number of permutations with prescribed up-down structure as a function of two variables</a>, INTEGERS, 12 (2012), #A1.
%H A060351 Vladimir Shevelev and J. Spilker, <a href="http://dx.doi.org/10.4171/EM/229">Up-down coefficients for permutations</a>, Elem. Math. 68 (2013), 115-127.
%F A060351 {n+1,2*k} + {n+1,2*k+1} = (n+1)*{n,k},
%F A060351 {n+2,4*k} + {n+2,4*k+2} = {n+2, 4*k+1} + {n+2,4*k+1} + {n+2,4*k+3} = (n+2)*(n+1)/2 * {n,k}, etc.
%F A060351 Sum_{i=0..2^r-1} {n,i} = n*(n-1)*...*(n-r+1).
%F A060351 For n >= 1, 0 <= k < 2^(n-1), {n,k} <= {n,r_n}, where r_n=(2^n-2)/3, if n is odd, r_n=(2^n-1)/3, if n is even.
%F A060351 Equality holds iff k=r_n or 2^(n-1)-r_n-1, which corresponds the case of alternating permutations. De Bruijn mentioned that Niven knew the latter result, but he never published this statement. A proof can be found in the Shevelev and Spilker reference (Section 5).
%F A060351 Many other equalities, recursions and unequalities can be found in Shevelev and Shevelev-Spilker references. - _Vladimir Shevelev_, Feb 13 2014
%e A060351 Interpreted as a triangle:
%e A060351   1;
%e A060351   1;
%e A060351   1, 1;
%e A060351   1, 2, 2, 1;
%e A060351   1, 3, 5, 3, 3, 5, 3, 1;
%e A060351   1, 4, 9, 6, 9, 16, 11, 4, 4, 11, 16, 9, 6, 9, 4, 1;
%e A060351   1, 5, 14, 10, 19, 35, 26, 10, 14, 40, 61, 35, 26, 40, 19, 5, 5, 19, 40, 26, 35, 61, 40, 14, 10, 26, 35, 19, 10, 14, 5, 1;
%e A060351   ...
%e A060351 From _Vladimir Shevelev_, Feb 13 2014: (Start)
%e A060351 Consider {4,2} (see comments). k=010 (4-1 binary digits).
%e A060351 So {4,2} is the number of down-up-down permutations of {1,2,3,4}. We have 5 such permutations (2,1,4,3),(3,1,4,2),(3,2,4,1),(4,1,3,2) and (4,2,3,1). Thus {4,2}=5.
%e A060351 Over rows, the sequence has the form:
%e A060351   {0,0}
%e A060351   {1,0}
%e A060351   {2,0} {2,1}
%e A060351   {3,0} {3,1} {3,2} {3,3}
%e A060351   {4,0} {4,1} {4,2} {4,3} {4,4} {4,5} {4,6} {4,7}
%e A060351   ...
%e A060351 such that the i-th row contains ceiling(2^(i-1)) entries with row sum i!, i>=0.
%e A060351 (End)
%e A060351 The binary expansion of n=11 is 1011, which has k=4 digits. Of the first k-1=3 bits, starting from the least significant bit on the right, the first and second are 1, so S={1,2}. The a(11)=3 permutations of [k]={1,2,3,4} with descent set S={1,2} are {3,2,1,4}, {4,2,1,3}, and {4,3,1,2}. - _Danny Rorabaugh_, Apr 02 2015
%p A060351 ct := proc(k) option remember; local i,out,n; if k=0 then RETURN(1); fi; n := floor(evalf(log[2](k)))+1; if k=2^n or k=2^(n+1)-1 then RETURN(1); fi; out := 0; for i from 1 to n do if irem(iquo(k, 2^(i-1)), 2) = 1 and irem(iquo(2*k,2^(i-1)),2) =0 then out := out+(n-1)!/(i-1)!/(n-i)!* ct(floor(irem(k,2^(i-1))+2^(i-2)))*ct(iquo(k,2^i)); fi; od; out; end: seq(ct(i),i=0..64);
%p A060351 # second Maple program:
%p A060351 b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
%p A060351       add(b(u-j, o+j-1, t+1)*x^floor(2^(t-1)), j=1..u)+
%p A060351       add(b(u+j-1, o-j, t+1), j=1..o)))
%p A060351     end:
%p A060351 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
%p A060351 seq(T(n), n=0..7);  # _Alois P. Heinz_, Sep 08 2020
%p A060351 # third Maple program:
%p A060351 b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0),
%p A060351      `if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u),
%p A060351       add(b(u+j-1, o-j, iquo(t, 2)), j=1..o)))
%p A060351     end:
%p A060351 T:= (n, k)-> b(n, 0, 2*k):
%p A060351 seq(seq(T(n, k), k=0..ceil(2^(n-1))-1), n=0..7);  # _Alois P. Heinz_, Sep 12 2020
%t A060351 <<DiscreteMath`Combinatorica`;binDescents[perm_List]:= FromDigits[Sign[Rest[perm] - Drop[perm, -1]]/2 + 1/2, 2];Table[CoefficientList[Apply[Plus, ((Length[#1]*x^#1 & )[Flatten[Outer[binDescents[TableauxToPermutation[#1, #2]] & , {FirstLexicographicTableau[#1]}, Tableaux[#1], 1]]] & ) /@ Partitions[w], {0, 1}], x], {w, 2, 7}] (* _Wouter Meeussen_, Jan 30 2012 *)
%t A060351 upDown[n_, k_] := upDown[n, k] = Module[{t, m}, t = Flatten[ Reverse[ Position[ Reverse[ IntegerDigits[k, 2]], 1]]]; m = Length[t]; (-1)^m + Sum[upDown[t[[j]], k - 2^(t[[j]]-1)]*Binomial[n, t[[j]]], {j, 1, m}]]; Table[upDown[n, k], {n, 1, 7}, {k, 0, 2^(n-1)-1}] // Flatten (* _Jean-François Alcover_, Jul 16 2017, after _Vladimir Shevelev_ *)
%t A060351 P[n_, x_] := P[n, x] = (1/(1-x^2^(n-1)))(Product[1-x^2^k, {k, 0, (n-1)}] + Sum[Binomial[n, i] Product[1-x^2^k, {k, i, n-1}] x^2^(i-1) P[i, x], {i, 1, n-1}]) // Simplify; P[1, _] = 1; Table[CoefficientList[P[n, x], x], {n, 1, 7}] // Flatten (* _Jean-François Alcover_, Sep 06 2018, after _Vladimir Shevelev_ *)
%Y A060351 Row sums give A000142.
%Y A060351 Row lengths give A011782(n).
%Y A060351 T(n,n) gives A335308.
%Y A060351 Cf. A060350, A291902, A291903, A334622, A334623.
%K A060351 easy,base,nonn,look,tabf
%O A060351 0,6
%A A060351 _Mike Zabrocki_, Mar 31 2001
%E A060351 Definition corrected by Julian Gilbey, Jul 26 2007
%E A060351 T(0,0)=1 prepended by _Alois P. Heinz_, Sep 08 2020