login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A208900 Number of bitstrings of length n which (if having two or more runs) the last two runs have different lengths. 5

%I

%S 2,2,6,10,26,50,114,226,482,962,1986,3970,8066,16130,32514,65026,

%T 130562,261122,523266,1046530,2095106,4190210,8384514,16769026,

%U 33546242,67092482,134201346,268402690,536838146,1073676290,2147418114,4294836226,8589803522

%N Number of bitstrings of length n which (if having two or more runs) the last two runs have different lengths.

%C A run is a maximal subsequence of (possibly just one) identical bits.

%H Vincenzo Librandi, <a href="/A208900/b208900.txt">Table of n, a(n) for n = 1..1000</a>

%H Aruna Gabhe, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.119.02.161">Problem 11623</a>, Am. Math. Monthly 119 (2012) 161.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-6,4).

%F a(n) = 2^n + 2 - 2^(floor(n/2)+1).

%F a(n) = 3*a(n-1) - 6*a(n-3) + 4*a(n-4), a(0) = 2, a(1) = 2, a(2) = 6, a(3) = 10.

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

%e If n=3 the bitstrings where the last runs have different lengths are 111,000,100,011,110,001 so a(3) = 6.

%t Table[2 + 2^n - 2^(Floor[n/2] + 1) , {n, 1, 40}]

%t LinearRecurrence[{3, 0, -6, 4}, {2, 2, 6, 10}, 40]

%Y Cf. A056453, A208901, A208902, A208903.

%K nonn,easy

%O 1,1

%A _David Nacin_, Mar 03 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 05:28 EDT 2021. Contains 348141 sequences. (Running on oeis4.)