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,3

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

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

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

Prog

(PARI) my(x='x+O('x^40)); Vec((1-x^2)/(1-x-2*x^2+x^4)) \\ G. C. Greubel, May 09 2019
(Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (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
(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

Crossrefs

Cf. A275446.

Bisection of A003269 (odd part),

Cf. A236582, A251074, A236580.

Sequence in context: A024502 A280254 A280917 * A027988 A238859 A224960

Adjacent sequences: A052532 A052533 A052534 * A052536 A052537 A052538

Keyword

easy,nonn

Author

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

Extensions

More terms from James A. Sellers, Jun 05 2000

Status

approved