A008860 a(n) = Sum_{k=0..7} binomial(n,k).

1, 2, 4, 8, 16, 32, 64, 128, 255, 502, 968, 1816, 3302, 5812, 9908, 16384, 26333, 41226, 63004, 94184, 137980, 198440, 280600, 390656, 536155, 726206, 971712, 1285624, 1683218, 2182396, 2804012, 3572224, 4514873, 5663890, 7055732

Offset: 0

Author

N. J. A. Sloane and R. K. Guy

Keywords

• nonn
• easy

Comments

This is a general comment about sequences: A000012, A000027, A000124, A000125, A000127, A006261, A008859, this sequence, A008861, A008862, A008863. Let j in {1, 2, ..., 11} index these 11 sequences respective to their order above. Then a(n) in each sequence is the number of compositions of (n+1) into j or fewer parts. From this we see that the ordinary generating function for each sequence is Sum_{i=0..j-1} x^i/(1-x)^(i+1). - Geoffrey Critzer, Jan 19 2009

a(n) is the maximal number of regions in 7-space formed by n-1 6-dimensional hypercubes. Also the number of binary words of length n matching the regular expression 1*0*1*0*1*0*1*0*. A000124, A000125, A000127, A006261, A008859 count binary words of the form 0*1*0*, 1*0*1*0*, 0*1*0*1*0*, 1*0*1*0*1*0*, and 0*1*0*1*0*1*0* respectively. - Manfred Scheucher, Jun 22 2023

Examples

			a(8)=255 because there are 255 compositions of 9 into eight or fewer parts. - _Geoffrey Critzer_, Jan 23 2009
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Ângela Mestre and José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
• Index entries for linear recurrences with constant coefficients, signature (8,-28,56,-70,56,-28,8,-1).

Crossrefs

Cf. A008859, A008861, A008862, A008863, A006261, A000127.

Cf. A007318, A219531.

Programs

GAP

List([0..40], n-> Sum([0..7], k-> Binomial(n,k)) ); # G. C. Greubel, Sep 13 2019

Haskell

a008860 = sum . take 8 . a007318_row  -- Reinhard Zumkeller, Nov 24 2012

Magma

[&+[Binomial(n, k): k in [0..7]]: n in [0..55]]; // Vincenzo Librandi, May 20 2019

Maple

seq(sum(binomial(n,j), j=0..7), n=0..40); # G. C. Greubel, Sep 13 2019

Mathematica

CoefficientList[Series[(1-6x+16x^2-24x^3+22x^4-12x^5+4x^6)/(1-x)^8, {x, 0, 34}], x] (* Georg Fischer, May 19 2019 *)
Sum[Binomial[Range[41]-1, j-1], {j,8}] (* G. C. Greubel, Sep 13 2019 *)

PARI

a(n)=(n+1)*(n^6-15*n^5+127*n^4-477*n^3+1576*n^2-1212*n+5040)/5040 \\ Charles R Greathouse IV, Dec 07 2011

Sage

[binomial(n,1)+binomial(n,3)+binomial(n,5)+binomial(n,7) for n in range(1, 36)] # Zerinvary Lajos, May 17 2009

Sage

[sum(binomial(n,k) for k in (0..7)) for n in (0..40)] # G. C. Greubel, Sep 13 2019

Formula

a(n) = Sum_{k=1..4} binomial(n+1, 2k-1) = (n^6 - 14*n^5 + 112*n^4 - 350*n^3 + 1099*n^2 + 364*n + 3828)*n/5040 + 1. [Len Smiley's formula for A006261, copied by Frank Ellermann]

G.f.: (1 - 6*x + 16*x^2 - 24*x^3 + 22*x^4 - 12*x^5 + 4*x^6)/(1-x)^8. - Geoffrey Critzer, Jan 19 2009 [Corrected by Georg Fischer, May 19 2019]