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!)
A242785 Number of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down. 4
1, 1, 2, 5, 21, 70, 450, 4326, 34944, 209863, 1573632, 21824925, 302273664, 2854894485, 60269056512, 1207441809209, 19346879737625, 252773481889854, 2918333808555034, 69792946997645295, 982945842995115000, 16085109561896603059, 402131210857811703926 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

CROSSREFS

Column k=0 of A242783.

Main diagonal of A242784.

Cf. A335308.

Sequence in context: A000941 A000131 A328041 * A228385 A152801 A062297

Adjacent sequences:  A242782 A242783 A242784 * A242786 A242787 A242788

KEYWORD

nonn

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 August 4 18:15 EDT 2021. Contains 346455 sequences. (Running on oeis4.)