A084635 - OEIS

%I #28 Nov 23 2025 02:06:45

%S 1,1,2,4,8,17,38,86,192,419,894,1872,3864,7893,16006,32298,64960,

%T 130375,261310,523300,1047416,2095801,4192742,8386814,16775168,

%U 33552107,67106238,134214776,268432152,536867229,1073737734,2147479122,4294962304,8589929103,17179863166

%N Binomial transform of 1,0,1,0,1,1,1,...

%C Without its first term, it is the binomial transform of 1,1,1,1,2,2,2,2,2...

%C Number of binary strings of length n except those with exactly one 0 or with exactly three 0's. For example, a(6) = 38 since from the 64 strings of length 6 we subtract the 6 permutations of 011111 and the 20 permutations of 000111. - _Enrique Navarrete_, Nov 16 2025

%H G. C. Greubel, <a href="/A084635/b084635.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (6,-14,16,-9,2).

%F a(n) = 2^n - n*(n^2 - 3*n + 8)/6.

%F a(n) = 1 + C(n,2) + Sum_{k=4..n} C(n,k).

%F O.g.f.: (1-5*x+10*x^2-10*x^3+5*x^4)/((1-x)^4*(1-2*x)). - _R. J. Mathar_, Apr 02 2008

%F a(n) = A000225(n) - (n-1) - binomial(n,3). - _G. C. Greubel_, Mar 19 2023

%F From _Elmo R. Oliveira_, Nov 14 2025: (Start)

%F E.g.f.: exp(x)*(exp(x) - (x + x^3/6)).

%F a(n) = 6*a(n-1) - 14*a(n-2) + 16*a(n-3) - 9*a(n-4) + 2*a(n-5). (End)

%F a(n) = 2^n - A000125(n-1). - _Enrique Navarrete_, Nov 16 2025

%t Table[2^n -n -Binomial[n,3], {n,0,50}] (* _G. C. Greubel_, Mar 19 2023 *)

%o (Magma) [2^n -n*(n^2-3*n+8)/6: n in [0..50]]; // _G. C. Greubel_, Mar 19 2023

%o (SageMath) [2^n -n*(n^2-3*n+8)/6 for n in range(51)] # _G. C. Greubel_, Mar 19 2023

%Y Cf. A000125, A000225, A000325, A084634.

%K easy,nonn

%O 0,3

%A _Paul Barry_, Jun 06 2003