cp's OEIS Frontend

A008949 Triangle read by rows of partial sums of binomial coefficients: T(n,k) = Sum_{i=0..k} binomial(n,i) (0 <= k <= n); also dimensions of Reed-Muller codes.

%I A008949 #199 Apr 22 2025 11:06:47
%S A008949 1,1,2,1,3,4,1,4,7,8,1,5,11,15,16,1,6,16,26,31,32,1,7,22,42,57,63,64,
%T A008949 1,8,29,64,99,120,127,128,1,9,37,93,163,219,247,255,256,1,10,46,130,
%U A008949 256,382,466,502,511,512,1,11,56,176,386,638,848,968,1013,1023,1024,1,12,67,232,562,1024,1486,1816,1981,2036,2047,2048
%N A008949 Triangle read by rows of partial sums of binomial coefficients: T(n,k) = Sum_{i=0..k} binomial(n,i) (0 <= k <= n); also dimensions of Reed-Muller codes.
%C A008949 The second-left-from-middle column is A000346: T(2n+2, n) = A000346(n). - Ed Catmur (ed(AT)catmur.co.uk), Dec 09 2006
%C A008949 T(n,k) is the maximal number of regions into which n hyperplanes of co-dimension 1 divide R^k (the Cake-Without-Icing numbers). - _Rob Johnson_, Jul 27 2008
%C A008949 T(n,k) gives the number of vertices within distance k (measured along the edges) of an n-dimensional unit cube, (i.e., the number of vertices on the hypercube graph Q_n whose distance from a reference vertex is <= k). - _Robert Munafo_, Oct 26 2010
%C A008949 A triangle formed like Pascal's triangle, but with 2^n for n >= 0 on the right border instead of 1. - _Boris Putievskiy_, Aug 18 2013
%C A008949 For a closed-form formula for generalized Pascal's triangle see A228576. - _Boris Putievskiy_, Sep 04 2013
%C A008949 Consider each "1" as an apex of two sequences: the first is the set of terms in the same row as the "1", but the rightmost term in the row repeats infinitely. Example: the row (1, 4, 7, 8) becomes (1, 4, 7, 8, 8, 8, ...). The second sequence begins with the same "1" but is the diagonal going down and to the right, thus: (1, 5, 16, 42, 99, 219, 466, ...). It appears that for all such sequence pairs, the binomial transform of the first, (1, 4, 7, 8, 8, 8, ...) in this case; is equal to the second: (1, 5, 16, 42, 99, ...). - _Gary W. Adamson_, Aug 19 2015
%C A008949 Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*. Let q(n) be the sum of polynomials in the n-th generation of T*. For n >= 0, row n of A008949 gives the coefficients of q(n+1); e.g., (row 3) = (1, 4, 7, 8) matches x^3 + 4*x^2 + 7*x + 9, which is the sum of the 8 polynomials in the 4th generation of T*. - _Clark Kimberling_, Jun 16 2016
%C A008949 T(n,k) is the number of subsets of [n]={1,...,n} of at most size k. Equivalently, T(n,k) is the number of subsets of [n] of at least size n-k. Counting the subsets of at least size (n-k) by conditioning on the largest element m of the smallest (n-k) elements of such a subset provides the formula T(n,k) = Sum_{m=n-k..n} C(m-1,n-k-1)*2^(n-m), and, by letting j=m-n+k, we obtain T(n,k) = Sum_{j=0..k} C(n+j-k-1,j)*2^(k-j). - _Dennis P. Walsh_, Sep 25 2017
%C A008949 If the interval of integers 1..n is shifted up or down by k, making the new interval 1+k..n+k or 1-k..n-k, then T(n-1,n-1-k) (= 2^(n-1)-T(n-1,k-1)) is the number of subsets of the new interval that contain their own cardinal number as an element. - _David Pasino_, Nov 01 2018
%D A008949 F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 376.
%H A008949 Harvey P. Dale, <a href="/A008949/b008949.txt">Table of n, a(n) for n = 0..10000</a>
%H A008949 Milica Andelic, C. M. da Fonseca and A. Pereira, <a href="https://arxiv.org/abs/1609.04208">The mu-permanent, a new graph labeling, and a known integer sequence</a>, arXiv:1609.04208 [math.CO], 2016.
%H A008949 Stefan Forcey, <a href="https://sforcey.github.io/sf34/planes_axioms.pdf">Planes and axioms</a>, Univ. Akron (2024). See p. 2.
%H A008949 Stefan Forcey, <a href="https://arxiv.org/abs/2504.11461">Counting plane arrangements via oriented matroids</a>, arXiv:2504.11461 [math.HO], 2025. See p. 18.
%H A008949 Rob Johnson, <a href="http://web.archive.org/web/20140822210215/http://www.whim.org/nebula/math/spacediv.html">Dividing Space</a>.
%H A008949 Norman Lindquist and Gerard Sierksma, <a href="https://doi.org/10.1016/0097-3165(81)90015-7">Extensions of set partitions</a>, Journal of Combinatorial Theory, Series A 31.2 (1981): 190-198. See Table I.
%H A008949 Denis Neiter and Amsha Proag, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Proag/proag3.html">Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
%H A008949 Dennis P. Walsh, <a href="http://capone.mtsu.edu/dwalsh/subcount.pdf">A note on counting subsets of restricted size</a>
%H A008949 Wikipedia, <a href="https://en.wikipedia.org/wiki/Bernoulli%27s_triangle">Bernoulli's triangle</a>
%H A008949 <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>
%F A008949 From partial sums across rows of Pascal triangle A007318.
%F A008949 T(n, 0) = 1, T(n, n) = 2^n, T(n, k) = T(n-1, k-1) + T(n-1, k), 0 < k < n.
%F A008949 G.f.: (1 - x*y)/((1 - y - x*y)*(1 - 2*x*y)). - Antonio Gonzalez (gonfer00(AT)gmail.com), Sep 08 2009
%F A008949 T(2n,n) = A032443(n). - _Philippe Deléham_, Sep 16 2009
%F A008949 T(n,k) = 2 T(n-1,k-1) + binomial(n-1,k) = 2 T(n-1,k) - binomial(n-1,k). - _M. F. Hasler_, May 30 2010
%F A008949 T(n,k) = binomial(n,n-k)* 2F1(1, -k; n+1-k; -1). - _Olivier Gérard_, Aug 02 2012
%F A008949 For a closed-form formula for arbitrary left and right borders of Pascal like triangle see A228196. - _Boris Putievskiy_, Aug 18 2013
%F A008949 T(n,floor(n/2)) = A027306(n). - _Reinhard Zumkeller_, Nov 14 2014
%F A008949 T(n,n) = 2^n, otherwise for 0 <= k <= n-1, T(n,k) = 2^n - T(n,n-k-1). - _Bob Selcoe_, Mar 30 2017
%F A008949 For fixed j >= 0, lim_{n -> oo} T(n+1,n-j+1)/T(n,n-j) = 2. - _Bob Selcoe_, Apr 03 2017
%F A008949 T(n,k) = Sum_{j=0..k} C(n+j-k-1,j)*2^(k-j). - _Dennis P. Walsh_, Sep 25 2017
%e A008949 Triangle begins:
%e A008949   1;
%e A008949   1,  2;
%e A008949   1,  3,  4;
%e A008949   1,  4,  7,   8;
%e A008949   1,  5, 11,  15,  16;
%e A008949   1,  6, 16,  26,  31,  32;
%e A008949   1,  7, 22,  42,  57,  63,  64;
%e A008949   1,  8, 29,  64,  99, 120, 127, 128;
%e A008949   1,  9, 37,  93, 163, 219, 247, 255,  256;
%e A008949   1, 10, 46, 130, 256, 382, 466, 502,  511,  512;
%e A008949   1, 11, 56, 176, 386, 638, 848, 968, 1013, 1023, 1024;
%e A008949   ...
%p A008949 A008949 := proc(n,k) local i; add(binomial(n,i),i=0..k) end; # Typo corrected by _R. J. Mathar_, Oct 26 2010
%t A008949 Table[Length[Select[Subsets[n], (Length[ # ] <= k) &]], {n, 0, 12}, {k, 0, n}] // Grid (* _Geoffrey Critzer_, May 13 2009 *)
%t A008949 Flatten[Accumulate/@Table[Binomial[n,i],{n,0,20},{i,0,n}]] (* _Harvey P. Dale_, Aug 08 2015 *)
%t A008949 T[ n_, k_] := If[ n < 0 || k > n, 0, Binomial[n, k] Hypergeometric2F1[1, -k, n + 1 - k, -1]]; (* _Michael Somos_, Aug 05 2017 *)
%o A008949 (PARI) A008949(n)=T8949(t=sqrtint(2*n-sqrtint(2*n)),n-t*(t+1)/2)
%o A008949 T8949(r,c)={ 2*c > r || return(sum(i=0,c,binomial(r,i))); 1<<r - sum( i=c+1,r,binomial(r,i))} \\ _M. F. Hasler_, May 30 2010
%o A008949 (PARI) {T(n, k) = if(k>n, 0, sum(i=0, k, binomial(n, i)))}; /* _Michael Somos_, Aug 05 2017 */
%o A008949 (PARI) row(n) = my(v=vector(n+1, k, binomial(n,k-1))); vector(#v, k, sum(i=1, k, v[i])); \\ _Michel Marcus_, Apr 13 2025
%o A008949 (Haskell)
%o A008949 a008949 n k = a008949_tabl !! n !! k
%o A008949 a008949_row n = a008949_tabl !! n
%o A008949 a008949_tabl = map (scanl1 (+)) a007318_tabl
%o A008949 -- _Reinhard Zumkeller_, Nov 23 2012
%o A008949 (GAP) T:=Flat(List([0..11],n->List([0..n],k->Sum([0..k],j->Binomial(n+j-k-1,j)*2^(k-j))))); # _Muniru A Asiru_, Nov 25 2018
%o A008949 (Magma) [[(&+[Binomial(n,j): j in [0..k]]): k in [0..n]]: n in [0..12]]; // _G. C. Greubel_, Nov 25 2018
%o A008949 (Sage) [[sum(binomial(n,j) for j in range(k+1)) for k in range(n+1)] for n in range(12)] # _G. C. Greubel_, Nov 25 2018
%Y A008949 Diagonals are given by A000079, A000225, A000295, A002662, A002663, A002664, A035038-A035042.
%Y A008949 Columns are given by A000012, A000027, A000124, A000125, A000127, A006261, A008859, A008860, A008861, A008862, A008863. - _Ken Shirriff_, Jun 28 2011
%Y A008949 Row sums sequence is A001792.
%Y A008949 T(n, m)= A055248(n, n-m).
%Y A008949 Cf. A110555, A007318, A000346, A171886, A228196, A228576.
%Y A008949 Cf. also A027306, A249111, A163866, A261363.
%Y A008949 Cf. A000071, A001924
%K A008949 tabl,nonn,easy,nice
%O A008949 0,3
%A A008949 _N. J. A. Sloane_
%E A008949 More terms from Larry Reeves (larryr(AT)acm.org), Mar 23 2000