login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 57
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,13

LINKS

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

EXAMPLE

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

MAPLE

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);

MATHEMATICA

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 *)

CROSSREFS

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.

Sequence in context: A293429 A201075 A131338 * A265313 A106498 A093466

Adjacent sequences:  A242781 A242782 A242783 * A242785 A242786 A242787

KEYWORD

nonn,tabl,changed

AUTHOR

Alois P. Heinz, May 22 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 20:09 EDT 2020. Contains 337374 sequences. (Running on oeis4.)