A106472 Expansion of g.f. (1 - x)^2*(1 + x) / (1 - 2*x)^2.

1, 3, 7, 17, 40, 92, 208, 464, 1024, 2240, 4864, 10496, 22528, 48128, 102400, 217088, 458752, 966656, 2031616, 4259840, 8912896, 18612224, 38797312, 80740352, 167772160, 348127232, 721420288, 1493172224, 3087007744, 6375342080, 13153337344, 27111981056, 55834574848

Offset

0,2

Comments

Binomial transform of A029578(n+2). Row sums of number triangle A106471.

a(n) is the number of parts equal to 1 or 2 in all the compositions of n + 1. Example: a(2)=7 because in the compositions [3], [1,2], [2,1], and [1,1,1] we have 0 + 2 + 2 + 3 = 7 parts equal to 1 or 2. Equivalently, a(n) = Sum_{k>=0} k*A296559(n+1,k). - Emeric Deutsch, Dec 16 2017

a(n) is the number of runs of 1s of length <= 2 over all binary strings of length n+1. - Félix Balado, Jun 28 2025

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 100.

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

Formula

a(0)=1, a(1)=3, and a(n) = (3*n + 8)*2^(n-3), for n>=2. [simplified by Ralf Stephan, Nov 16 2010]

a(n) = 4*a(n-1) - 4*a(n-2) for n > 3. - Colin Barker, Dec 16 2017

E.g.f.: (exp(2*x)*(4 + 3*x) + x)/4. - Stefano Spezia, May 14 2023

Sum_{n>=0} (-1)^n/a(n) = (2^(14/3)/3)*(log(2^(1/3)-1) + 2*sqrt(3)*arccot((2^(4/3)-1)/sqrt(3))) - 2107/165. - Amiram Eldar, Feb 13 2026

Maple

1, 3, seq((3*n+8)*2^(n-3), n = 2 .. 27); # Emeric Deutsch, Dec 16 2017

Mathematica

Join[{1, 3}, LinearRecurrence[{4, -4}, {7, 17}, 30]] (* Jean-François Alcover, Dec 16 2017 *)

Prog

(PARI) my(x='x+O('x^99)); Vec((1+x)*(1-x)^2/(1-2*x)^2) \\ Altug Alkan, Dec 16 2017

Crossrefs

Cf. A029578, A106471, A296559.

Sequence in context: A147142 A298371 A367396 * A309538 A036885 A247300

Adjacent sequences: A106469 A106470 A106471 * A106473 A106474 A106475

Keyword

easy,nonn

Author

Paul Barry, May 03 2005

Status

approved