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

Author

Todd Simpson

Keywords

• nonn
• nice
• easy

Comments

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

Examples

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

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

Crossrefs

Cf. A001997, A001998.

Cf. A000244.

Programs

Haskell

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

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

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)

Extensions

Interpretation in terms of bending wire from Colin Mallows.