A099425 Expansion of (1+x^2)/(1-2*x-x^2).

1, 2, 6, 14, 34, 82, 198, 478, 1154, 2786, 6726, 16238, 39202, 94642, 228486, 551614, 1331714, 3215042, 7761798, 18738638, 45239074, 109216786, 263672646, 636562078, 1536796802, 3710155682, 8957108166, 21624372014, 52205852194, 126036076402, 304278004998

Offset

0,2

Comments

Binomial transform of A094024(n+1).

a(n) is the number of matchings of the corona C'(n) of the cycle graph C(n) and the complete graph K(1); in other words, C'(n) is the graph constructed from C(n) to which for each vertex v a new vertex v' and the edge vv' is added. Example: a(3)=14 because in the graph with vertex set {A,B,C,a,b,c} and edge set {AB,AC,BC,Aa,Bb,Cc} we have the following 14 matchings: the empty set, the six singletons containing one of the edges, {Aa,BC}, {Bb,AC}, {Cc,AB}, {Aa,Bb}, {Aa,Cc}, {Bb,Cc} and {Aa,Bb,Cc}. Row sums of A102413. - Emeric Deutsch, Jan 07 2005

Apart from first term, same as A002203. - Peter Shor, May 12 2005

Equals the INVERT transform of integers with repeats. Example: a(4) = 34 = (1, 1, 2, 6, 14) dot (5, 3, 3, 1, 1) = (5 + 3 + 6 + 6 + 14) = 34.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

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

Formula

a(n) = (1+sqrt(2))^n + (1-sqrt(2))^n - 0^n see silver mean (A014176).

a(n) = Sum_{k=0..n} A000129(n+1-k)*C(1, k/2)*(1+(-1)^k)/2.

a(n) = 2*A001333(n) - 0^n.

a(n) = round((1+sqrt(2))^n). - Bruno Berselli, Feb 04 2013

G.f.: G(0) - 1, where G(k) = 1 + 1/(1 - x*(2*k-1)/(x*(2*k+1) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jul 30 2013

a(n) = A000129(n+1) + A000129(n-1). - Vladimir Kruchinin, Apr 19 2024

Maple

a:= n-> (<<0|1>, <1|2>>^n. <<2, 2>>)[1, 1]-0^n:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 26 2018

Mathematica

CoefficientList[Series[(1+x^2)/(1-2x-x^2), {x, 0, 30}], x] (* or *) LinearRecurrence[{2, 1}, {1, 2, 6}, 40] (* Harvey P. Dale, Mar 23 2020 *)

Prog

(Haskell)
a099425 = sum . a102413_row  -- Reinhard Zumkeller, Apr 15 2014

Crossrefs

Cf. A000129, A001333, A002203, A094024, A102413.

Cf. A014176 (silver mean).

Sequence in context: A208902 A018016 A182644 * A186523 A177790 A307068

Adjacent sequences: A099422 A099423 A099424 * A099426 A099427 A099428

Keyword

nonn,easy

Author

Paul Barry, Oct 15 2004

Status

approved