cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-8 of 8 results.

A000295 Eulerian numbers (Euler's triangle: column k=2 of A008292, column k=1 of A173018).

Original entry on oeis.org

0, 0, 1, 4, 11, 26, 57, 120, 247, 502, 1013, 2036, 4083, 8178, 16369, 32752, 65519, 131054, 262125, 524268, 1048555, 2097130, 4194281, 8388584, 16777191, 33554406, 67108837, 134217700, 268435427, 536870882, 1073741793, 2147483616, 4294967263, 8589934558
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

There are 2 versions of Euler's triangle:
* A008292 Classic version of Euler's triangle used by Comtet (1974).
* A173018 Version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990).
Euler's triangle rows and columns indexing conventions:
* A008292 The rows and columns of the Eulerian triangle are both indexed starting from 1. (Classic version: used in the classic books by Riordan and Comtet.)
* A173018 The rows and columns of the Eulerian triangle are both indexed starting from 0. (Graham et al.)
Number of Dyck paths of semilength n having exactly one long ascent (i.e., ascent of length at least two). Example: a(4)=11 because among the 14 Dyck paths of semilength 4, the paths that do not have exactly one long ascent are UDUDUDUD (no long ascent), UUDDUUDD and UUDUUDDD (two long ascents). Here U=(1,1) and D=(1,-1). Also number of ordered trees with n edges having exactly one branch node (i.e., vertex of outdegree at least two). - Emeric Deutsch, Feb 22 2004
Number of permutations of {1,2,...,n} with exactly one descent (i.e., permutations (p(1),p(2),...,p(n)) such that #{i: p(i)>p(i+1)}=1). E.g., a(3)=4 because the permutations of {1,2,3} with one descent are 132, 213, 231 and 312.
a(n+1) is the convolution of nonnegative integers (A001477) and powers of two (A000079). - Graeme McRae, Jun 07 2006
Partial sum of main diagonal of A125127. - Jonathan Vos Post, Nov 22 2006
Number of partitions of an n-set having exactly one block of size > 1. Example: a(4)=11 because, if the partitioned set is {1,2,3,4}, then we have 1234, 123|4, 124|3, 134|2, 1|234, 12|3|4, 13|2|4, 14|2|3, 1|23|4, 1|24|3 and 1|2|34. - Emeric Deutsch, Oct 28 2006
k divides a(k+1) for k in A014741. - Alexander Adamchuk, Nov 03 2006
(Number of permutations avoiding patterns 321, 2413, 3412, 21534) minus one. - Jean-Luc Baril, Nov 01 2007, Mar 21 2008
The chromatic invariant of the prism graph P_n for n >= 3. - Jonathan Vos Post, Aug 29 2008
Decimal integer corresponding to the result of XORing the binary representation of 2^n - 1 and the binary representation of n with leading zeros. This sequence and a few others are syntactically similar. For n > 0, let D(n) denote the decimal integer corresponding to the binary number having n consecutive 1's. Then D(n).OP.n represents the n-th term of a sequence when .OP. stands for a binary operator such as '+', '-', '*', 'quotentof', 'mod', 'choose'. We then get the various sequences A136556, A082495, A082482, A066524, A000295, A052944. Another syntactically similar sequence results when we take the n-th term as f(D(n)).OP.f(n). For example if f='factorial' and .OP.='/', we get (A136556)(A000295) ; if f='squaring' and .OP.='-', we get (A000295)(A052944). - K.V.Iyer, Mar 30 2009
Chromatic invariant of the prism graph Y_n.
Number of labelings of a full binary tree of height n-1, such that each path from root to any leaf contains each label from {1,2,...,n-1} exactly once. - Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009
Also number of nontrivial equivalence classes generated by the weak associative law X((YZ)T)=(X(YZ))T on words with n open and n closed parentheses. Also the number of join (resp. meet)-irreducible elements in the pruning-grafting lattice of binary trees with n leaves. - Jean Pallo, Jan 08 2010
Nonzero terms of this sequence can be found from the row sums of the third sub-triangle extracted from Pascal's triangle as indicated below by braces:
1;
1, 1;
{1}, 2, 1;
{1, 3}, 3, 1;
{1, 4, 6}, 4, 1;
{1, 5, 10, 10}, 5, 1;
{1, 6, 15, 20, 15}, 6, 1;
... - L. Edson Jeffery, Dec 28 2011
For integers a, b, denote by a<+>b the least c >= a, such that the Hamming distance D(a,c) = b (note that, generally speaking, a<+>b differs from b<+>a). Then for n >= 3, a(n) = n<+>n. This has a simple explanation: for n >= 3 in binary we have a(n) = (2^n-1)-n = "anti n". - Vladimir Shevelev, Feb 14 2012
a(n) is the number of binary sequences of length n having at least one pair 01. - Branko Curgus, May 23 2012
Nonzero terms are those integers k for which there exists a perfect (Hamming) error-correcting code. - L. Edson Jeffery, Nov 28 2012
a(n) is the number of length n binary words constructed in the following manner: Select two positions in which to place the first two 0's of the word. Fill in all (possibly none) of the positions before the second 0 with 1's and then complete the word with an arbitrary string of 0's or 1's. So a(n) = Sum_{k=2..n} (k-1)*2^(n-k). - Geoffrey Critzer, Dec 12 2013
Without first 0: a(n)/2^n equals Sum_{k=0..n} k/2^k. For example: a(5)=57, 57/32 = 0/1 + 1/2 + 2/4 + 3/8 + 4/16 + 5/32. - Bob Selcoe, Feb 25 2014
The first barycentric coordinate of the centroid of the first n rows of Pascal's triangle, assuming the numbers are weights, is A000295(n+1)/A000337(n). See attached figure. - César Eliud Lozada, Nov 14 2014
Starting (0, 1, 4, 11, ...), this is the binomial transform of (0, 1, 2, 2, 2, ...). - Gary W. Adamson, Jul 27 2015
Also the number of (non-null) connected induced subgraphs in the n-triangular honeycomb rook graph. - Eric W. Weisstein, Aug 27 2017
a(n) is the number of swaps needed in the worst case to transform a binary tree with n full levels into a heap, using (bottom-up) heapify. - Rudy van Vliet, Sep 19 2017
The utility of large networks, particularly social networks, with n participants is given by the terms a(n) of this sequence. This assertion is known as Reed's Law, see the Wikipedia link. - Johannes W. Meijer, Jun 03 2019
a(n-1) is the number of subsets of {1..n} in which the largest element of the set exceeds by at least 2 the next largest element. For example, for n = 5, a(4) = 11 and the 11 sets are {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}, {1,2,4}, {1,2,5}, {1,3,5}, {2,3,5}, {1,2,3,5}. - Enrique Navarrete, Apr 08 2020
a(n-1) is also the number of subsets of {1..n} in which the second smallest element of the set exceeds by at least 2 the smallest element. For example, for n = 5, a(4) = 11 and the 11 sets are {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,4,5}, {1,3,4,5}. - Enrique Navarrete, Apr 09 2020
a(n+1) is the sum of the smallest elements of all subsets of {1..n}. For example, for n=3, a(4)=11; the subsets of {1,2,3} are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, and the sum of smallest elements is 11. - Enrique Navarrete, Aug 20 2020
Number of subsets of an n-set that have more than one element. - Eric M. Schmidt, Mar 13 2021
Number of individual bets in a "full cover" bet on n-1 horses, dogs, etc. in different races. Each horse, etc. can be bet on or not, giving 2^n bets. But, by convention, singles (a bet on only one race) are not included, reducing the total number bets by n. It is also impossible to bet on no horses at all, reducing the number of bets by another 1. A full cover on 4 horses, dogs, etc. is therefore 6 doubles, 4 trebles and 1 four-horse etc. accumulator. In British betting, such a bet on 4 horses etc. is a Yankee; on 5, a super-Yankee. - Paul Duckett, Nov 17 2021
From Enrique Navarrete, May 25 2022: (Start)
Number of binary sequences of length n with at least two 1's.
a(n-1) is the number of ways to choose an odd number of elements greater than or equal to 3 out of n elements.
a(n+1) is the number of ways to split [n] = {1,2,...,n} into two (possibly empty) complementary intervals {1,2,...,i} and {i+1,i+2,...,n} and then select a subset from the first interval (2^i choices, 0 <= i <= n), and one block/cell (i.e., subinterval) from the second interval (n-i choices, 0 <= i <= n).
(End)
Number of possible conjunctions in a system of n planets; for example, there can be 0 conjunctions with one planet, one with two planets, four with three planets (three pairs of planets plus one with all three) and so on. - Wendy Appleby, Jan 02 2023
Largest exponent m such that 2^m divides (2^n-1)!. - Franz Vrabec, Aug 18 2023
It seems that a(n-1) is the number of odd r with 0 < r < 2^n for which there exist u,v,w in the x-independent beginning of the Collatz trajectory of 2^n x + r with u+v = w+1, as detailed in the link "Collatz iteration and Euler numbers?". A better understanding of this might also give a formula for A374527. - Markus Sigg, Aug 02 2024
This sequence has a connection to consecutively halved positional voting (CHPV); see Mendenhall and Switkay. - Hal M. Switkay, Feb 25 2025
a(n) is the number of subsets of size 2 and more of an n-element set. Equivalently, a(n) is the number of (hyper)edges of size 2 and more in a complete hypergraph of n vertices. - Yigit Oktar, Apr 05 2025

Examples

			G.f. = x^2 + 4*x^3 + 11*x^4 + 26*x^5 + 57*x^6 + 120*x^7 + 247*x^8 + 502*x^9 + ...

References

  • O. Bottema, Problem #562, Nieuw Archief voor Wiskunde, 28 (1980) 115.
  • L. Comtet, "Permutations by Number of Rises; Eulerian Numbers." Section 6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 51 and 240-246, 1974.
  • F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 151.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
  • D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 34.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 215.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A008292 (classic version of Euler's triangle used by Comtet (1974)).
Cf. A173018 (version of Euler's triangle used by Graham, Knuth and Patashnik in Concrete Math. (1990)).
Cf. A002662 (partial sums).
Partial sums of A000225.
Row sums of A014473 and of A143291.
Second column of triangles A112493 and A112500.
Sequences A125128 and A130103 are essentially the same.
Column k=1 of A124324.
Cf. A000079, A000108, A000217, A000325, A000975, A001511, A002663.
Cf. A002664, A007814, A008292, A008949, A014741, A016031, A028366.
Cf. A035039, A035040, A035041, A035042, A079583, A107907, A130321.
Cf. A130128, A130330, A131768, A131816.

Programs

  • Haskell
    a000295 n = 2^n - n - 1  -- Reinhard Zumkeller, Nov 25 2013
  • Magma
    [2^n-n-1: n in [0..40]]; // Vincenzo Librandi, Jul 29 2015
  • Magma
    [EulerianNumber(n, 1): n in [0..40]]; // G. C. Greubel, Oct 02 2024
  • Maple
    [ seq(2^n-n-1, n=1..50) ];
A000295 := -z/(2*z-1)/(z-1)**2; # Simon Plouffe in his 1992 dissertation
# Grammar specification:
spec := [S, { B = Set(Z, 1 <= card), C = Sequence(B, 2 <= card), S = Prod(B, C) }, unlabeled]:
struct := n -> combstruct[count](spec, size = n+1);
seq(struct(n), n = 0..33); # Peter Luschny, Jul 22 2014
  • Mathematica
    a[n_] = If[n==0, 0, n*(HypergeometricPFQ[{1, 1-n}, {2}, -1] - 1)];
Table[a[n], {n,0,40}] (* Olivier Gérard, Mar 29 2011 *)
LinearRecurrence[{4, -5, 2}, {0, 0, 1}, 40] (* Vincenzo Librandi, Jul 29 2015 *)
Table[2^n -n-1, {n,0,40}] (* Eric W. Weisstein, Nov 16 2017 *)
  • PARI
    a(n)=2^n-n-1 \\ Charles R Greathouse IV, Jun 10 2011
  • SageMath
    [2^n -(n+1) for n in range(41)] # G. C. Greubel, Oct 02 2024

Formula

a(n) = 2^n - n - 1.
G.f.: x^2/((1-2*x)*(1-x)^2).
A107907(a(n+2)) = A000079(n+2). - Reinhard Zumkeller, May 28 2005
E.g.f.: exp(x)*(exp(x)-1-x). - Emeric Deutsch, Oct 28 2006
a(0)=0, a(1)=0, a(n) = 3*a(n-1) - 2*a(n-2) + 1. - Miklos Kristof, Mar 09 2005
a(0)=0, a(n) = 2*a(n-1) + n - 1 for all n in Z.
a(n) = Sum_{k=2..n} binomial(n, k). - Paul Barry, Jun 05 2003
a(n+1) = Sum_{i=1..n} Sum_{j=1..i} C(i, j). - Benoit Cloitre, Sep 07 2003
a(n+1) = 2^n*Sum_{k=0..n} k/2^k. - Benoit Cloitre, Oct 26 2003
a(0)=0, a(1)=0, a(n) = Sum_{i=0..n-1} i+a(i) for i > 1. - Gerald McGarvey, Jun 12 2004
a(n+1) = Sum_{k=0..n} (n-k)*2^k. - Paul Barry, Jul 29 2004
a(n) = Sum_{k=0..n} binomial(n, k+2); a(n+2) = Sum_{k=0..n} binomial(n+2, k+2). - Paul Barry, Aug 23 2004
a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-k-1, k+1)*2^(n-k-2)*(-1/2)^k. - Paul Barry, Oct 25 2004
a(0) = 0; a(n) = Stirling2(n,2) + a(n-1) = A000225(n-1) + a(n-1). - Thomas Wieder, Feb 18 2007
a(n) = A000325(n) - 1. - Jonathan Vos Post, Aug 29 2008
a(0) = 0, a(n) = Sum_{k=0..n-1} 2^k - 1. - Doug Bell, Jan 19 2009
a(n) = A000217(n-1) + A002662(n) for n>0. - Geoffrey Critzer, Feb 11 2009
a(n) = A000225(n) - n. - Zerinvary Lajos, May 29 2009
a(n) = n*(2F1([1,1-n],[2],-1) - 1). - Olivier Gérard, Mar 29 2011
Column k=1 of A173018 starts a'(n) = 0, 1, 4, 11, ... and has the hypergeometric representation n*hypergeom([1, -n+1], [-n], 2). This can be seen as a formal argument to prefer Euler's A173018 over A008292. - Peter Luschny, Sep 19 2014
E.g.f.: exp(x)*(exp(x)-1-x); this is U(0) where U(k) = 1 - x/(2^k - 2^k/(x + 1 - x^2*2^(k+1)/(x*2^(k+1) - (k+1)/U(k+1)))); (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Dec 01 2012
a(n) = A079583(n) - A000225(n+1). - Miquel Cerda, Dec 25 2016
a(0) = 0; a(1) = 0; for n > 1: a(n) = Sum_{i=1..2^(n-1)-1} A001511(i). - David Siegers, Feb 26 2019
a(n) = A007814(A028366(n)). - Franz Vrabec, Aug 18 2023
a(n) = Sum_{k=1..floor((n+1)/2)} binomial(n+1, 2*k+1). - Taras Goy, Jan 02 2025

A055248 Triangle of partial row sums of triangle A007318(n,m) (Pascal's triangle). Triangle A008949 read backwards. Riordan (1/(1-2x), x/(1-x)).

Original entry on oeis.org

1, 2, 1, 4, 3, 1, 8, 7, 4, 1, 16, 15, 11, 5, 1, 32, 31, 26, 16, 6, 1, 64, 63, 57, 42, 22, 7, 1, 128, 127, 120, 99, 64, 29, 8, 1, 256, 255, 247, 219, 163, 93, 37, 9, 1, 512, 511, 502, 466, 382, 256, 130, 46, 10, 1, 1024, 1023, 1013, 968, 848, 638, 386, 176, 56, 11, 1
Offset: 0

Views

Author

Wolfdieter Lang, May 26 2000

Keywords

Comments

In the language of the Shapiro et al. reference (also given in A053121) such a lower triangular (ordinary) convolution array, considered as matrix, belongs to the Riordan-group. The g.f. for the row polynomials p(n,x) (increasing powers of x) is 1/((1-2*z)*(1-x*z/(1-z))).
Binomial transform of the all 1's triangle: as a Riordan array, it factors to give (1/(1-x),x/(1-x))(1/(1-x),x). Viewed as a number square read by antidiagonals, it has T(n,k) = Sum_{j=0..n} binomial(n+k,n-j) and is then the binomial transform of the Whitney square A004070. - Paul Barry, Feb 03 2005
Riordan array (1/(1-2x), x/(1-x)). Antidiagonal sums are A027934(n+1), n >= 0. - Paul Barry, Jan 30 2005; edited by Wolfdieter Lang, Jan 09 2015
Eigensequence of the triangle = A005493: (1, 3, 10, 37, 151, 674, ...); row sums of triangles A011971 and A159573. - Gary W. Adamson, Apr 16 2009
Read as a square array, this is the generalized Riordan array ( 1/(1 - 2*x), 1/(1 - x) ) as defined in the Bala link (p. 5), which factorizes as ( 1/(1 - x), x/(1 - x) )*( 1/(1 - x), x )*( 1, 1 + x ) = P*U*transpose(P), where P denotes Pascal's triangle, A007318, and U is the lower unit triangular array with 1's on or below the main diagonal. - Peter Bala, Jan 13 2016

Examples

			The triangle a(n,m) begins:
n\m    0    1    2   3   4   5   6   7  8  9 10 ...
0:     1
1:     2    1
2:     4    3    1
3:     8    7    4   1
4:    16   15   11   5   1
5:    32   31   26  16   6   1
6:    64   63   57  42  22   7   1
7:   128  127  120  99  64  29   8   1
8:   256  255  247 219 163  93  37   9  1
9:   512  511  502 466 382 256 130  46 10  1
10: 1024 1023 1013 968 848 638 386 176 56 11  1
... Reformatted. - _Wolfdieter Lang_, Jan 09 2015
Fourth row polynomial (n=3): p(3,x)= 8 + 7*x + 4*x^2 + x^3.
The matrix inverse starts
   1;
  -2,   1;
   2,  -3,   1;
  -2,   5,  -4,    1;
   2,  -7,   9,   -5,    1;
  -2,   9, -16,   14,   -6,    1;
   2, -11,  25,-  30,   20,   -7,    1;
  -2,  13, -36,   55,  -50,   27,   -8,    1;
   2, -15,  49,  -91,  105,  -77,   35,   -9,  1;
  -2,  17, -64,  140, -196,  182, -112,   44, -10,   1;
   2, -19,  81, -204,  336, -378,  294, -156,  54, -11, 1;
   ...
which may be related to A029653. - _R. J. Mathar_, Mar 29 2013
From _Peter Bala_, Dec 23 2014: (Start)
With the array M(k) as defined in the Formula section, the infinite product M(0)*M(1)*M(2)*... begins
/1      \ /1        \ /1       \       /1       \
|2 1     ||0 1       ||0 1      |      |2  1     |
|4 3 1   ||0 2 1     ||0 0 1    |... = |4  5 1   |
|8 7 4 1 ||0 4 3 1   ||0 0 2 1  |      |8 19 9 1 |
|...     ||0 8 7 4 1 ||0 0 4 3 1|      |...      |
|...     ||...       ||...      |      |         |
= A143494. (End)
Matrix factorization of square array as P*U*transpose(P):
/1      \ /1        \ /1 1 1 1 ...\    /1  1  1  1 ...\
|1 1     ||1 1       ||0 1 2 3 ... |   |2  3  4  5 ... |
|1 2 1   ||1 1 1     ||0 0 1 3 ... | = |4  7 11 16 ... |
|1 3 3 1 ||1 1 1 1   ||0 0 0 1 ... |   |8 15 26 42 ... |
|...     ||...       ||...         |   |...            |
- _Peter Bala_, Jan 13 2016

Links

Crossrefs

Column sequences: A000079 (powers of 2, m=0), A000225 (m=1), A000295 (m=2), A002662 (m=3), A002663 (m=4), A002664 (m=5), A035038 (m=6), A035039 (m=7), A035040 (m=8), A035041 (m=9), A035042 (m=10).
Row sums: A001792(n) = A055249(n, 0).
Alternating row sums: A011782.
Cf. A011971, A159573. - Gary W. Adamson, Apr 16 2009
Cf. A007318, A008949, A106516, A143494.

Programs

  • Haskell
    a055248 n k = a055248_tabl !! n !! k
a055248_row n = a055248_tabl !! n
a055248_tabl = map reverse a008949_tabl
-- Reinhard Zumkeller, Jun 20 2015
  • Maple
    T := (n,k) -> 2^n - (1/2)*binomial(n, k-1)*hypergeom([1, n + 1], [n-k + 2], 1/2).
seq(seq(simplify(T(n,k)), k=0..n),n=0..10); # Peter Luschny, Oct 10 2019
  • Mathematica
    a[n_, m_] := Sum[ Binomial[n, m + j], {j, 0, n}]; Table[a[n, m], {n, 0, 10}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jul 05 2013, after Paul Barry *)
T[n_, k_] := Binomial[n, k] * Hypergeometric2F1[1, k - n, k + 1, -1];
Flatten[Table[T[n, k], {n, 0, 7}, {k, 0, n}]]  (* Peter Luschny, Oct 06 2023 *)

Formula

a(n, m) = A008949(n, n-m), if n > m >= 0.
a(n, m) = Sum_{k=m..n} A007318(n, k) (partial row sums in columns m).
Column m recursion: a(n, m) = Sum_{j=m..n-1} a(j, m) + A007318(n, m) if n >= m >= 0, a(n, m) := 0 if n
G.f. for column m: (1/(1-2*x))*(x/(1-x))^m, m >= 0.
a(n, m) = Sum_{j=0..n} binomial(n, m+j). - Paul Barry, Feb 03 2005
Inverse binomial transform (by columns) of A112626. - Ross La Haye, Dec 31 2006
T(2n,n) = A032443(n). - Philippe Deléham, Sep 16 2009
From Peter Bala, Dec 23 2014: (Start)
Exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(8 + 7*x + 4*x^2/2! + x^3/3!) = 8 + 15*x + 26*x^2/2! + 42*x^3/3! + 64*x^4/4! + .... The same property holds more generally for Riordan arrays of the form ( f(x), x/(1 - x) ).
Let M denote the present triangle. For k = 0,1,2,... define M(k) to be the lower unit triangular block array
/I_k 0\
\ 0 M/ having the k X k identity matrix I_k as the upper left block; in particular, M(0) = M. The infinite product M(0)*M(1)*M(2)*..., which is clearly well-defined, is equal to A143494 (but with a different offset). See the Example section. Cf. A106516. (End)
a(n,m) = Sum_{p=m..n} 2^(n-p)*binomial(p-1,m-1), n >= m >= 0, else 0. - Wolfdieter Lang, Jan 09 2015
T(n, k) = 2^n - (1/2)*binomial(n, k-1)*hypergeom([1, n+1], [n-k+2], 1/2). - Peter Luschny, Oct 10 2019
T(n, k) = binomial(n, k)*hypergeom([1, k - n], [k + 1], -1). - Peter Luschny, Oct 06 2023
n-th row polynomial R(n, x) = (2^n - x*(1 + x)^n)/(1 - x). These polynomials can be used to find series acceleration formulas for the constants log(2) and Pi. - Peter Bala, Mar 03 2025

A004070 Table of Whitney numbers W(n,k) read by antidiagonals, where W(n,k) is maximal number of pieces into which n-space is sliced by k hyperplanes, n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 4, 1, 1, 2, 4, 7, 5, 1, 1, 2, 4, 8, 11, 6, 1, 1, 2, 4, 8, 15, 16, 7, 1, 1, 2, 4, 8, 16, 26, 22, 8, 1, 1, 2, 4, 8, 16, 31, 42, 29, 9, 1, 1, 2, 4, 8, 16, 32, 57, 64, 37, 10, 1, 1, 2, 4, 8, 16, 32, 63, 99, 93, 46, 11, 1, 1, 2, 4, 8, 16, 32, 64, 120, 163
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

As a number triangle, this is given by T(n,k)=sum{j=0..n, C(n,j)(-1)^(n-j)sum{i=0..j, C(j+k,i-k)}}. - Paul Barry, Aug 23 2004
As a number triangle, this is the Riordan array (1/(1-x), x(1+x)) with T(n,k)=sum{i=0..n, binomial(k,i-k)}. Diagonal sums are then A023434(n+1). - Paul Barry, Feb 16 2005
Form partial sums across rows of square array of binomial coefficients A026729; see also A008949. - Philippe Deléham, Aug 28 2005
Square array A026729 -> Partial sums across rows
1 0 0 0 0 0 0 . . . . 1 1 1 1 1 1 1 . . . . . .
1 1 0 0 0 0 0 . . . . 1 2 2 2 2 2 2 . . . . . .
1 2 1 0 0 0 0 . . . . 1 3 4 4 4 4 4 . . . . . .
1 3 3 1 0 0 0 . . . . 1 4 7 8 8 8 8 . . . . . .
For other Whitney numbers see A007799.
W(n,k) is the number of length k binary sequences containing no more than n 1's. - Geoffrey Critzer, Mar 15 2010
From Emeric Deutsch, Jun 15 2010: (Start)
Viewed as a number triangle, T(n,k) is the number of internal nodes of the Fibonacci tree of order n+2 at level k. A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node.
(End)
Named after the American mathematician Hassler Whitney (1907-1989). - Amiram Eldar, Jun 13 2021

Examples

			Table W(n,k) begins:
  1 1 1 1  1  1  1 ...
  1 2 3 4  5  6  7 ...
  1 2 4 7 11 16 22 ...
  1 2 4 8 15 26 42 ...
W(2,4) = 11 because there are 11 length 4 binary sequences containing no more than 2 1's: {0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 0}, {0, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}, {0, 1, 1, 0}, {1, 0, 0, 0}, {1, 0, 0, 1}, {1, 0, 1, 0}, {1, 1, 0, 0}. - _Geoffrey Critzer_, Mar 15 2010
Table T(n, k) begins:
  1
  1  1
  1  2  1
  1  2  3  1
  1  2  4  4  1
  1  2  4  7  5  1
  1  2  4  8 11  6  1
...

References

  • Donald E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Links

Crossrefs

Cf. A007799. As a triangle, mirror A052509.
Rows converge to powers of two (A000079). Subdiagonals include A000225, A000295, A002662, A002663, A002664, A035038, A035039, A035040, A035041, A035042. Antidiagonal sums are A000071.
Rows are: A000012, A000027, A000124, A000125, A000127, A006261, A008859, A008860, A008861, A008862, A008863.
Cf. A178522, A178524.

Programs

  • Mathematica
    Transpose[ Table[Table[Sum[Binomial[n, k], {k, 0, m}], {m, 0, 15}], {n, 0, 15}]] // Grid (* Geoffrey Critzer, Mar 15 2010 *)
T[ n_, k_] := Sum[ Binomial[n, j] (-1)^(n - j) Sum[ Binomial[j + k, i - k], {i, 0, j}], {j, 0, n}]; (* Michael Somos, May 31 2016 *)
  • PARI
    /* array read by antidiagonals up coordinate index functions */
t1(n) = binomial(floor(3/2 + sqrt(2+2*n)), 2) - (n+1); /* A025581 */
t2(n) = n - binomial(floor(1/2 + sqrt(2+2*n)), 2); /* A002262 */
/* define the sequence array function for A004070 */
W(n, k) = sum(i=0, n, binomial(k, i));
/* visual check ( origin 0,0 ) */
printp(matrix(7, 7, n, k, W(n-1, k-1)));
/* print the sequence entries by antidiagonals going up ( origin 0,0 ) */
print1("S A004070 "); for(n=0, 32, print1(W(t1(n), t2(n))","));
print1("T A004070 "); for(n=33, 61, print1(W(t1(n), t2(n))","));
print1("U A004070 "); for(n=62, 86, print1(W(t1(n), t2(n))",")); /* Michael Somos, Apr 28 2000 */
  • PARI
    T(n, k)=sum(m=0, n-k, binomial(k, m)) \\ Jianing Song, May 30 2022

Formula

W(n, k) = Sum_{i=0..n} binomial(k, i). - Bill Gosper
W(n, k) = if k=0 or n=0 then 1 else W(n, k-1)+W(n-1, k-1). - David Broadhurst, Jan 05 2000
The table W(n,k) = A000012 * A007318(transform), where A000012 = (1; 1,1; 1,1,1; ...). - Gary W. Adamson, Nov 15 2007
E.g.f. for row n: (1 + x + x^2/2! + ... + x^n/n!)* exp(x). - Geoffrey Critzer, Mar 15 2010
G.f.: 1 / (1 - x - x*y*(1 - x^2)) = Sum_{0 <= k <= n} x^n * y^k * T(n, k). - Michael Somos, May 31 2016
W(n, n) = 2^n. - Michael Somos, May 31 2016
From Jianing Song, May 30 2022: (Start)
T(n, 0) = T(n, n) = 1 for n >= 0; T(n, k) = T(n-1, k-1) + T(n-2, k-1) for k=1, 2, ..., n-1, n >= 2.
T(n, k) = Sum_{m=0..n-k} binomial(k, m).
T(n,k) = 2^k for 0 <= k <= floor(n/2). (End)

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Mar 20 2000

A035038 a(n) = 2^n - C(n,0) - C(n,1) - ... - C(n,5).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 8, 37, 130, 386, 1024, 2510, 5812, 12911, 27824, 58651, 121670, 249528, 507624, 1026876, 2069256, 4158861, 8344056, 16721761, 33486026, 67025182, 134116144, 268313018, 536724316, 1073567387, 2147277280, 4294724471, 8589650318, 17179537972
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Starting with "1", equals the eigensequence of a triangle with A000579 = binomial(n,6) = (1, 7, 28, 84, 210, ...) as the left column and the rest 1's. - Gary W. Adamson, Jul 24 2010

Links

Crossrefs

Cf. A000079, A000225, A000295, A000579, A002663, A002664, A007318.
Cf. A035039, A035040, A035041, A035042.

Programs

  • Haskell
    a035038 n = a035038_list !! n
a035038_list = map (sum . drop 6) a007318_tabl
-- Reinhard Zumkeller, Jun 20 2015
  • Magma
    [n le 5 select 0 else (&+[Binomial(n,j): j in [6..n]]): n in [0..50]]; // G. C. Greubel, Mar 20 2023
  • Maple
    a:= n-> (Matrix(7, (i,j)-> if (i=j-1) then 1 elif j=1 then [8,-27,50,-55, 36,-13,2][i] else 0 fi)^(n))[1,7]:
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 05 2008
  • Mathematica
    Table[Sum[Binomial[n, k+6], {k,0,n}], {n,0,30}] (* Zerinvary Lajos, Jul 08 2009 *)
Table[2^n-Total[Binomial[n,Range[0,5]]],{n,0,40}] (* Harvey P. Dale, Oct 24 2017 *)
  • SageMath
    [sum(binomial(n,j) for j in range(6,n+1)) for n in range(51)] # G. C. Greubel, Mar 20 2023

Formula

From Paul Barry, Aug 23 2004: (Start)
G.f.: x^6/((1-2*x)*(1-x)^6).
a(n) = Sum_{k=0..n} C(n, k+6) = Sum_{k=6..n} C(n, k).
a(n) = 2*a(n-1) + C(n-1, 5). (End)

A035041 a(n) = 2^n - C(n,0) - C(n,1) - ... - C(n,8).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 11, 67, 299, 1093, 3473, 9949, 26333, 65536, 155382, 354522, 784626, 1695222, 3593934, 7507638, 15505590, 31746651, 64574877, 130712029, 263644133, 530396371, 1065084887, 2136022699, 4279934123, 8570386546
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Links

Crossrefs

a(n)= A055248(n, 9). Partial sums of A035040.
Cf. A000079, A000225, A000295, A002663, A002664, A035038-A035042.
Cf. A007318.

Programs

  • Haskell
    a035041 n = a035041_list !! n
a035041_list = map (sum . drop 9) a007318_tabl
-- Reinhard Zumkeller, Jun 20 2015
  • Maple
    a:=n->sum(binomial(n,j),j=9..n): seq(a(n), n=0..33); # Zerinvary Lajos, Jan 04 2007
  • Mathematica
    a=1;lst={};s1=s2=s3=s4=s5=s6=s7=s8=s9=0;Do[s1+=a;s2+=s1;s3+=s2;s4+=s3;s5+=s4;s6+=s5;s7+=s6;s8+=s7;s9+=s8;AppendTo[lst,s9];a=a*2,{n,5!}];lst (* Vladimir Joseph Stephan Orlovsky, Jan 10 2009 *)
Table[Sum[ Binomial[n, k], {k, 9, n}], {n, 0, 33}] (* Zerinvary Lajos, Jul 08 2009 *)

Formula

G.f.: x^9/((1-2*x)*(1-x)^9).

A058393 A square array based on 1^n (A000012) with each term being the sum of 2 consecutive terms in the previous row.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 0, 1, 2, 1, 1, 1, 2, 3, 1, 0, 1, 2, 4, 4, 1, 1, 1, 2, 4, 7, 5, 1, 0, 1, 2, 4, 8, 11, 6, 1, 1, 1, 2, 4, 8, 15, 16, 7, 1, 0, 1, 2, 4, 8, 16, 26, 22, 8, 1, 1, 1, 2, 4, 8, 16, 31, 42, 29, 9, 1, 0, 1, 2, 4, 8, 16, 32, 57, 64, 37, 10, 1, 1, 1, 2, 4, 8, 16, 32, 63, 99, 93, 46, 11, 1, 0
Offset: 0

Views

Author

Henry Bottomley, Nov 24 2000

Keywords

Comments

Changing the formula by replacing T(0,2n)=T(1,n) by T(0,2n)=T(m,n) for some other value of m, would make the generating function change to coefficient of x^n in expansion of (1+x)^k/(1-x^2)^m. This would produce A058394, A058395, A057884, (and effectively A007318).

Examples

			Rows are (1,0,1,0,1,0,1,...), (1,1,1,1,1,1,...), (1,2,2,2,2,2,...), (1,3,4,4,4,...) etc.

Crossrefs

Rows are A000035 (A000012 with zeros), A000012, A040000 etc. Columns are A000012, A001477, A000124, A000125, A000127, A006261, A008859, A008860, A008861, A008862, A008863 etc. Diagonals include A000079, A000225, A000295, A002662, A002663, A002664, A035038, A035039, A035040, A035041, etc. The triangles A008949, A054143 and A055248 also appear in the half of the array which is not powers of 2.

Formula

T(n, k)=T(n-1, k-1)+T(n, k-1) with T(0, k)=1, T(1, 1)=1, T(0, 2n)=T(1, n) and T(0, 2n+1)=0. Coefficient of x^n in expansion of (1+x)^k/(1-x^2).

A106471 A number triangle with duplicated columns of the form 2^n - Sum_{j=0..2k-1} C(n,j).

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 4, 4, 1, 16, 8, 11, 4, 1, 32, 16, 26, 11, 6, 1, 64, 32, 57, 26, 22, 6, 1, 128, 64, 120, 57, 64, 22, 8, 1, 256, 128, 247, 120, 163, 64, 37, 8, 1, 512, 256, 502, 247, 382, 163, 130, 37, 10, 1, 1024, 512, 1013, 502, 848, 382, 386, 130, 56, 10, 1, 2048, 1024
Offset: 0

Views

Author

Paul Barry, May 03 2005

Keywords

Comments

Columns include A000079, A000295, A002663, A035038, A035040.
Row sums are A106472.
Product of binomial matrix binomial(n,k) and number triangle A106465.

Examples

			Triangle begins
   1;
   2,  1;
   4,  2,  1;
   8,  4,  4,  1;
  16,  8, 11,  4,  1;
  32, 16, 26, 11,  6, 1;
  64, 32, 57, 26, 22, 6, 1;

Formula

Column 2k has g.f. x^(2*k)/((1-2*x)*(1-x)^(2*k-2)).
Column 2k+1 has g.f. x^(2*k+1)/((1-2*x)*(1-x)^(2*k)).

A232774 Triangle T(n,k), read by rows, given by T(n,0)=1, T(n,1)=2^(n+1)-n-2, T(n,n)=(-1)^(n-1) for n > 0, T(n,k)=T(n-1,k)-T(n-1,k-1) for 1 < k < n.

Original entry on oeis.org

1, 1, 1, 1, 4, -1, 1, 11, -5, 1, 1, 26, -16, 6, -1, 1, 57, -42, 22, -7, 1, 1, 120, -99, 64, -29, 8, -1, 1, 247, -219, 163, -93, 37, -9, 1, 1, 502, -466, 382, -256, 130, -46, 10, -1, 1, 1013, -968, 848, -638, 386, -176, 56, -11, 1, 2036, -1981, 1816, -1486, 1024
Offset: 0

Views

Author

Philippe Deléham, Nov 30 2013

Keywords

Comments

Row sums are A000079(n) = 2^n.
Diagonal sums are A024493(n+1) = A130781(n).
Sum_{k=0..n} T(n,k)*x^k = -A003063(n+2), A159964(n), A000012(n), A000079(n), A001045(n+2), A056450(n), (-1)^(n+1)*A232015(n+1) for x = -2, -1, 0, 1, 2, 3, 4 respectively.

Examples

			Triangle begins:
  1;
  1,    1;
  1,    4,   -1;
  1,   11,   -5,   1;
  1,   26,  -16,   6,   -1;
  1,   57,  -42,  22,   -7,   1;
  1,  120,  -99,  64,  -29,   8,   -1;
  1,  247, -219, 163,  -93,  37,   -9,  1;
  1,  502, -466, 382, -256, 130,  -46, 10,  -1;
  1, 1013, -968, 848, -638, 386, -176, 56, -11, 1;

Crossrefs

Columns: A000012, A000295, -A002662, A002663, -A002664, A035038, -A035039, A035040, -A035041, A035042.
Cf. A000079, A055248, A024493, A130781, A000302.
Cf. also A003063, A159964, A000012, A001045, A056450, A232015.

Formula

G.f.: Sum_{n>=0, k=0..n} T(n,k)*y^k*x^n=(1+2*(y-1)*x)/((1-2*x)*(1+(y-1)*x)).
|T(2*n,n)| = 4^n = A000302(n).
T(n,k) = (-1)^(k-1) * (Sum_{i=0..n-k} (2^(i+1)-1) * binomial(n-i-1,k-1)) for 0 < k <= n and T(n,0) = 1 for n >= 0. - Werner Schulte, Mar 22 2019
Showing 1-8 of 8 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.