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

1, 1, 2, 4, 7, 14, 26, 50, 95, 181, 345, 657, 1252, 2385, 4544, 8657, 16493, 31422, 59864, 114051, 217286, 413966, 788674, 1502555, 2862617, 5453761, 10390321, 19795288, 37713313, 71850128, 136886433, 260791401, 496850954, 946583628

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

a(n) = number of compositions of n with parts in {2,1,3,5,7,9,...}. The generating function follows easily from Theorem 1.1 of the Hoggatt et al. reference. Example: a(4)= 7 because we have 22, 31, 13, 211, 121, 112, and 1111. - Emeric Deutsch, Aug 17 2016.

Diagonal sums of A054142. - Paul Barry, Jan 21 2005

Equals INVERT transform of (1, 1, 1, 0, 1, 0, 1, 0, 1, ...). - Gary W. Adamson, Apr 27 2009

Number of tilings of a 4 X 2n rectangle by 4 X 1 tetrominoes. - M. Poyraz Torcuk, Dec 10 2021

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024. See p. 18.
• V. E. Hoggatt, Jr. and Marjorie Bicknell, Palindromic compositions, Fibonacci Quart., Vol. 13(4), 1975, pp. 350-356.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 465
• Todd Mullen, On Variants of Diffusion, Dalhousie University (Halifax, NS Canada, 2020).
• Todd Mullen, Richard Nowakowski, and Danielle Cox, Counting Path Configurations in Parallel Diffusion, arXiv:2010.04750 [math.CO], 2020.
• Index entries for linear recurrences with constant coefficients, signature (1,2,0,-1).

Crossrefs

Cf. A275446.

Bisection of A003269 (odd part),

Cf. A236582, A251074, A236580.

Programs

GAP

a:=[1,1,2,4];; for n in [5..40] do a[n]:=a[n-1]+2*a[n-2]-a[n-4]; od; a; # G. C. Greubel, May 09 2019

Magma

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x^2)/( 1-x-2*x^2+x^4) )); // G. C. Greubel, May 09 2019

Maple

spec := [S,{S=Sequence(Prod(Z,Union(Z,Sequence(Prod(Z,Z)))))},unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);

Mathematica

CoefficientList[Series[(1-x^2)/(1-x-2x^2+x^4), {x, 0, 40}], x] (* or *)
Table[Length@ Flatten[Map[Permutations, DeleteCases[IntegerPartitions@ n, {_, a_, _} /; And[EvenQ@ a, a != 2]]], 1], {n, 0, 40}]  (* Michael De Vlieger, Aug 17 2016 *)
LinearRecurrence[{1,2,0,-1},{1,1,2,4},40] (* Harvey P. Dale, Apr 12 2018 *)

PARI

my(x='x+O('x^40)); Vec((1-x^2)/(1-x-2*x^2+x^4)) \\ G. C. Greubel, May 09 2019

Sage

((1-x^2)/(1-x-2*x^2+x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 09 2019

Formula

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

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

a(n) = Sum_{alpha = RootOf(1-x-2*x^2+x^4)} (1/283)*(27 + 112*alpha + 9*alpha^2 -48*alpha^3)*alpha^(-n-1).

a(n) = Sum_{k=0..floor(n/2)} binomial(2*n-3*k, k). - Paul Barry, Jan 21 2005

a(n) = A158943(n) -A158943(n-2). - R. J. Mathar, Jan 13 2023

Extensions

More terms from James Sellers, Jun 05 2000