A060351 - OEIS

%I #88 Jan 07 2025 01:59:45

%S 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 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 10,26,35,19,10,14,5,1,1

%N 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 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 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 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 I. Niven, A combinatorial problem of finite sequences, Nieuw Arch. Wisk. (3) 16 (1968), 116-123.

%H Alois P. Heinz, <a href="/A060351/b060351.txt">Rows n = 0..14, flattened</a> (rows n=1..12 from Wouter Meeussen)

%H 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 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 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 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 {n+1,2*k} + {n+1,2*k+1} = (n+1)*{n,k},

%F {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 Sum_{i=0..2^r-1} {n,i} = n*(n-1)*...*(n-r+1).

%F 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 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 Many other equalities, recursions and unequalities can be found in Shevelev and Shevelev-Spilker references. - _Vladimir Shevelev_, Feb 13 2014

%e Interpreted as a triangle:

%e   1;

%e   1;

%e   1, 1;

%e   1, 2, 2, 1;

%e   1, 3, 5, 3, 3, 5, 3, 1;

%e   1, 4, 9, 6, 9, 16, 11, 4, 4, 11, 16, 9, 6, 9, 4, 1;

%e   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   ...

%e From _Vladimir Shevelev_, Feb 13 2014: (Start)

%e Consider {4,2} (see comments). k=010 (4-1 binary digits).

%e 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 Over rows, the sequence has the form:

%e   {0,0}

%e   {1,0}

%e   {2,0} {2,1}

%e   {3,0} {3,1} {3,2} {3,3}

%e   {4,0} {4,1} {4,2} {4,3} {4,4} {4,5} {4,6} {4,7}

%e   ...

%e such that the i-th row contains ceiling(2^(i-1)) entries with row sum i!, i>=0.

%e (End)

%e 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 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 # second Maple program:

%p b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,

%p       add(b(u-j, o+j-1, t+1)*x^floor(2^(t-1)), j=1..u)+

%p       add(b(u+j-1, o-j, t+1), j=1..o)))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):

%p seq(T(n), n=0..7);  # _Alois P. Heinz_, Sep 08 2020

%p # third Maple program:

%p b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0),

%p      `if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u),

%p       add(b(u+j-1, o-j, iquo(t, 2)), j=1..o)))

%p     end:

%p T:= (n, k)-> b(n, 0, 2*k):

%p seq(seq(T(n, k), k=0..ceil(2^(n-1))-1), n=0..7);  # _Alois P. Heinz_, Sep 12 2020

%t <<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 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 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 Row sums give A000142.

%Y Row lengths give A011782(n).

%Y T(n,n) gives A335308.

%Y Cf. A060350, A291902, A291903, A334622, A334623.

%K easy,base,nonn,look,tabf,changed

%O 0,6

%A _Mike Zabrocki_, Mar 31 2001

%E Definition corrected by Julian Gilbey, Jul 26 2007

%E T(0,0)=1 prepended by _Alois P. Heinz_, Sep 08 2020