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!)
A287898 Number of ways to go up and down n stairs, with fewer than 4 stairs at a time, stepping on each stair at least once. 1
1, 3, 9, 27, 79, 233, 687, 2025, 5969, 17595, 51865, 152883, 450655, 1328401, 3915743, 11542481, 34023905, 100292659, 295633833, 871443275, 2568763439, 7571973753, 22319994767, 65792907193, 193938514865, 571674807403, 1685132453689, 4967284459107 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Also the number of words using 0, 1 and 2 which have n-1 length and don't appear 0000 or 1111.

LINKS

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (2,2,2,1).

FORMULA

a(n+4) = 2*a(n+3) + 2*a(n+2) + 2*a(n+1) + a(n).

G.f.: x*(1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3 - x^4). - Colin Barker, Jun 02 2017

EXAMPLE

n = 2

0->1->2->0 (0), 0->2->1->0 (1), 0->1->2->1->0 (2). So a(2) = 3.

n = 3

0->1->2->3->0    (00), 0->1->3->2->0    (01), 0->1->2->3->2->0    (02),

0->2->3->1->0    (10), 0->3->2->1->0    (11), 0->2->3->2->1->0    (12),

0->1->2->3->1->0 (20), 0->1->3->2->1->0 (21), 0->1->2->3->2->1->0 (22). So a(3) = 9.

...

n = 5

0->1->2->3->5->4->0 (0001), ... , 0->4->5->3->2->1->0 (1110),

0->4->5->4->3->2->1->0 (1112), ... , 0->1->2->3->4->5->4->3->2->1->0 (2222).

So a(5) = 81 - 2 = 79.

MATHEMATICA

CoefficientList[Series[(1 + x)*(1 + x^2)/(1 - 2*x - 2*x^2 - 2*x^3 - x^4), {x, 0, 30}], x] (* Wesley Ivan Hurt, Jun 02 2017 *)

PROG

(Ruby)

def f(ary, n)

  return false if ary.size < n

  a = ary[-1]

  ary[-n..-2].all?{|i| i == a}

end

def A(k, n)

  f_ary = [[]]

  ary = [1]

  (n - 1).times{

    b_ary = []

    f_ary.each{|i|

      i0, i1, i2 = i + [0], i + [1], i + [2]

      b_ary << i0 if !f(i0, k)

      b_ary << i1 if !f(i1, k)

      b_ary << i2

    }

    f_ary = b_ary

    ary << f_ary.size

  }

  ary

end

p A(4, 10)

(PARI) Vec(x*(1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3 - x^4) + O(x^30)) \\ Colin Barker, Jun 02 2017

CROSSREFS

Cf. A001333, A233828(n-1).

Sequence in context: A077827 A299108 A304067 * A129770 A134396 A059502

Adjacent sequences:  A287895 A287896 A287897 * A287899 A287900 A287901

KEYWORD

nonn,easy

AUTHOR

Seiichi Manyama, Jun 02 2017

EXTENSIONS

More terms from Colin Barker, Jun 02 2017

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 April 10 08:09 EDT 2021. Contains 342845 sequences. (Running on oeis4.)