A007307 a(n) = a(n-2) + a(n-3), with a(0) = 0, a(1) = 1, a(2) = 2.

0, 1, 2, 1, 3, 3, 4, 6, 7, 10, 13, 17, 23, 30, 40, 53, 70, 93, 123, 163, 216, 286, 379, 502, 665, 881, 1167, 1546, 2048, 2713, 3594, 4761, 6307, 8355, 11068, 14662, 19423, 25730, 34085, 45153, 59815, 79238, 104968, 139053, 184206, 244021, 323259, 428227

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Also the number of maximal matchings in the (n-2)-pan graph. - Eric W. Weisstein, Dec 30 2017

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, Matching
• Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
• Eric Weisstein's World of Mathematics, Pan Graph
• Index entries for linear recurrences with constant coefficients, signature (0,1,1).

Crossrefs

Cf. A000931, A001608.

Programs

Magma

I:=[0,1,2]; [n le 3 select I[n] else Self(n-2)+Self(n-3): n in [1..50]]; // Vincenzo Librandi, Jun 09 2013

Maple

G(x):=(-1-x^3)/(-1+x^2+x^3): f[0]:=G(x): for n from 1 to 58 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n]/n!,n=1..43); # Zerinvary Lajos, Mar 27 2009
# second Maple program:
a:= n-> (<<0|1|0>, <0|0|1>, <1|1|0>>^n.<<($0..2)>>)[1$2]:
seq(a(n), n=0..60);  # Alois P. Heinz, Nov 06 2016

Mathematica

Table[- RootSum[-1 - # + #^3 &, -16 #^n - 13 #^(n + 1) + #^(n + 2) &]/23, {n, 20}] (* Eric W. Weisstein, Dec 30 2017 *)
LinearRecurrence[{0, 1, 1}, {1, 3, 3}, 20] (* Eric W. Weisstein, Dec 30 2017 *)
CoefficientList[Series[x (-1 - 3 x - 2 x^2)/(-1 + x^2 + x^3), {x, 0, 20}], x] (* Eric W. Weisstein, Dec 30 2017 *)

Formula

From Wolfdieter Lang, Jun 15 2010: (Start)

a(n) = p(n-1) + 2*p(n-2) = p(n+1) + p(n-2), with p(n):=A000931(n+3).

O.g.f: x*(1+2*x)/(1-x^2-x^3). (End)

a(n) = (A000931(n+1) + A001608(n+1))/2. - Elmo R. Oliveira, Dec 31 2022