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

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