A173009 Expansion of o.g.f. x*(1 - x + x^2)/(1 -3*x +x^2 +3*x^3 -2*x^4).

0, 1, 2, 6, 13, 29, 60, 124, 251, 507, 1018, 2042, 4089, 8185, 16376, 32760, 65527, 131063, 262134, 524278, 1048565, 2097141, 4194292, 8388596, 16777203, 33554419, 67108850, 134217714, 268435441, 536870897

Offset: 1

Author

Thomas Wieder, Feb 07 2010

Keywords

• nonn
• easy

Comments

The mean value m(n) = Sum_{k=0..(2^n -n-1)} k*p(n,k) of the distribution function p(n,k) = binomial(2^n-n-1, k)/2^(2^n-n-1) is 0., 0.5, 2., 5.5, 13., 28.5, 60., 123.5, 251., 506.5, 1018., 2041.5, 4089., 8184.5... We set a(n) = round(m(n)).

The half-integer sequence h(n) = 0, 1/2, 2, 11/2, 13, 57/2, 60, 247/2, 251, 1013/2, 1018, 4083/2, 4089, 16369/2, 16376, 65519/2, 65527, ... is the binomial transform of 0, 1/2, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

Crossrefs

Cf. A000295, A016031, A173010.

Programs

Magma

[Round((2^n -n-1)/2): n in [1..40]]; // G. C. Greubel, Feb 20 2021

Maple

A173009:= n-> round((2^n -n-1)/2); seq(A173009(n), n=1..40); # G. C. Greubel, Feb 20 2021

Mathematica

Table[Ceiling[(2^n-n-1)/2],{n,30}] (* or *) LinearRecurrence[{3,-1,-3,2},{0,1,2,6},30] (* Harvey P. Dale, Nov 16 2011 *)

PARI

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 2,-3,-1,3]^(n-1)*[0;1;2;6])[1,1] \\ Charles R Greathouse IV, Apr 18 2020

Sage

[round((2^n -n-1)/2) for n in (1..40)] # G. C. Greubel, Feb 20 2021

Formula

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

m(n) = (1/4)*2^n - 1/2 + m*(n-1) with m(1)=0 and a(n) = round(m(n)).

a(1)=0, a(2)=1, a(3)=2, a(4)=6, a(n) = 3*a(n-1) -a(n-2) -3*a(n-3) +2*a(n-4). - Harvey P. Dale, Nov 16 2011

a(n) = round(A000295(n)/2). - G. C. Greubel, Feb 20 2021