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

Author

Seiichi Manyama, Jun 02 2017

Keywords

• nonn
• easy

Comments

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

Examples

			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.
		

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

Crossrefs

Cf. A001333, A233828(n-1).

Programs

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

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

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)

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

Extensions

More terms from Colin Barker, Jun 02 2017