A335308 -id:A335308 - cp's OEIS frontend

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 5, 8, 1, 1, 1, 1, 2, 6, 17, 16, 1, 1, 1, 1, 2, 6, 21, 70, 32, 1, 1, 1, 1, 2, 6, 19, 90, 349, 64, 1, 1, 1, 1, 2, 6, 21, 70, 450, 2017, 128, 1, 1, 1, 1, 2, 6, 23, 90, 331, 2619, 13358, 256, 1, 1

Offset: 0

Alois P. Heinz, May 22 2014

			A(4,5) = 19 because there are 4! = 24 permutations of {1,2,3,4} and only 5 of them do not avoid the consecutive step pattern up, down, up given by the binary expansion of 5 = 101_2: (1,3,2,4), (1,4,2,3), (2,3,1,4), (2,4,1,3), (3,4,1,2).
Square array A(n,k) begins:
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   2,     2,     2,     2,     2,     2,     2, ...
  1, 1,   4,     5,     6,     6,     6,     6,     6, ...
  1, 1,   8,    17,    21,    19,    21,    23,    24, ...
  1, 1,  16,    70,    90,    70,    90,   111,   116, ...
  1, 1,  32,   349,   450,   331,   450,   642,   672, ...
  1, 1,  64,  2017,  2619,  1863,  2619,  4326,  4536, ...
  1, 1, 128, 13358, 17334, 11637, 17334, 33333, 34944, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns give: 0, 1: A000012, 2: A011782, 3: A049774, 4, 6: A177479, 5: A177477, 7: A117158, 8, 14: A177518, 9: A177519, 10: A177520, 11, 13: A177521, 12: A177522, 15: A177523, 16, 30: A177524, 17: A177525, 18, 22: A177526, 19, 25: A177527, 20, 26: A177528, 21: A177529, 23, 29: A177530, 24, 28: A177531, 27: A177532, 31: A177533, 32, 62: A177534, 33: A177535, 34, 46: A177536, 35, 49: A177537, 36, 54: A177538, 37, 41: A177539, 38: A177540, 39, 57: A177541, 40, 58: A177542, 42: A177543, 43, 53: A177544, 44, 50: A177545, 45: A177546, 47, 61: A177547, 48, 60: A177548, 51: A177549, 52: A177550, 55, 59: A177551, 56: A177552, 63: A177553, 127: A230051, 255: A230231, 511: A230232, 1023: A230233, 2047: A254523.
Main diagonal gives A242785.
Cf. A242783, A335308.

A:= proc(n, k) option remember; local b, m, r, h;
      if k<2 then return 1 fi;
      m:= iquo(k, 2, 'r'); h:= 2^ilog2(k);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
      `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
      end; forget(b);
      b(n, 0, 0)
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

Clear[A]; A[n_, k_] := A[n, k] = Module[{b, m, r, h}, If[k < 2, Return[1]]; {m, r} = QuotientRemainder[k, 2]; h = 2^Floor[Log[2, k]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t == m && r == 0, 0, Sum[b[u - j, o + j - 1, Mod[2*t, h]], {j, 1, u}]] + If[t == m && r == 1, 0, Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]], {j, 1, o}]]]; b[n, 0, 0]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Sep 22 2014, translated from Maple *)

A242783 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down; triangle T(n,k), n>=0, read by rows.

Original entry on oeis.org

1, 1, 2, 5, 1, 21, 3, 70, 50, 450, 270, 4326, 602, 99, 12, 1, 34944, 5376, 209863, 139714, 13303, 1573632, 1366016, 530432, 158720, 21824925, 15302031, 2715243, 74601, 302273664, 161855232, 14872704, 2854894485, 2600075865, 712988175, 59062275

Offset: 0

Alois P. Heinz, May 22 2014

Sum_{k>0} k*T(n,k) = A249249(n).

			T(7,3) = 12 because 12 permutations of {1,2,3,4,5,6,7} have exactly 3 (possibly overlapping) occurrences of the consecutive step pattern up, up, up given by the binary expansion of 7 = 111_2: (1,2,3,4,5,7,6), (1,2,3,4,6,7,5), (1,2,3,5,6,7,4), (1,2,4,5,6,7,3), (1,3,4,5,6,7,2), (2,1,3,4,5,6,7), (2,3,4,5,6,7,1), (3,1,2,4,5,6,7), (4,1,2,3,5,6,7), (5,1,2,3,4,6,7), (6,1,2,3,4,5,7), (7,1,2,3,4,5,6).
Triangle T(n,k) begins:
: n\k :       0        1       2       3  4  ...
+-----+------------------------------------
:  0  :       1;
:  1  :       1;                             [row  1 of A008292]
:  2  :       2;                             [row  2 of A008303]
:  3  :       5,       1;                    [row  3 of A162975]
:  4  :      21,       3;                    [row  4 of A242819]
:  5  :      70,      50;                    [row  5 of A227884]
:  6  :     450,     270;                    [row  6 of A242819]
:  7  :    4326,     602,     99,     12, 1; [row  7 of A220183]
:  8  :   34944,    5376;                    [row  8 of A242820]
:  9  :  209863,  139714,  13303;            [row  9 of A230695]
: 10  : 1573632, 1366016, 530432, 158720;    [row 10 of A230797]

Alois P. Heinz, Rows n = 0..130, flattened

Column k=0-10 give: A242785, A246221, A246222, A246223, A246224, A246225, A246226, A246227, A246228, A246229, A243105.
Row sums give A000142.
Cf. A242784, A249249, A295987, A335308.

T:= proc(n) option remember; local b, k, r, h;
      k:= iquo(n,2,'r'); h:= 2^ilog2(n);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, irem(2*t,   h))*`if`(r=0 and t=k, x, 1), j=1..u)+
      add(b(u+j-1, o-j, irem(2*t+1, h))*`if`(r=1 and t=k, x, 1), j=1..o)))
      end: forget(b);
      (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 0))
    end:
seq(T(n), n=0..15);

T[n_] := T[n] = Module[{b, k, r, h}, {k, r} = QuotientRemainder[n, 2]; h = 2^Floor[Log[2, n]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Expand[ Sum[b[u - j, o + j - 1, Mod[2*t, h]]*If[r == 0 && t == k, x, 1], {j, 1, u}] + Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]]*If[r == 1 && t == k, x, 1], {j, 1, o}]]]; Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Feb 20 2016, after Alois P. Heinz *)

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.

Original entry on oeis.org

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, 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, 1

Offset: 0

Mike Zabrocki, Mar 31 2001

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

			Interpreted as a triangle:
  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;
  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;
  ...
From _Vladimir Shevelev_, Feb 13 2014: (Start)
Consider {4,2} (see comments). k=010 (4-1 binary digits).
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.
Over rows, the sequence has the form:
  {0,0}
  {1,0}
  {2,0} {2,1}
  {3,0} {3,1} {3,2} {3,3}
  {4,0} {4,1} {4,2} {4,3} {4,4} {4,5} {4,6} {4,7}
  ...
such that the i-th row contains ceiling(2^(i-1)) entries with row sum i!, i>=0.
(End)
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

I. Niven, A combinatorial problem of finite sequences, Nieuw Arch. Wisk. (3) 16 (1968), 116-123.

Alois P. Heinz, Rows n = 0..14, flattened (rows n=1..12 from Wouter Meeussen)
N. G. de Bruijn, Permutations with given ups and downs, Nieuw Arch. 18 (1970), 61-65.
Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure, arXiv:0801.0072 [math.CO], 2007-2010. See remarks following Theorem 22.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1.
Vladimir Shevelev and J. Spilker, Up-down coefficients for permutations, Elem. Math. 68 (2013), 115-127.

Row sums give A000142.
Row lengths give A011782(n).
T(n,n) gives A335308.
Cf. A060350, A291902, A291903, A334622, A334623.

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);
# second Maple program:
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, t+1)*x^floor(2^(t-1)), j=1..u)+
      add(b(u+j-1, o-j, t+1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..7);  # Alois P. Heinz, Sep 08 2020
# third Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, `if`(t=0, 1, 0),
     `if`(irem(t, 2)=0, add(b(u-j, o+j-1, iquo(t, 2)), j=1..u),
      add(b(u+j-1, o-j, iquo(t, 2)), j=1..o)))
    end:
T:= (n, k)-> b(n, 0, 2*k):
seq(seq(T(n, k), k=0..ceil(2^(n-1))-1), n=0..7);  # Alois P. Heinz, Sep 12 2020

<Wouter Meeussen, Jan 30 2012 *)
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 *)
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 *)

{n+1,2*k} + {n+1,2*k+1} = (n+1)*{n,k},
{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.
Sum_{i=0..2^r-1} {n,i} = n*(n-1)*...*(n-r+1).
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.
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).
Many other equalities, recursions and unequalities can be found in Shevelev and Shevelev-Spilker references. - Vladimir Shevelev, Feb 13 2014

Definition corrected by Julian Gilbey, Jul 26 2007

T(0,0)=1 prepended by Alois P. Heinz, Sep 08 2020

A242785 Number of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

1, 1, 2, 5, 21, 70, 450, 4326, 34944, 209863, 1573632, 21824925, 302273664, 2854894485, 60269056512, 1207441809209, 19346879737625, 252773481889854, 2918333808555034, 69792946997645295, 982945842995115000, 16085109561896603059, 402131210857811703926

Offset: 0

Alois P. Heinz, May 22 2014

nonn

			a(4) = 21 because there are 4! = 24 permutations of {1,2,3,4} and only 3 of them do not avoid the consecutive step pattern up, down, down given by the binary expansion of 4 = 100_2: (1,4,3,2), (2,4,3,1), (3,4,2,1).

Alois P. Heinz, Table of n, a(n) for n = 0..150

Column k=0 of A242783.
Main diagonal of A242784.
Cf. A335308.

a:= proc(n) option remember; local b, m, r, h;
      if n<2 then return 1 fi;
      m:= iquo(n, 2, 'r'); h:= 2^ilog2(n);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
      `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
      end; forget(b);
      b(n, 0, 0)
    end:
seq(a(n), n=0..30);

a[n_] := a[n] = Module[{b, m, r, h},
     If[n < 2, Return[1]]; {m, r} = QuotientRemainder[n, 2];
     h = 2^(Length@IntegerDigits[n, 2] - 1);
     b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1,
     If[t == m && r == 0, 0,
          Sum[b[u - j, o + j - 1, Mod[2t, h]], {j, 1, u}]] +
     If[t == m && r == 1, 0,
          Sum[b[u + j - 1, o - j, Mod[2t+1, h]], {j, 1, o}]]];
     b[n, 0, 0]];
a /@ Range[0, 30] (* Jean-François Alcover, Mar 23 2021, after Alois P. Heinz *)

cp's OEIS Frontend

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A242783 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down; triangle T(n,k), n>=0, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A242785 Number of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica