

A000295


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


178



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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.
A107907(a(n+2)) = A000079(n+2).  Reinhard Zumkeller, May 28 2005
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 array defined in A125127 = Array L(k,n) read by antidiagonals: kstep Lucas numbers.  Jonathan Vos Post, Nov 22 2006
Number of partitions of an nset 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, 1234, 1243, 1342, 1234, 1234, 1324, 1423, 1234, 1243 and 1234.  Emeric Deutsch, Oct 28 2006
n divides a(n+1) for n = A014741(n) = {1, 2, 6, 18, 42, 54, 126, 162, 294, 342, 378, 486, 882, 1026, ...}.  Alexander Adamchuk, Nov 03 2006
(Number of permutations avoiding patterns 321, 2413, 3412, 21534) minus one.  JeanLuc 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 nth 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 nth 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 n1, such that each path from root to any leaf contains each label from {1,2,..,n1} 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 pruninggrafting 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 subtriangle 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^n1)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) errorcorrecting 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} (k1)*2^(nk).  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 (nonnull) connected induced subgraphs in the ntriangular 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 (bottomup) 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(n1) 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(n1) 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 nset that have more than one element.  Eric M. Schmidt, Mar 13 2021


REFERENCES

O. Bottema, Problem #562, Nieuw Archief voor Wiskunde, 28 (1980) 115.
L. Comtet, "Permutations by Number of Rises; Eulerian Numbers." §6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 51 and 240246, 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. AddisonWesley, Reading, MA, 1990.
D. E. Knuth, The Art of Computer Programming. AddisonWesley, 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

T. D. Noe, Table of n, a(n) for n = 0..500
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
J. L. Baril and J. M. Pallo, The pruninggrafting lattice of binary trees, Theoretical Computer Science, 409, 2008, 382393.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron, M. Gadouleau, J. D. Mitchell, and Y. Peresse, Chains of subsemigroups, arXiv preprint arXiv:1501.06394 [math.GR], 2015. See Table 4.
Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.
Benjamin Hellouin de Menibus and Yvan Le Borgne, Asymptotic behaviour of the onedimensional "rockpaperscissors" cyclic cellular automaton, arXiv:1903.12622 [math.PR], 2019.
Karl Dilcher and Maciej Ulas, Arithmetic properties of polynomial solutions of the Diophantine equation P(x)x^(n+1)+Q(x)(x+1)^(n+1) = 1, arXiv:1909.11222 [math.NT], 2019.
Filippo Disanto, Some Statistics on the Hypercubes of Catalan Permutations, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.2.
J. M. Dusel, Balanced parabolic quotients and branching rules for Demazure crystals, J Algebr Comb (2016) 44: 363. DOI: 10.1007/s108010160673y.
Pascal Floquet, Serge Domenech and Luc Pibouleau, Combinatorics of Sharp Separation System synthesis : Generating functions and Search Efficiency Criterion, Industrial Engineering and Chemistry Research, 33, pp. 440443, 1994.
Pascal Floquet, Serge Domenech, Luc Pibouleau and Said Aly, Some Complements in Combinatorics of Sharp Separation System Synthesis, American Institute of Chemical Engineering Journal, 39(6), pp. 975978, 1993.
E. T. Frankel, A calculus of figurate numbers and finite differences, American Mathematical Monthly, 57 (1950), 1425. [Annotated scanned copy]
Joël Gay, Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups, Doctoral Thesis, Discrete Mathematics [cs.DM], Université ParisSaclay, 2018.
R. K. Guy, Letter to N. J. A. Sloane
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 388
Lucas Kang, Investigation of Rule 73 as Case Study of Class 4 LongDistance Cellular Automata, arXiv preprint arXiv:1310.3311 [nlin.CG], 2013.
O. Kullmann and X. Zhao, Bounds for variables with few occurrences in conjunctive normal forms, arXiv preprint arXiv:1408.0629 [math.CO], 2014.
César Eliud Lozada, Centroids of Pascal triangles
Candice A. Marshall, Construction of PseudoInvolutions in the Riordan Group, Dissertation, Morgan State University, 2017.
J. C. P. Miller, Letter to N. J. A. Sloane, Mar 26 1971
J. W. Moon, A problem on arcs without bypasses in tournaments, J. Combinatorial Theory Ser. B 21 (1976), no. 1, 7175. MR0427129(55 #165).
Agustín Moreno Cañadas, Hernán Giraldo, and Gabriel Bravo Rios, On the Number of Sections in the AuslanderReiten Quiver of Algebras of Dynkin Type, Far East Journal of Mathematical Sciences (FJMS), Vol. 101, No. 8 (2017), pp. 16311654.
Nagatomo Nakamura, PseudoNormal Random Number Generation via the Eulerian Numbers, Josai Mathematical Monographs, vol 8, p 8595, 2015.
E. Norton, Symplectic Reflection Algebras in Positive Characteristic as Ore Extensions, arXiv preprint arXiv:1302.5411 [math.RA], 2013.
Ronald Orozco López, Solution of the Differential Equation y^(k)= e^(a*y), Special Values of Bell Polynomials and (k,a)Autonomous Coefficients, Universidad de los Andes (Colombia 2021).
J. M. Pallo, Weak associativity and restricted rotation, Information Processing Letters, 109, 2009, 514517.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257260. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
J. Riordan, Review of Frankel (1950) [Annotated scanned copy]
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 20 (1968), 816.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 816. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Chromatic Invariant
Eric Weisstein's World of Mathematics, Prism Graph
Wikipedia, Reed's Law
Robert G. Wilson v, Letter to N. J. A. Sloane, Apr. 1994
Anssi YliJyra, On Dependency Analysis via Contractions and Weighted FSTs, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133158.  N. J. A. Sloane, Dec 25 2012
Index entries for linear recurrences with constant coefficients, signature (4,5,2).


FORMULA

a(n) = 2^n  n  1.
G.f.: x^2/((12*x)*(1x)^2).
E.g.f.: exp(x)*(exp(x)1x).  Emeric Deutsch, Oct 28 2006
a(0)=0, a(1)=0, a(n) = 3*a(n1)  2*a(n2) + 1.  Miklos Kristof, Mar 09 2005
a(0)=0, a(n) = 2*a(n1) + 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..n1} i+a(i) for i > 1.  Gerald McGarvey, Jun 12 2004
a(n+1) = Sum_{k=0..n} (nk)*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((n1)/2)} binomial(nk1, k+1)*2^(nk2)*(1/2)^k.  Paul Barry, Oct 25 2004
a(0) = 0; a(n) = Stirling2(n,2) + a(n1).  Thomas Wieder, Feb 18 2007
a(n) = A000325(n)1.  Jonathan Vos Post, Aug 29 2008
a(0) = 0, a(n) = Sum_{k=0..n1} 2^k  1.  Doug Bell, Jan 19 2009
a(n) = A000225(n)  n.  Zerinvary Lajos, May 29 2009
a(n) = n*(2F1([1,1n],[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)1x); 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, 4step).  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^(n1)1} A001511(i).  David Siegers, Feb 26 2019


EXAMPLE

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 + ...


MAPLE

[ seq(2^nn1, n=1..50) ];
A000295 := z/(2*z1)/(z1)**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_] = n*(HypergeometricPFQ[{1, 1  n}, {2}, 1]  1); Table[a[n], {n, 1, 30}] (* 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, 20}] (* Eric W. Weisstein, Nov 16 2017 *)


PROG

(PARI) a(n)=2^nn1 \\ Charles R Greathouse IV, Jun 10 2011
(Haskell) a000295 n = 2^n  n  1  Reinhard Zumkeller, Nov 25 2013
(MAGMA) [2^nn1: n in [0..40]]; // Vincenzo Librandi, Jul 29 2015


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. A008949, A000079, A002663, A002664, A035039A035042, A000108, A014741, A130128, A130330, A131768, A130321, A131816, A000975, A016031.
Partial sums of A000225.
Row sums of triangle A014473. Second column of triangles A112493 and A112500.
Cf. A000325.  Jonathan Vos Post, Aug 29 2008
A000295(n)A002662(n) = A000217(n1) for n>0.  Geoffrey Critzer, Feb 11 2009
Row sums of A143291.  Alois P. Heinz, Jun 01 2009
Sequences A125128 and A130103 are essentially the same.  M. F. Hasler, Jul 30 2015
Column k=1 of A124324.
Sequence in context: A030196 A248425 A130103 * A125128 A034334 A036891
Adjacent sequences: A000292 A000293 A000294 * A000296 A000297 A000298


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



