|
| |
|
|
A000295
|
|
Eulerian numbers (Euler's triangle: column k=2 of A008292, column k=1 of A173018)
(Formerly M3416 N1382)
|
|
100
| |
|
|
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; 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 (deutsch(AT)duke.poly.edu), 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 (reinhard.zumkeller(AT)gmail.com), May 28 2005
a(n+1) is the convolution of nonnegative integers (A001477) and powers of two (A000079) - Graeme McRae (g_m(AT)mcraefamily.com), Jun 07 2006
Partial sum of main diagonal of array defined in A125127 = Array L(k,n) read by antidiagonals: k-step Lucas numbers. - Jonathan Vos Post (jvospost3(AT)gmail.com), 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 (deutsch(AT)duke.poly.edu), 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 (alex(AT)kolmogorov.com), Nov 03 2006
(Number of permutations avoiding patterns 321, 2413, 3412, 21534) minus one. - J.-L. Baril (barjl(AT)u-bourgogne.fr), Nov 01 2007, Mar 21 2008
The chromatic invariant of the prism graph P_n for n=>3. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 29 2008]
a(n) is the number of binary sequences of length n having at least two 0's. [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Feb 11 2009]
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). [From Kailasam Viswanathan Iyer (kvi(AT)nitt.edu), Mar 30 2009]
Chromatic invariant of the prism graph Y_n
Starting with 1 = A000975 convolved with [1, 2, 2, 2,...] [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 02 2009]
Comment from Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009: Number of labellings 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.
Comment from Jean Pallo, Jan 08 2010: 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.
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 24 2010: (Start)
Starting with "1" = the eigensequence of a triangle with the triangular series
as the left border and the rest 1's. (End)
Contribution from L. Edson Jeffery, Dec 28 2011 (Start):
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;
... (End)
|
|
|
REFERENCES
| J. L. Baril and J. M. Pallo: The pruning-grafting lattice of binary trees, Theoretical Computer Science, 409, 2008, 382-393.
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 240-246, 1974.
F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 151.
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. 440-443, 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. 975-978, 1993.
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. M. Pallo: Weak associativity and restricted rotation, Information Processing Letters, 109, 2009, 514-517.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 215.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 20 (1968), 8-16.
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
Index entries for sequences related to linear recurrences with constant coefficients, signature (4,-5,2).
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 388
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Eric W. Weisstein, Chromatic Invariant.
Eric Weisstein's World of Mathematics, Chromatic Invariant
|
|
|
FORMULA
| a(n)=2^n - n - 1.
G.f.: x^2/((1-2*x)*(1-x)^2).
E.g.f.: exp(x)*(exp(x)-1-x). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 28 2006
a(0)=0, a(1)=0, a(n)=3*a(n-1)-2*a(n-2)+1 - Miklos Kristof (kristmikl(AT)freemail.hu), Mar 09 2005
a(1)=0, a(n)=2*a(n-1)+n-1, n>1.
a(n)=sum(k=2..n, binomial(n, k) ) - Paul Barry (pbarry(AT)wit.ie), Jun 05 2003
a(n+1)=sum(1<=i<=n, sum(1<=j<=i, C(i, j))) - Benoit Cloitre (benoit7848c(AT)orange.fr), Sep 07 2003
a(n+1)=2^n*sum(k=0, n, k/2^k) - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 26 2003
a(0)=0, a(1)=0, a(n) = Sum i=0..n-1 i+a(i) for i > 1 - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Jun 12 2004
a(n+1)=sum(k=0..n, (n-k)*2^k ). - Paul Barry (pbarry(AT)wit.ie), 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 (pbarry(AT)wit.ie), 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 (pbarry(AT)wit.ie), Oct 25 2004
a(0) = 0; a(n)=stirling2(n,2)+a(n-1). - Thomas Wieder (thomas.wieder(AT)t-online.de), Feb 18 2007
Equals row sums of triangle A130128 starting (1, 4, 11, 26, 57,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 11 2007
Starting (1, 4, 11, 26,...) gives row sums of triangle A130330 which is composed of (1,3,7,15...) in every column, thus: row sums of (1; 3,1; 7,3,1;...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 24 2007
Row sums of triangle A131768 starting (1, 4, 11, 26, 57, 120,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 13 2007
Sequence starting (1, 4, 11, 26, 57,...) = A130321 * (1, 2, 3,...). Sequence starting (1, 4, 11, 26, 57,...) = binomial transform of (1, 3, 4, 4, 4,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 27 2007
Row sums of triangle A131816 starting (1, 4, 11, 26,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 30 2007
a(n) = A000325(n)-1. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 29 2008]
a(0) = 0, a(n) = sum(k=0..n-1, 2^k - 1 ) [From Doug Bell (bell.doug(AT)gmail.com), Jan 19 2009]
a(n) =A000225(n)-n . [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 29 2009]
a(n) = n*(2F1([1,1-n],[2],-1) - 1) [From Olivier Gerard, (olivier.gerard(AT)gmail.com) Mar 29 2011]
|
|
|
MAPLE
| [ seq(2^n-n-1, n=1..50) ];
A000295:=-z/(2*z-1)/(z-1)**2; [S. Plouffe in his 1992 dissertation.]
|
|
|
MATHEMATICA
| lst={}; s=0; Do[s+=(s-n); AppendTo[lst, s], {n, 5!}]; lst [From Vladimir Orlovsky (4vladimir(AT)gmail.com), Oct 10 2008]
a[n_] = n*(HypergeometricPFQ[{1, 1-n}, {2}, -1] - 1); Table[a[n], {n, 1, 30}] [From Olivier Gerard, Mar 29 2011]
|
|
|
PROG
| (PARI) a(n)=2^n-n-1 \\ Charles R Greathouse IV, Jun 10 2011
|
|
|
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, A000225, A002663, A002664, A035039-A035042, A000108, A014741, A130128, A130330, A131768, A130321, A131816, A000975.
Partial sums of A000225.
Row sums of triangle A014473. Second column of triangles A112493 and A112500.
Cf. A000325. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 29 2008]
A000295-A002662=A000217 [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Feb 11 2009]
Row sums of A143291. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jun 01 2009]
Sequence in context: A030196 A125128 A130103 * A034334 A036891 A183276
Adjacent sequences: A000292 A000293 A000294 * A000296 A000297 A000298
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
