A266550 Independence number of the n-Mycielski graph.

1, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 12287, 24575, 49151, 98303, 196607, 393215, 786431, 1572863, 3145727, 6291455, 12582911, 25165823, 50331647, 100663295, 201326591, 402653183, 805306367, 1610612735, 3221225471, 6442450943, 12884901887

Offset: 1

Author

Eric W. Weisstein, Dec 31 2015

Keywords

• nonn
• easy

Links

• Eric Weisstein's World of Mathematics, Independence Number.
• Eric Weisstein's World of Mathematics, Mycielski Graph.
• Index entries for linear recurrences with constant coefficients, signature (3,-2).

Crossrefs

Cf. A052940, A055010, A083329, A153893.

Programs

Magma

[1,1] cat [-1+3*2^(n-3): n in [3..40]]; // Vincenzo Librandi, Jan 01 2016

Magma

I:=[1,1,2,5]; [n le 4 select I[n] else 3*Self(n-1)-2*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jan 01 2016

Mathematica

Table[Piecewise[{{-1 + 3 2^(n - 3), n > 2}}, 1], {n, 35}]
CoefficientList[Series[1 + x*(1 - x + x^2)/((1 - x)*(1 - 2*x)), {x, 0, 35}], x] (* Vincenzo Librandi, Jan 01 2016 *)

Formula

a(1) = 1, a(2) = 1; for n>2, a(n) = -1 + 3*2^(n-3) = A083329(n-2) = A055010(n-2) = A153893(n-3).

G.f.: x + x^2*(1 - x + x^2)/((1 - x)*(1 - 2*x)).

a(n) = 3*a(n-1)-2*a(n-2) for n>2. - Vincenzo Librandi, Jan 01 2016

a(n) = A052940(n-3) for n > 3. - Georg Fischer, Oct 23 2018

E.g.f.: (3*exp(2*x) - 8*exp(x) + 5 + 10*x+ 2*x^2)/8. - Stefano Spezia, Sep 14 2024