A001444 Bending a piece of wire of length n+1 (configurations that can only be brought into coincidence by turning the figure over are counted as different).

1, 2, 6, 15, 45, 126, 378, 1107, 3321, 9882, 29646, 88695, 266085, 797526, 2392578, 7175547, 21526641, 64573362, 193720086, 581140575, 1743421725, 5230206126, 15690618378, 47071677987, 141215033961, 423644570442, 1270933711326, 3812799539655, 11438398618965

Offset

0,2

Comments

The wire stays in the plane, there are n bends, each is R,L or O.

References

Todd Andrew Simpson, "Combinatorial Proofs and Generalizations of Weyl's Denominator Formula", Ph. D. Dissertation, Penn State University, 1994.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Index entries for sequences obtained by enumerating foldings

Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

Formula

a(n) = (3^n + 3^floor(n/2))/2.

G.f.: G(0) where G(k) = 1 + x*(3*3^k + 1)*(1 + 3*x*G(k+1))/(1 + 3^k). - Sergei N. Gladkovskii, Dec 13 2011 [Edited by Michael Somos, Sep 09 2013]

E.g.f. E(x) = (exp(3*x)+cosh(x*sqrt(3))+sinh(x*sqrt(3))/sqrt(3))/2 = G(0); G(k) = 1 + x*(3*3^k+1)/((2*k+1)*(1+3^k) - 3*x*(2*k+1)*(1+3^k)/(3*x + (2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 13 2011

From Colin Barker, Apr 02 2012: (Start)

a(n) = 3*a(n-1) + 3*a(n-2) - 9*a(n-3).

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

Example

There are 2 ways to bend a piece of wire of length 2 (bend it or not).
G.f. = 1 + 2*x + 6*x^2 + 15*x^3 + 45*x^4 + 126*x^5 + 378*x^6 + ...

Maple

f := n->(3^floor(n/2)+3^n)/2;

Mathematica

CoefficientList[Series[(1-x-3*x^2)/((1-3*x)*(1-3*x^2)), {x, 0, 30}], x] (* Vincenzo Librandi, Apr 15 2012 *)
LinearRecurrence[{3, 3, -9}, {1, 2, 6}, 40] (* Harvey P. Dale, Dec 30 2012 *)

Prog

(Haskell)
a001444 n = div (3 ^ n + 3 ^ (div n 2)) 2
-- Reinhard Zumkeller, Jun 30 2013

Crossrefs

Cf. A001997, A001998.

Cf. A000244.

Sequence in context: A052870 A293743 A360274 * A293744 A293745 A293746

Adjacent sequences: A001441 A001442 A001443 * A001445 A001446 A001447

Keyword

nonn,nice,easy

Author

Todd Simpson

Extensions

Interpretation in terms of bending wire from Colin Mallows.

Status

approved