A046739 -id:A046739 - cp's OEIS frontend

A008292 Triangle of Eulerian numbers T(n,k) (n >= 1, 1 <= k <= n) read by rows.

1, 1, 1, 1, 4, 1, 1, 11, 11, 1, 1, 26, 66, 26, 1, 1, 57, 302, 302, 57, 1, 1, 120, 1191, 2416, 1191, 120, 1, 1, 247, 4293, 15619, 15619, 4293, 247, 1, 1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1, 1, 1013, 47840, 455192, 1310354, 1310354, 455192, 47840, 1013, 1

Offset: 1

N. J. A. Sloane, Mar 15 1996

The indexing used here follows that given in the classic books by Riordan and Comtet. For two other versions see A173018 and A123125. - N. J. A. Sloane, Nov 21 2010
Coefficients of Eulerian polynomials. Number of permutations of n objects with k-1 rises. Number of increasing rooted trees with n+1 nodes and k leaves.
T(n,k) = number of permutations of [n] with k runs. T(n,k) = number of permutations of [n] requiring k readings (see the Knuth reference). T(n,k) = number of permutations of [n] having k distinct entries in its inversion table. - Emeric Deutsch, Jun 09 2004
T(n,k) = number of ways to write the Coxeter element s_{e1}s_{e1-e2}s_{e2-e3}s_{e3-e4}...s_{e_{n-1}-e_n} of the reflection group of type B_n, using s_{e_k} and as few reflections of the form s_{e_i+e_j}, where i = 1, 2, ..., n and j is not equal to i, as possible. - Pramook Khungurn (pramook(AT)mit.edu), Jul 07 2004
Subtriangle for k>=1 and n>=1 of triangle A123125. - Philippe Deléham, Oct 22 2006
T(n,k)/n! also represents the n-dimensional volume of the portion of the n-dimensional hypercube cut by the (n-1)-dimensional hyperplanes x_1 + x_2 + ... x_n = k, x_1 + x_2 + ... x_n = k-1; or, equivalently, it represents the probability that the sum of n independent random variables with uniform distribution between 0 and 1 is between k-1 and k. - Stefano Zunino, Oct 25 2006
[E(.,t)/(1-t)]^n = n!*Lag[n,-P(.,t)/(1-t)] and [-P(.,t)/(1-t)]^n = n!*Lag[n, E(.,t)/(1-t)] umbrally comprise a combinatorial Laguerre transform pair, where E(n,t) are the Eulerian polynomials and P(n,t) are the polynomials in A131758. - Tom Copeland, Sep 30 2007
From Tom Copeland, Oct 07 2008: (Start)
G(x,t) = 1/(1 + (1-exp(x*t))/t) = 1 + 1*x + (2+t)*x^2/2! + (6+6*t+t^2)*x^3/3! + ... gives row polynomials for A090582, the reverse f-polynomials for the permutohedra (see A019538).
G(x,t-1) = 1 + 1*x + (1+t)*x^2/2! + (1+4*t+t^2)*x^3/3! + ... gives row polynomials for A008292, the h-polynomials for permutohedra (Postnikov et al.).
G((t+1)*x, -1/(t+1)) = 1 + (1+t)*x + (1+3*t+2*t^2)*x^2/2! + ... gives row polynomials for A028246.
(End)
A subexceedant function f on [n] is a map f:[n] -> [n] such that 1 <= f(i) <= i for all i, 1 <= i <= n. T(n,k) equals the number of subexceedant functions f of [n] such that the image of f has cardinality k [Mantaci & Rakotondrajao]. Example T(3,2) = 4: if we identify a subexceedant function f with the word f(1)f(2)...f(n) then the subexceedant functions on [3] are 111, 112, 113, 121, 122 and 123 and four of these functions have an image set of cardinality 2. - Peter Bala, Oct 21 2008
Further to the comments of Tom Copeland above, the n-th row of this triangle is the h-vector of the simplicial complex dual to a permutohedron of type A_(n-1). The corresponding f-vectors are the rows of A019538. For example, 1 + 4*x + x^2 = y^2 + 6*y + 6 and 1 + 11*x + 11*x^2 + x^3 = y^3 + 14*y^2 + 36*y + 24, where x = y + 1, give [1,6,6] and [1,14,36,24] as the third and fourth rows of A019538. The Hilbert transform of this triangle (see A145905 for the definition) is A047969. See A060187 for the triangle of Eulerian numbers of type B (the h-vectors of the simplicial complexes dual to permutohedra of type B). See A066094 for the array of h-vectors of type D. For tables of restricted Eulerian numbers see A144696 - A144699. - Peter Bala, Oct 26 2008
For a natural refinement of A008292 with connections to compositional inversion and iterated derivatives, see A145271. - Tom Copeland, Nov 06 2008
The polynomials E(z,n) = numerator(Sum_{k>=1} (-1)^(n+1)*k^n*z^(k-1)) for n >=1 lead directly to the triangle of Eulerian numbers. - Johannes W. Meijer, May 24 2009
From Walther Janous (walther.janous(AT)tirol.com), Nov 01 2009: (Start)
The (Eulerian) polynomials e(n,x) = Sum_{k=0..n-1} T(n,k+1)*x^k turn out to be also the numerators of the closed-form expressions of the infinite sums:
S(p,x) = Sum_{j>=0} (j+1)^p*x^j, that is
S(p,x) = e(p,x)/(1-x)^(p+1), whenever |x| < 1 and p is a positive integer.
(Note the inconsistent use of T(n,k) in the section listing the formula section. I adhere tacitly to the first one.) (End)
If n is an odd prime, then all numbers of the (n-2)-th and (n-1)-th rows are in the progression k*n+1. - Vladimir Shevelev, Jul 01 2011
The Eulerian triangle is an element of the formula for the r-th successive summation of Sum_{k=1..n} k^j which appears to be Sum_{k=1..n} T(j,k-1) * binomial(j-k+n+r, j+r). - Gary Detlefs, Nov 11 2011
Li and Wong show that T(n,k) counts the combinatorially inequivalent star polygons with n+1 vertices and sum of angles (2*k-n-1)*Pi. An equivalent formulation is: define the total sign change S(p) of a permutation p in the symmetric group S_n to be equal to Sum_{i=1..n} sign(p(i)-p(i+1)), where we take p(n+1) = p(1). T(n,k) gives the number of permutations q in S_(n+1) with q(1) = 1 and S(q) = 2*k-n-1. For example, T(3,2) = 4 since in S_4 the permutations (1243), (1324), (1342) and (1423) have total sign change 0. - Peter Bala, Dec 27 2011
Xiong, Hall and Tsao refer to Riordan and mention that a traditional Eulerian number A(n,k) is the number of permutations of (1,2...n) with k weak exceedances. - Susanne Wienand, Aug 25 2014
Connections to algebraic geometry/topology and characteristic classes are discussed in the Buchstaber and Bunkova, the Copeland, the Hirzebruch, the Lenart and Zainoulline, the Losev and Manin, and the Sheppeard links; to the Grassmannian, in the Copeland, the Farber and Postnikov, the Sheppeard, and the Williams links; and to compositional inversion and differential operators, in the Copeland and the Parker links. - Tom Copeland, Oct 20 2015
The bivariate e.g.f. noted in the formulas is related to multiplying edges in certain graphs discussed in the Aluffi-Marcolli link. See p. 42. - Tom Copeland, Dec 18 2016
Distribution of left children in treeshelves is given by a shift of the Eulerian numbers. Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link. See A278677, A278678 or A278679 for more definitions and examples. - Sergey Kirgizov, Dec 24 2016
The row polynomial P(n, x) = Sum_{k=1..n} T(n, k)*x^k appears in the numerator of the o.g.f. G(n, x) = Sum_{m>=0} S(n, m)*x^m with S(n, m) = Sum_{j=0..m} j^n for n >= 1 as G(n, x) = Sum_{k=1..n} P(n, x)/(1 - x)^(n+2) for n >= 0 (with 0^0=1). See also triangle A131689 with a Mar 31 2017 comment for a rewritten form. For the e.g.f see A028246 with a Mar 13 2017 comment. - Wolfdieter Lang, Mar 31 2017
For relations to Ehrhart polynomials, volumes of polytopes, polylogarithms, the Todd operator, and other special functions, polynomials, and sequences, see A131758 and the references therein. - Tom Copeland, Jun 20 2017
For relations to values of the Riemann zeta function at integral arguments, see A131758 and the Dupont reference. - Tom Copeland, Mar 19 2018
Normalized volumes of the hypersimplices, attributed to Laplace. (Cf. the De Loera et al. reference, p. 327.) - Tom Copeland, Jun 25 2018

			The triangle T(n, k) begins:
n\k 1    2     3      4       5       6      7     8    9 10 ...
1:  1
2:  1    1
3:  1    4     1
4:  1   11    11      1
5:  1   26    66     26       1
6:  1   57   302    302      57       1
7:  1  120  1191   2416    1191     120      1
8:  1  247  4293  15619   15619    4293    247     1
9:  1  502 14608  88234  156190   88234  14608   502    1
10: 1 1013 47840 455192 1310354 1310354 455192 47840 1013  1
... Reformatted. - _Wolfdieter Lang_, Feb 14 2015
-----------------------------------------------------------------
E.g.f. = (y) * x^1 / 1! + (y + y^2) * x^2 / 2! + (y + 4*y^2 + y^3) * x^3 / 3! + ... - _Michael Somos_, Mar 17 2011
Let n=7. Then the following 2*7+1=15 consecutive terms are 1(mod 7): a(15+i), i=0..14. - _Vladimir Shevelev_, Jul 01 2011
Row 3: The plane increasing 0-1-2 trees on 3 vertices (with the number of colored vertices shown to the right of a vertex) are
.
.   1o (1+t)         1o t         1o t
.   |                / \          / \
.   |               /   \        /   \
.   2o (1+t)      2o     3o    3o    2o
.   |
.   |
.   3o
.
The total number of trees is (1+t)^2 + t + t = 1 + 4*t + t^2.

Mohammad K. Azarian, Geometric Series, Problem 329, Mathematics and Computer Education, Vol. 30, No. 1, Winter 1996, p. 101. Solution published in Vol. 31, No. 2, Spring 1997, pp. 196-197.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 106.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 243.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 254; 2nd. ed., p. 268.[Worpitzky's identity (6.37)]
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1998, Vol. 3, p. 47 (exercise 5.1.4 Nr. 20) and p. 605 (solution).
Meng Li and Ron Goldman. "Limits of sums for binomial and Eulerian numbers and their associated distributions." Discrete Mathematics 343.7 (2020): 111870.
Anthony Mendes and Jeffrey Remmel, Generating functions from symmetric functions, Preliminary version of book, available from Jeffrey Remmel's home page http://math.ucsd.edu/~remmel/
K. Mittelstaedt, A stochastic approach to Eulerian numbers, Amer. Math. Mnthly, 127:7 (2020), 618-628.
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 215.
R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Figure M3416, Academic Press, 1995.
H. S. Wall, Analytic Theory of Continued Fractions, Chelsea, 1973, see p. 208.
D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 101.

T. D. Noe, Rows 1 to 100 of triangle, flattened.
V. E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015.
Takashi Agoh, On Generalized Euler Numbers and Polynomials Related to Values of the Lerch Zeta Function, Integers (2020) Vol. 20, Article A5.
P. Aluffi and M. Marcolli, Feynman motives and deletion-contraction, arXiv:0907.3225 [math-ph], 2009.
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. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
J. F. Barbero G., J. Salas and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv:1307.5624 [math.CO], 2013.
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Patterns in treeshelves, arXiv:1611.07793 [cs.DM], 2016.
Jean-Luc Baril and José L. Ramírez, Some distributions in increasing and flattened permutations, arXiv:2410.15434 [math.CO], 2024. See p. 6.
Paul Barry, Eulerian polynomials as moments, via exponential Riordan arrays, arXiv preprint arXiv:1105.3043 [math.CO], 2011, J. Int. Seq. 14 (2011) # 11.9.5.
Paul Barry, Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays, arXiv:1105.3044 [math.CO], 2011.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.
D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.
H. Belbachir, M. Rahmani, and B. Sury, Sums Involving Moments of Reciprocals of Binomial Coefficients, J. Int. Seq. 14 (2011) #11.6.6.
Hacene Belbachir, Mourad Rahmani and B. Sury, Alternating Sums of the Reciprocals of Binomial Coefficients, Journal of Integer Sequences, Vol. 15 (2012), #12.2.8.
Edward A. Bender, Central and local limit theorems applied to asymptotic enumeration Journal of Combinatorial Theory, Series A, 15(1) (1973), 91-111. See Example 5.3.
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
V. Buchstaber and E. Bunkova, Elliptic formal group laws, integral Hirzebruch genera and Krichever genera, arXiv:1010.0944 [math-ph], 2010, p. 35.
Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth, and Teresa Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv:1812.07112 [math.CO], 2018.
F. Cachazo, S. He, and E. Y. Yuan, Scattering in Three Dimensions from Rational Maps, arXiv:1306.2962 [hep-th], 2013.
F. Cachazo, S. Mizera, and G. Zhang, Scattering equations: Real solutions and particles on a line, arXiv:1609.00008 [hep-th], 2016.
David Callan, Problem 498, The College Mathematics Journal, Vol. 24, No. 2 (Mar., 1993), pp. 183-190 (8 pages).
David Callan, Shi-Mei Ma, and Toufik Mansour, Some Combinatorial Arrays Related to the Lotka-Volterra System, Electronic Journal of Combinatorics, Volume 22, Issue 2 (2015), Paper #P2.22.
Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
L. Carlitz, Eulerian numbers and operators, Collectanea Mathematica 24:2 (1973), pp. 175-200.
Leonard Carlitz, Permutations, sequences and special functions, SIAM Review 17, no. 2 (1975): 298-322.
L. Carlitz et al., Permutations and sequences with repetitions by number of increases, J. Combin. Theory, 1 (1966), 350-374, p. 351.
L. Carlitz, D. C. Kurtz, R. Scoville and O. P. Stackelberg, Asymptotic properties of Eulerian numbers, Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 23(1), 47-54 (1972).
Raphaël Cerf and Joseba Dalmau, The quasispecies distribution, arXiv:1609.05738 [q-bio.PE], 2016.
Mircea I. Cirnu, Determinantal formulas for sum of generalized arithmetic-geometric series, Boletin de la Asociacion Matematica Venezolana, Vol. XVIII, No. 1 (2011), p. 13.
Tom Copeland, The Elliptic Lie Triad: Riccati and KdV Equations, Infinigens, and Elliptic Genera, 2015.
Tom Copeland, Reciprocity and Umbral Witchcraft: An Eve with Stirling, Bernoulli, Archimedes, Euler, Laguerre, and Worpitzky, 2020.
J. A. De Loera, J. Rambau, and F. Santos, Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, Vol. 25, Springer-Verlag, 2010.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
J. Desarmenien and D. Foata, The signed Eulerian Numbers
J. Desarmenien and D. Foata, The signed Eulerian numbers, Discrete Math. 99 (1992), no. 1-3, 49-58.
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
B. Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths Thesis, Brandeis Univ., Aug. 2008.
C. Dupont, Odd zeta motive and linear forms in odd zeta values, arXiv:1601.00950 [math.AG], 2016.
A. Dzhumadil'daev and D. Yeliussizov, Power sums of binomial coefficients, Journal of Integer Sequences, 16 (2013), Article 13.1.6.
R. Ehrenborg, M. Readdy, and E. Steingrímsson, Mixed Volumes and Slices of the Cube, J Comb. Theory, Series A 81, Issue 1, Jan. 1998, 121-126.
M. Farber and A. Postnikov, Arrangements of equal minors in the positive Grassmannian, arXiv preprint arXiv:1502.01434 [math.CO], 2015.
Joseph A. Farrow, A Monte Carlo Approach to the 4D Scattering Equations, arXiv:1806.02732 [hep-th], 2018.
FindStat - Combinatorial Statistic Finder, The number of descents of a permutation, The number of exceedances (also excedences) of a permutation, and The number of weak exceedances (also weak excedences) of a permutation
D. Foata, Distributions eulériennes et mahoniennes sur le groupe des permutations, pp. 27-49 of M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977.
D. Foata and M. Schutzenberger, Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Math., no.138, Springer Verlag 1970; arXiv:math/0508232 [math.CO], 2005.
Dominique Foata and Guo-Niu Han, Doubloons and new q-tangent numbers, Quart. J. Math. 62 (2) (2011) 417-432.
E. T. Frankel, A calculus of figurate numbers and finite differences, American Mathematical Monthly, 57 (1950), 14-25. [Annotated scanned copy]
Ghislain R. Franssens, On a Number Pyramid Related to the Binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.
Jason Fulman, Gene B. Kim, Sangchul Lee, and T. Kyle Petersen, On the joint distribution of descents and signs of permutations, arXiv:1910.04258 [math.CO], 2019.
D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.
S. Garoufalidis and R. Kashaev, From state integrals to q-series, arXiv:1304.2705 [math.GT], 2013.
Ira Gessel, The Smith College diploma problem.
Alexander Gnedin and Grigori Olshanski, The boundary of the Eulerian number triangle, arXiv:math/0602610 [math.PR], 2006.
Mats Granvik, Do these ratios of the Eulerian numbers converge to the logarithm of x?, Mathematics Stack Exchange, Dec 30 2014.
Jim Haglund and Mirko Visontai, Stable multivariate Eulerian polynomials and generalized Stirling permutations.
Thomas Hameister, Sujit Rao, and Connor Simpson, Chow rings of matroids and atomistic lattices, research paper, University of Minnesota, 2017, also arXiv:1802.04241 [math.CO], 2018.
A. J. J. Heidrich, On the factorization of Eulerian polynomials, Journal of Number Theory, 18(2):157-168, 1984.
Herwig Hauser and Christoph Koutschan, Multivariate linear recurrences and power series division, Discrete Math. 312 (2012), no. 24, 3553--3560. MR2979485.
F. Hirzebruch, Eulerian polynomials, Münster J. of Math. 1 (2008), pp. 9-12.
P. Hitczenko and S. Janson, Weighted random staircase tableaux, arXiv:1212.5498 [math.CO], 2012.
Matthew Hubbard and Tom Roby, Pascal's Triangle From Top to Bottom
Hsien-Kuei Hwang, Hua-Huai Chern, and Guan-Huei Duh, An asymptotic distribution theory for Eulerian recurrences with applications, arXiv:1807.01412 [math.CO], 2018.
Svante Janson, Euler-Frobenius numbers and rounding, arXiv:1305.3512 [math.PR], 2013.
Lucas Kang, Investigation of Rule 73 as Case Study of Class 4 Long-Distance Cellular Automata, arXiv:1310.3311 [nlin.CG], 2013.
A. Kerber and K.-J. Thuerlings, Eulerian numbers, Foulkes characters and Lefschetz characters of S_n, Séminaire Lotharingien, Vol. 8 (1984), 31-36.
Takao Komatsu and Yuan Zhang, Weighted Sylvester sums on the Frobenius set in more variables, arXiv:2101.04298 [math.NT], 2021. Mentions this sequence.
A. R. Kräuter, Über die Permanente gewisser zirkulärer Matrizen..., Séminaire Lotharingien de Combinatoire, B11b (1984), 11 pp.
H. K. Krishnapriyan, Eulerian Polynomials and Faulhaber's Result on Sums of Powers of Integers, he College Mathematics Journal, Vol. 26, No. 2 (Mar., 1995), pp. 118-123 (6 pages).
D. H. Lehmer, Generalized Eulerian numbers, J. Combin. Theory Ser.A 32 (1982), no. 2, 195--215. MR0654621 (83k:10026).
C. Lenart and K. Zainoulline, Towards generalized cohomology Schubert calculus via formal root polynomials, arXiv:1408.5952 [math.AG], 2014.
Nan Li, Ehrhart h*-vectors of hypersimplices, Discr. Comp. Geom. 48 (2012) 847-878, Theorem 1.1
M-H. Li and N-C. Wong, Sums of angles of star polygons and the Eulerian Numbers, Southeast Asian Bulletin of Mathematics 2004.
Feihu Liu, Guoce Xin, and Chen Zhang, Ehrhart Polynomials of Order Polytopes: Interpreting Combinatorial Sequences on the OEIS, arXiv:2412.18744 [math.CO], 2024. See p. 12.
A. Losev and Y. Manin, New moduli spaces of pointed curves and pencils of flat connections, arXiv:0001003 [math.AG], 2000 (p. 8)
Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO], 2012.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
Shi-Mei Ma, A family of two-variable derivative polynomials for tangent and secant, El J. Combinat. 20 (1) (2013) P11.
Shi-Mei Ma, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, Alternating Eulerian polynomials and left peak polynomials, arXiv:2104.09374, 2021
Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, On certain combinatorial expansions of descent polynomials and the change of grammars, arXiv:1802.02861 [math.CO], 2018.
S.-M. Ma, T. Mansour, and M. Schork, Normal ordering problem and the extensions of the Stirling grammar, arXiv:1308.0169 [math.CO], 2013.
Shi-Mei Ma, T. Mansour, and D. Callan, Some combinatorial arrays related to the Lotka-Volterra system, arXiv:1404.0731 [math.CO], 2014.
Shi-Mei Ma and Hai-Na Wang, Enumeration of a dual set of Stirling permutations by their alternating runs, arXiv:1506.08716 [math.CO], 2015.
P. A. MacMahon, The divisors of numbers, Proc. London Math. Soc., (2) 19 (1920), 305-340; Coll. Papers II, pp. 267-302.
R. Mantaci and F. Rakotondrajao, A permutation representation that knows what "Eulerian" means, Discrete Mathematics and Theoretical Computer Science, 4 101-108, (2001) [another version]
O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. [Annotated scanned copy]
O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19.
Nagatomo Nakamura, Pseudo-Normal Random Number Generation via the Eulerian Numbers, Josai Mathematical Monographs, vol 8, p 85-95, 2015.
David Neal, The series Sum k=1 to oo n^m*x^n and a Pascal-Like Triangle, The College Mathematics Journal, Vol. 25, No. 2 (Mar., 1994), pp. 99-101 (3 pages).
S. Parker, The Combinatorics of Functional Composition and Inversion, Dissertation, Brandeis Univ. (1993).
Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016-2017.
C. de Jesús Pita Ruiz Velasco, Convolution and Sulanke Numbers, JIS 13 (2010) 10.1.8.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
A. Postnikov, V. Reiner, and L. Williams, Faces of generalized permutohedra, arXiv:0609184 [math.CO], 2007.
A. Randrianarivony and J. Zeng, Une famille de polynomes qui interpole plusieurs suites..., Adv. Appl. Math. 17 (1996), 1-26.
J. Riordan, Review of Frankel (1950) [Annotated scanned copy]
J. Riordan, Triangular permutation numbers, Proc. Amer. Math. Soc. 2 (1951) 429-432, r(x,t).
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16. [Annotated scanned copy]
G. Rzadkowski, Two formulas for Successive Derivatives and Their Applications, JIS 12 (2009) 09.8.2.
G. Rzadkowski, An Analytic Approach to Special Numbers and Polynomials, J. Int. Seq. 18 (2015) 15.8.8.
Grzegorz Rzadkowski and M. Urlinska, A Generalization of the Eulerian Numbers, arXiv preprint arXiv:1612.06635 [math.CO], 2016-2017.
J. Sack and H. Ulfarsson, Refined inversion statistics on permutations, arXiv:1106.1995 [math.CO], 2011.
M. Sheppeard, Constructive motives and scattering 2013 (p. 41).
D. Singh, The numbers L(m,n) and their relations with prepared Bernoulli and Eulerian numbers, Math. Student, 20 (1952), 66-70. [Annotated scanned copy]
M. Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq. 14 (2011) # 11.9.7.
R. Sprugnoli, Alternating Weighted Sums of Inverses of Binomial Coefficients, J. Integer Sequences, 15 (2012), #12.6.3.
Yidong Sun and Liting Zhai, Some properties of a class of refined Eulerian polynomials, arXiv:1810.07956 [math.CO], 2018.
S. Tanimoto, A study of Eulerian numbers by means of an operator on permutations, Europ. J. Combin., 24 (2003), 33-43.
Eric Weisstein's World of Mathematics, Eulerian Number and Euler's Number Triangle
Susanne Wienand, plots of exceedances for permutations of [4]
L. K. Williams, Enumeration of totally positive Grassmann cells, arXiv:math/0307271 [math.CO], 2003-2004.
Anthony James Wood, Nonequilibrium steady states from a random-walk perspective, Ph. D. Thesis, The University of Edinburgh (Scotland, UK 2019).
Anthony J. Wood, Richard A. Blythe, and Martin R. Evans, Combinatorial mappings of exclusion processes, arXiv:1908.00942 [cond-mat.stat-mech], 2019.
Tingyao Xiong, Jonathan I. Hall, and Hung-Ping Tsao, Combinatorial Interpretation of General Eulerian Numbers, Journal of Discrete Mathematics, (2014), Article ID 870596, 6 pages.
D. Yeliussizov, Permutation Statistics on Multisets, Ph.D. Dissertation, Computer Science, Kazakh-British Technical University, 2012.
Yifan Zhang and George Grossman, A Combinatorial Proof for the Generating Function of Powers of a Second-Order Recurrence Sequence, J. Int. Seq. 21 (2018), #18.3.3.
Index entries for sequences related to rooted trees
Index entries for "core" sequences

Columns k=2..8 are A000295, A000460, A000498, A000505, A000514, A001243, A001244.

Cf. A019538, A028246, A048993, A048994, A049019, A086885, A090582, A129185, A131758, A139605, A173018.

Flat(List([1..10],n->List([1..n],k->Sum([0..k],j->(-1)^j*(k-j)^n*Binomial(n+1,j))))); # Muniru A Asiru, Jun 29 2018

import Data.List (genericLength)
a008292 n k = a008292_tabl !! (n-1) !! (k-1)
a008292_row n = a008292_tabl !! (n-1)
a008292_tabl = iterate f [1] where
   f xs = zipWith (+)
     (zipWith (*) ([0] ++ xs) (reverse ks)) (zipWith (*) (xs ++ [0]) ks)
     where ks = [1 .. 1 + genericLength xs]
-- Reinhard Zumkeller, May 07 2013

Eulerian:= func< n,k | (&+[(-1)^j*Binomial(n+1,j)*(k-j+1)^n: j in [0..k+1]]) >; [[Eulerian(n,k): k in [0..n-1]]: n in [1..10]]; // G. C. Greubel, Apr 15 2019

A008292 := proc(n,k) option remember; if k < 1 or k > n then 0; elif k = 1 or k = n then 1; else k*procname(n-1,k)+(n-k+1)*procname(n-1,k-1) ; end if; end proc:

t[n_, k_] = Sum[(-1)^j*(k-j)^n*Binomial[n+1, j], {j, 0, k}];
Flatten[Table[t[n, k], {n, 1, 10}, {k, 1, n}]] (* Jean-François Alcover, May 31 2011, after Michael Somos *)
Flatten[Table[CoefficientList[(1-x)^(k+1)*PolyLog[-k, x]/x, x], {k, 1, 10}]] (* Vaclav Kotesovec, Aug 27 2015 *)
Table[Tally[
   Count[#, x_ /; x > 0] & /@ (Differences /@
      Permutations[Range[n]])][[;; , 2]], {n, 10}] (* Li Han, Oct 11 2020 *)

{T(n, k) = if( k<1 || k>n, 0, if( n==1, 1, k * T(n-1, k) + (n-k+1) * T(n-1, k-1)))}; /* Michael Somos, Jul 19 1999 */

{T(n, k) = sum( j=0, k, (-1)^j * (k-j)^n * binomial( n+1, j))}; /* Michael Somos, Jul 19 1999 */

{A(n,c)=c^(n+c-1)+sum(i=1,c-1,(-1)^i/i!*(c-i)^(n+c-1)*prod(j=1,i,n+c+1-j))}

from sympy import binomial
def T(n, k): return sum([(-1)**j*(k - j)**n*binomial(n + 1, j) for j in range(k + 1)])
for n in range(1, 11): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Nov 08 2017

T <- function(n, k) {
  S <- numeric()
  for (j in 0:k) S <- c(S, (-1)^j*(k-j)^n*choose(n+1, j))
  return(sum(S))
}
for (n in 1:10){
  for (k in 1:n) print(T(n,k))
} # Indranil Ghosh, Nov 08 2017

[[sum((-1)^j*binomial(n+1, j)*(k-j)^n for j in (0..k)) for k in (1..n)] for n in (1..12)] # G. C. Greubel, Feb 23 2019

T(n, k) = k * T(n-1, k) + (n-k+1) * T(n-1, k-1), T(1, 1) = 1.
T(n, k) = Sum_{j=0..k} (-1)^j * (k-j)^n * binomial(n+1, j).
Row sums = n! = A000142(n) unless n=0. - Michael Somos, Mar 17 2011
E.g.f. A(x, q) = Sum_{n>0} (Sum_{k=1..n} T(n, k) * q^k) * x^n / n! = q * ( e^(q*x) - e^x ) / ( q*e^x - e^(q*x) ) satisfies dA / dx = (A + 1) * (A + q). - Michael Somos, Mar 17 2011
For a column listing, n-th term: T(c, n) = c^(n+c-1) + Sum_{i=1..c-1} (-1)^i/i!*(c-i)^(n+c-1)*Product_{j=1..i} (n+c+1-j). - Randall L Rathbun, Jan 23 2002
From John Robertson (jpr2718(AT)aol.com), Sep 02 2002: (Start)
Four characterizations of Eulerian numbers T(i, n):
1. T(0, n)=1 for n>=1, T(i, 1)=0 for i>=1, T(i, n) = (n-i)T(i-1, n-1) + (i+1)T(i, n-1).
2. T(i, n) = Sum_{j=0..i} (-1)^j*binomial(n+1,j)*(i-j+1)^n for n>=1, i>=0.
3. Let C_n be the unit cube in R^n with vertices (e_1, e_2, ..., e_n) where each e_i is 0 or 1 and all 2^n combinations are used. Then T(i, n)/n! is the volume of C_n between the hyperplanes x_1 + x_2 + ... + x_n = i and x_1 + x_2 + ... + x_n = i+1. Hence T(i, n)/n! is the probability that i <= X_1 + X_2 + ... + X_n < i+1 where the X_j are independent uniform [0, 1] distributions. - See Ehrenborg & Readdy reference.
4. Let f(i, n) = T(i, n)/n!. The f(i, n) are the unique coefficients so that (1/(r-1)^(n+1)) Sum_{i=0..n-1} f(i, n) r^{i+1} = Sum_{j>=0} (j^n)/(r^j) whenever n>=1 and abs(r)>1. (End)
O.g.f. for n-th row: (1-x)^(n+1)*polylog(-n, x)/x. - Vladeta Jovovic, Sep 02 2002
Triangle T(n, k), n>0 and k>0, read by rows; given by [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] DELTA [1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] (positive integers interspersed with 0's) where DELTA is Deléham's operator defined in A084938.
Sum_{k=1..n} T(n, k)*2^k = A000629(n). - Philippe Deléham, Jun 05 2004
From Tom Copeland, Oct 10 2007: (Start)
Bell_n(x) = Sum_{j=0..n} S2(n,j) * x^j = Sum_{j=0..n} E(n,j) * Lag(n,-x, j-n) = Sum_{j=0..n} (E(n,j)/n!) * (n!*Lag(n,-x, j-n)) = Sum_{j=0..n} E(n,j) * binomial(Bell.(x)+j, n) umbrally where Bell_n(x) are the Bell / Touchard / exponential polynomials; S2(n,j), the Stirling numbers of the second kind; E(n,j), the Eulerian numbers; and Lag(n,x,m), the associated Laguerre polynomials of order m.
For x = 0, the equation gives Sum_{j=0..n} E(n,j) * binomial(j,n) = 1 for n=0 and 0 for all other n. By substituting the umbral compositional inverse of the Bell polynomials, the lower factorial n!*binomial(y,n), for x in the equation, the Worpitzky identity is obtained; y^n = Sum_{j=0..n} E(n,j) * binomial(y+j,n).
Note that E(n,j)/n! = E(n,j)/(Sum_{k=0..n} E(n,k)). Also (n!*Lag(n, -1, j-n)) is A086885 with a simple combinatorial interpretation in terms of seating arrangements, giving a combinatorial interpretation to the equation for x=1; n!*Bell_n(1) = n!*Sum_{j=0..n} S2(n,j) = Sum_{j=0..n} E(n,j) * (n!*Lag(n, -1, j-n)).
(Appended Sep 16 2020) For connections to the Bernoulli numbers, extensions, proofs, and a clear presentation of the number arrays involved in the identities above, see my post Reciprocity and Umbral Witchcraft. (End)
From the relations between the h- and f-polynomials of permutohedra and reciprocals of e.g.f.s described in A049019: (t-1)((t-1)d/dx)^n 1/(t-exp(x)) evaluated at x=0 gives the n-th Eulerian row polynomial in t and the n-th row polynomial in (t-1) of A019538 and A090582. From the Comtet and Copeland references in A139605: ((t+exp(x)-1)d/dx)^(n+1) x gives pairs of the Eulerian polynomials in t as the coefficients of x^0 and x^1 in its Taylor series expansion in x. - Tom Copeland, Oct 05 2008
G.f: 1/(1-x/(1-x*y/1-2*x/(1-2*x*y/(1-3*x/(1-3*x*y/(1-... (continued fraction). - Paul Barry, Mar 24 2010
If n is odd prime, then the following consecutive 2*n+1 terms are 1 modulo n: a((n-1)*(n-2)/2+i), i=0..2*n. This chain of terms is maximal in the sense that neither the previous term nor the following one are 1 modulo n. - _Vladimir Shevelev, Jul 01 2011
From Peter Bala, Sep 29 2011: (Start)
For k = 0,1,2,... put G(k,x,t) := x -(1+2^k*t)*x^2/2 +(1+2^k*t+3^k*t^2)*x^3/3-(1+2^k*t+3^k*t^2+4^k*t^3)*x^4/4+.... Then the series reversion of G(k,x,t) with respect to x gives an e.g.f. for the present table when k = 0 and for A008517 when k = 1.
The e.g.f. B(x,t) := compositional inverse with respect to x of G(0,x,t) = (exp(x)-exp(x*t))/(exp(x*t)-t*exp(x)) = x + (1+t)*x^2/2! + (1+4*t+t^2)*x^3/3! + ... satisfies the autonomous differential equation dB/dx = (1+B)*(1+t*B) = 1 + (1+t)*B + t*B^2.
Applying [Bergeron et al., Theorem 1] gives a combinatorial interpretation for the Eulerian polynomials: A(n,t) counts plane increasing trees on n vertices where each vertex has outdegree <= 2, the vertices of outdegree 1 come in 1+t colors and the vertices of outdegree 2 come in t colors. An example is given below. Cf. A008517. Applying [Dominici, Theorem 4.1] gives the following method for calculating the Eulerian polynomials: Let f(x,t) = (1+x)*(1+t*x) and let D be the operator f(x,t)*d/dx. Then A(n+1,t) = D^n(f(x,t)) evaluated at x = 0.
(End)
With e.g.f. A(x,t) = G[x,(t-1)]-1 in Copeland's 2008 comment, the compositional inverse is Ainv(x,t) = log(t-(t-1)/(1+x))/(t-1). - Tom Copeland, Oct 11 2011
T(2*n+1,n+1) = (2*n+2)*T(2*n,n). (E.g., 66 = 6*11, 2416 = 8*302, ...) - Gary Detlefs, Nov 11 2011
E.g.f.: (1-y) / (1 - y*exp( (1-y)*x )). - Geoffrey Critzer, Nov 10 2012
From Peter Bala, Mar 12 2013: (Start)
Let {A(n,x)} n>=1 denote the sequence of Eulerian polynomials beginning [1, 1 + x, 1 + 4*x + x^2, ...]. Given two complex numbers a and b, the polynomial sequence defined by R(n,x) := (x+b)^n*A(n+1,(x+a)/(x+b)), n >= 0, satisfies the recurrence equation R(n+1,x) = d/dx((x+a)*(x+b)*R(n,x)). These polynomials give the row generating polynomials for several triangles in the database including A019538 (a = 0, b = 1), A156992 (a = 1, b = 1), A185421 (a = (1+i)/2, b = (1-i)/2), A185423 (a = exp(i*Pi/3), b = exp(-i*Pi/3)) and A185896 (a = i, b = -i).
(End)
E.g.f.: 1 + x/(T(0) - x*y), where T(k) = 1 + x*(y-1)/(1 + (k+1)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 07 2013
From Tom Copeland, Sep 18 2014: (Start)
A) Bivariate e.g.f. A(x,a,b)= (e^(ax)-e^(bx))/(a*e^(bx)-b*e^(ax)) = x + (a+b)*x^2/2! + (a^2+4ab+b^2)*x^3/3! + (a^3+11a^2b+11ab^2+b^3)x^4/4! + ...
B) B(x,a,b)= log((1+ax)/(1+bx))/(a-b) = x - (a+b)x^2/2 + (a^2+ab+b^2)x^3/3 - (a^3+a^2b+ab^2+b^3)x^4/4 + ... = log(1+u.*x), with (u.)^n = u_n = h_(n-1)(a,b) a complete homogeneous polynomial, is the compositional inverse of A(x,a,b) in x (see Drake, p. 56).
C) A(x) satisfies dA/dx = (1+a*A)(1+b*A) and can be written in terms of a Weierstrass elliptic function (see Buchstaber & Bunkova).
D) The bivariate Eulerian row polynomials are generated by the iterated derivative ((1+ax)(1+bx)d/dx)^n x evaluated at x=0 (see A145271).
E) A(x,a,b)= -(e^(-ax)-e^(-bx))/(a*e^(-ax)-b*e^(-bx)), A(x,-1,-1) = x/(1+x), and B(x,-1,-1) = x/(1-x).
F) FGL(x,y) = A(B(x,a,b) + B(y,a,b),a,b) = (x+y+(a+b)xy)/(1-ab*xy) is called the hyperbolic formal group law and related to a generalized cohomology theory by Lenart and Zainoulline. (End)
For x > 1, the n-th Eulerian polynomial A(n,x) = (x - 1)^n * log(x) * Integral_{u>=0} (ceiling(u))^n * x^(-u) du. - Peter Bala, Feb 06 2015
Sum_{j>=0} j^n/e^j, for n>=0, equals Sum_{k=1..n} T(n,k)e^k/(e-1)^(n+1), a rational function in the variable "e" which evaluates, approximately, to n! when e = A001113 = 2.71828... - Richard R. Forberg, Feb 15 2015
For a fixed k, T(n,k) ~ k^n, proved by induction. - Ran Pan, Oct 12 2015
From A145271, multiply the n-th diagonal (with n=0 the main diagonal) of the lower triangular Pascal matrix by g_n = (d/dx)^n (1+a*x)*(1+b*x) evaluated at x= 0, i.e., g_0 = 1, g_1 = (a+b), g_2 = 2ab, and g_n = 0 otherwise, to obtain the tridiagonal matrix VP with VP(n,k) = binomial(n,k) g_(n-k). Then the m-th bivariate row polynomial of this entry is P(m,a,b) = (1, 0, 0, 0, ...) [VP * S]^(m-1) (1, a+b, 2ab, 0, ...)^T, where S is the shift matrix A129185, representing differentiation in the divided powers basis x^n/n!. Also, P(m,a,b) = (1, 0, 0, 0, ...) [VP * S]^m (0, 1, 0, ...)^T. - Tom Copeland, Aug 02 2016
Cumulatively summing a row generates the n starting terms of the n-th differences of the n-th powers. Applying the finite difference method to x^n, these terms correspond to those before constant n! in the lowest difference row. E.g., T(4,k) is summed as 0+1=1, 1+11=12, 12+11=23, 23+1=4!. See A101101, A101104, A101100, A179457. - Andy Nicol, May 25 2024

Thanks to Michael Somos for additional comments.

Further comments from Christian G. Bower, May 12 2000

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

N. J. A. Sloane

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

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

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

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"
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See pp. 9, 17, 18.
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.
Jean-Luc Baril and J. M. Pallo, The pruning-grafting lattice of binary trees, Theoretical Computer Science, 409, 2008, 382-393.
Jean-Luc Baril and José L. Ramírez, Some distributions in increasing and flattened permutations, arXiv:2410.15434 [math.CO], 2024. See p. 7.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, Maximilien Gadouleau, James D. Mitchell, and Yann 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.
Shelby Cox, Pratik Misra, and Pardis Semnani, Homaloidal Polynomials and Gaussian Models of Maximum Likelihood Degree One, arXiv:2402.06090 [math.AG], 2024.
Benjamin Hellouin de Menibus and Yvan Le Borgne, Asymptotic behaviour of the one-dimensional "rock-paper-scissors" 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/s10801-016-0673-y.
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.
E. T. Frankel, A calculus of figurate numbers and finite differences, American Mathematical Monthly, 57 (1950), 14-25. [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é Paris-Saclay, 2018.
R. K. Guy, Letter to N. J. A. Sloane.
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See pp. 24-25.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 388.
Wayne A. Johnson, An Euler operator approach to Ehrhart series, arXiv:2303.16991 [math.CO], 2023.
Lucas Kang, Investigation of Rule 73 as Case Study of Class 4 Long-Distance Cellular Automata, arXiv preprint arXiv:1310.3311 [nlin.CG], 2013.
Oliver Kullmann and Xishun 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 Pseudo-Involutions in the Riordan Group, Dissertation, Morgan State University, 2017.
Peter Charles Mendenhall and Hal M. Switkay, Consecutively Halved Positional Voting: A Special Case of Geometric Voting, Social Sciences vol. 12 no. 2 (2023), 47-59.
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, 71--75. MR0427129(55 #165).
Agustín Moreno Cañadas, Hernán Giraldo, and Gabriel Bravo Rios, On the Number of Sections in the Auslander-Reiten Quiver of Algebras of Dynkin Type, Far East Journal of Mathematical Sciences (FJMS), Vol. 101, No. 8 (2017), pp. 1631-1654.
Nagatomo Nakamura, Pseudo-Normal Random Number Generation via the Eulerian Numbers, Josai Mathematical Monographs, vol 8, p 85-95, 2015.
Emily 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, 514-517.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
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), 8-16.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16. [Annotated scanned copy]
Markus Sigg, Collatz iteration and Euler numbers?
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 Yli-Jyra, On Dependency Analysis via Contractions and Weighted FSTs, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133-158. - _N. J. A. Sloane_, Dec 25 2012
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

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.

a000295 n = 2^n - n - 1  -- Reinhard Zumkeller, Nov 25 2013

[2^n-n-1: n in [0..40]]; // Vincenzo Librandi, Jul 29 2015

[EulerianNumber(n, 1): n in [0..40]]; // G. C. Greubel, Oct 02 2024

[ 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

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 *)

a(n)=2^n-n-1 \\ Charles R Greathouse IV, Jun 10 2011

[2^n -(n+1) for n in range(41)] # G. C. Greubel, Oct 02 2024

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

A000255 a(n) = na(n-1) + (n-1)a(n-2), a(0) = 1, a(1) = 1.

Original entry on oeis.org

1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, 34361893981, 513137616783, 8178130767479, 138547156531409, 2486151753313617, 47106033220679059, 939765362752547227, 19690321886243846661, 432292066866171724421

Offset: 0

N. J. A. Sloane

a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]. - Len Smiley, Oct 13 2001
Also, for n > 0, determinant of the tridiagonal n X n matrix M such that M(i,i)=i and for i=1..n-1, M(i,i+1)=-1, M(i+1,i)=i. - Mario Catalani (mario.catalani(AT)unito.it), Feb 04 2003
Also, for n > 0, maximal permanent of a nonsingular n X n (0,1)-matrix, which is achieved by the matrix with just n-1 0's, all on main diagonal. [For proof, see next entry.] - W. Edwin Clark, Oct 28 2003
Proof from Richard Brualdi and W. Edwin Clark, Nov 15 2003: Let n >= 4. Take an n X n (0,1)-matrix A which is nonsingular. It has t >= n-1, 0's, otherwise there will be two rows of all 1's. Let B be the matrix obtained from A by replacing t-(n-1) of A's 0's with 1's. Let D be the matrix with all 1's except for 0's in the first n-1 positions on the diagonal. This matrix is easily seen to be non-singular. Now we have per(A) < = per(B) < = per (D), where the first inequality follows since replacing 0's by 1's cannot decrease the permanent and the second from Corollary 4.4 in the Brualdi et al. reference, which shows that per(D) is the maximum permanent of ANY n X n matrix with n -1 0's. Corollary 4.4 requires n >= 4. a(n) for n < 4 can be computed directly.
With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003
Number of fixed-point-free permutations of n+2 that begin with a 2; e.g., for 1234, we have 2143, 2341, 2413, so a(2)=3. Also number of permutations of 2..n+2 that have no agreements with 1..n+1. E.g., for 123 against permutations of 234, we have 234, 342 and 432. Compare A047920. - Jon Perry, Jan 23 2004. [This can be proved by the standard argument establishing that d(n+2) = (n+1)(d(n+1)+d(n)) for derangements A000166 (n+1 choices of where 1 goes, then either 1 is in a transposition, or in a cycle of length at least 3, etc.). - D. G. Rogers, Aug 28 2006]
Stirling transform of A006252(n+1)=[1,1,2,4,14,38,...] is a(n)=[1,3,11,53,309,...]. - Michael Somos, Mar 04 2004
a(n+1) is the sequence of numerators of the self-convergents to 1/(e-2); see A096654. - Clark Kimberling, Jul 01 2004
Euler's interpretation was "fixedpoint-free permutations beginning with 2" and he listed the terms up to 148329 (although he was blind at the time). - Don Knuth, Jan 25 2007
Equals lim_{k->infinity} A153869^k. - Gary W. Adamson, Jan 03 2009
Hankel transform is A059332. - Paul Barry, Apr 22 2009
This sequence appears in the analysis of Euler's divergent series 1 - 1! + 2! - 3! + 4! ... by Lacroix, see Hardy. For information about this and related divergent series see A163940. - Johannes W. Meijer, Oct 16 2009
a(n), n >= 1, enumerates also the ways to distribute n beads, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and one open cord allowed to have any number of beads. Each beadless necklace as well as the beadless cord contributes a factor 1 in the counting, e.g., a(0):=1*1=1. There are k! possibilities for the cord with k>=0 beads, which means that the two ends of the cord should be considered as fixed, in short: a fixed cord. This produces for a(n) the exponential (aka binomial) convolution of the sequences {n!=A000142(n)} and the subfactorials {A000166(n)}.
See the formula below. Alternatively, the e.g.f. for this problem is seen to be (exp(-x)/(1-x))*(1/(1-x)), namely the product of the e.g.f.s for the subfactorials (from the unordered necklace problem, without necklaces with exactly one bead) and the factorials (from the fixed cord problem). Therefore the recurrence with inputs holds also. a(0):=1. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 02 2010
a(n) = (n-1)a(n-1) + (n-2)a(n-2) gives the same sequence offset by a 1. - Jon Perry, Sep 20 2012
Also, number of reduced 2 X (n+2) Latin rectangles. - A.H.M. Smeets, Nov 03 2013
Second column of Euler's difference table (second diagonal in example of A068106). - Enrique Navarrete, Dec 13 2016
If we partition the permutations of [n+2] in A000166 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n) (the class starting with the digit 1 is empty since no derangement starts with 1). Hence, A000166(n+2)=(n+1)*a(n), so a(n) is the size of each nonempty class of permutations of [n+2] in A000166. For example, for n=3 we have 44=4*11 (see link). - Enrique Navarrete, Jan 11 2017
For n >= 1, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+2), 1 <= j <= n.  For example, for n=2, the 3 circular permutations in S4 that avoid substrings {13,24} are (1234),(1423),(1432). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 2017
The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) holding for all n and k, which in turn is easily proved by induction making use of the given recurrences. - Peter Bala, Nov 21 2017
Number of permutations of [n] where the k-th fixed points are k-colored and all other points are unicolored. - Alois P. Heinz, Apr 28 2025

			a(3)=11: 1 3 2 4; 1 4 3 2; 2 1 4 3; 2 4 1 3; 3 2 1 4; 3 2 4 1; 4 1 3 2; 4 2 1 3; 4 3 2 1; 2 4 3 1; 3 1 4 2. The last two correspond to (n-1)*a(n-2) since they contain a [j,n+1,j+1].
Cord-necklaces problem. For n=4 one considers the following weak two part compositions of 4: (4,0), (2,2), (1,3), and (0,4), where (3,1) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively 4!*1, (binomial(4,2)*2)*sf(2), (binomial(4,1)*1)*sf(3), and 1*sf(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there). This adds up as 24 + 6*2 + 4*2 + 9 = 53 = a(4). - _Wolfdieter Lang_, Jun 02 2010
G.f. = 1 + x + 3*x^2 + 11*x^3 + 53*x^4 + 309*x^5 + 2119*x^6 + 16687*x^7 + ...

Richard A. Brualdi and Herbert J. Ryser, Combinatorial Matrix Theory, Camb. Univ. Press, 1991, Section 7.2, p. 202.
Charalambos A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 179, Table 5.4 and p. 177 (5.1).
CRC Handbook of Combinatorial Designs, 1996, p. 104.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, pp. 263-264. See Table 7.5.1, row 0; also Table 7.6.1, row 0.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.
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).
N. Ya. Vilenkin, Combinatorics, pp. 54 - 56, Academic Press, 1971. Caravan in the Desert, E_n = a(n-1), n >= 1.

T. D. Noe, Table of n, a(n) for n=0..100
M. H. Albert, M. D. Atkinson, and Robert Brignall, Permutation Classes of Polynomial Growth, arXiv:math/0603315 [math.CO], 2006-2007; Annals of Combinatorics 11 (2007) 249-264.
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, Vol. 19 (2012), Article P7. - From _N. J. A. Sloane_, Feb 06 2013
Barry Balof and Helen Jenne, Tilings, Continued Fractions, Derangements, Scramblings, and e, Journal of Integer Sequences, Vol. 17 (2014), Article 14.2.7.
Robert Brignall, Vít Jelínek, Jan Kynčl, and David Marchant, Zeros of the Möbius function of permutations, arXiv:1810.05449 [math.CO], 2018.
Richard A. Brualdi, John L. Goldwasser, and T. S. Michael, Maximum permanents of matrices of zeros and ones, J. Combin. Theory Ser. A 47 (1988), 207-245.
Giulio Cerbai and Luca Ferrari, Permutation patterns in genome rearrangement problems, arXiv:1808.02653 [math.CO], 2018. See p. 126.
Shane Chern, Lin Jiu, and Italo Simonelli, A central limit theorem for a card shuffling problem, arXiv:2309.08841 [math.PR], 2023.
Leonhard Euler, Recherches sur une nouvelle espèce des quarrés magiques, Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, 9 (1782), 85-239, on page 235 in section 152. This is paper E530 in Enestrom's index of Euler's works. The sequence appears on page 389 of Euler's Opera Omnia, series I, volume 7. [From D. E. Knuth]
Uriel Feige, Tighter bounds for online bipartite matching, 2018.
Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson Scheme, and Generalized Derangements, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages; doi:10.1155/2011/539030.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 373.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 36.
G. H. Hardy, Divergent Series, Oxford University Press, 1949. p. 29.
Florian Herzig, Problem 2330, Crux Mathematicorum, Vol. 24, No. 3 (1998), p. 176; Solution to Problem 2330, by Con Amore Problem Group, ibid., Vol. 25, No. 3 (1999), pp. 183-185.
F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.
Brian Hopkins, Euler's Enumerations, Enumerative Combinatorics and Applications, Vol. 1, No. 1 (2021), Article #S1H1.
Helen K. Jenne, Proofs you can count on, Honors Thesis, Math. Dept., Whitman College, 2013.
G. Kreweras, The number of more or less "regular" permutations, Fib. Quart., Vol. 18, No. 3 (1980), pp. 226-229.
Ajay Kumar and Chanchal Kumar, Monomial ideals induced by permutations avoiding patterns, 2018.
Toufik Mansour and Mark Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., Vol. 339, No. 4 (2016), pp. 1368-1376.
A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, Series A, Vol. 99, No. 2 (2002), pp. 345-357.
Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.
Enrique Navarrete, Forbidden Substrings in Circular K-Successions, arXiv:1702.02637 [math.CO], 2017.
Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., Vol. 19, No. 1 (1968), pp. 8-16.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., Vol. 19, No. 1 (1968), pp. 8-16. [Annotated scanned copy]
Max Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz., Vol. 52, No. 382 (1968), pp. 381-382.
Max Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz., Vol. 52, No. 382 (1968), pp. 381-382. [Annotated scanned copy]
Isaac Sofair, Derangement revisited, Math. Gazette, Vol. 97, No. 540 (2013), pp. 435-440.
Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Lin. Algebra and its Applic., Vol. 373 (2003), pp. 197-210.
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 5.

Row sums of triangle in A046740. A diagonal of triangle in A068106.
Cf. A000153, A000166, A000261, A001909, A001910, A055790.
Cf. A090010, A090012, A090013, A090014, A090015, A090016.
A052655 gives occurrence count for non-singular (0, 1)-matrices with maximal permanent, A089475 number of different values of permanent, A089480 occurrence counts for permanents all non-singular (0, 1)-matrices, A087982, A087983.
A diagonal in triangle A010027.
Cf. A153869, A159610, A002469.
a(n) = A086764(n+1,1).

a000255 n = a000255_list !! n
a000255_list = 1 : 1 : zipWith (+) zs (tail zs) where
   zs = zipWith (*) [1..] a000255_list
-- Reinhard Zumkeller, Dec 05 2011

I:=[1, 3]; [1] cat  [n le 2 select I[n] else n*Self(n-1)+(n-1)*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Aug 09 2018

a := n -> hypergeom([2,-n], [], 1)*(-1)^n:
seq(simplify(a(n)), n=0..19); # Peter Luschny, Sep 20 2014
seq(simplify(KummerU(-n, -n-1, -1)), n=0..21); # Peter Luschny, May 10 2022

c = CoefficientList[Series[Exp[ -z]/(1 - z)^2, {z, 0, 30}], z]; For[n = 0, n < 31, n++; Print[c[[n]]*(n - 1)! ]]
Table[Subfactorial[n] + Subfactorial[n + 1], {n, 0, 20}] (* Zerinvary Lajos, Jul 09 2009 *)
RecurrenceTable[{a[n]==n a[n-1]+(n-1)a[n-2],a[0]==1,a[1]==1},a[n], {n,20}] (* Harvey P. Dale, May 10 2011 *)
a[ n_] := If[ n < 0, 0, Round[ n! (n + 2) / E]] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ -x] / (1 - x)^2, {x, 0, n}]] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, (-1)^n HypergeometricPFQ[ {- n, 2}, {}, 1]] (* Michael Somos, Jun 01 2013 *)
sa[k_Integer]/;k>=2 := SparseArray[{{i_, i_} -> i, Band[{2, 1}] -> -1, {i_, j_} /; (i == j - 1) :> i}, {k, k}]; {1, 1}~Join~Array[Det[sa[#]] &, 20, 2] (* Shenghui Yang, Oct 15 2024 *)

{a(n) = if( n<0, 0, contfracpnqn( matrix( 2, n, i, j, j - (i==1)))[1, 1])};

{a(n) = if( n<0, 0, n! * polcoeff( exp( -x + x * O(x^n)) / (1 - x)^2, n))};

from sage.combinat.sloane_functions import ExtremesOfPermanentsSequence2
e = ExtremesOfPermanentsSequence2()
it = e.gen(1,1,1)
[next(it) for i in range(20)]
# Zerinvary Lajos, May 15 2009

E.g.f.: exp(-x)/(1-x)^2.
a(n) = Sum_{k=0..n} (-1)^k * (n-k+1) * n!/k!. - Len Smiley
Inverse binomial transform of (n+1)!. - Robert A. Stump (bee_ess107(AT)yahoo.com), Dec 09 2001
a(n-2) = !n/(n - 1) where !n is the subfactorial of n, A000166(n). - Lekraj Beedassy, Jun 18 2002
a(n) = floor((1/e)*n!*(n+2)+1/2). - Benoit Cloitre, Jan 15 2004
Apparently lim_{n->infinity} log(n) - log(a(n))/n = 1. - Gerald McGarvey, Jun 12 2004
a(n) = (n*(n+2)*a(n-1) + (-1)^n)/(n+1) for n >= 1, a(0)=1. See the Charalambides reference.
a(n) = GAMMA(n+3,-1)*exp(-1)/(n+1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009
a(n) = A000166(n) + A000166(n+1).
A002469(n) = (n-2)*a(n-1) + A000166(n). - Gary W. Adamson, Apr 17 2009
If we take b(n) = (-1)^(n+1)*a(n) for n > 0, then for n > 1 the arithmetic mean of the first n terms is -b(n-1). - Franklin T. Adams-Watters, May 20 2010
a(n) = hypergeometric([2,-n],[],1)*(-1)^n = KummerU(2,3+n,-1)*(-1)^n. See the Abramowitz-Stegun handbook (for the reference see e.g. A103921) p. 504, 13.1.10, and for the recurrence p. 507, 13.4.16. - Wolfdieter Lang, May 20 2010
a(n) = n!*(1 + Sum_{k=0..n-2} sf(n-k)/(n-k)!) with the subfactorials sf(n):= A000166(n) (this follows from the exponential convolution). - Wolfdieter Lang, Jun 02 2010
a(n) = 1/(n+1)*floor(((n+1)!+1)/e). - Gary Detlefs, Jul 11 2010
a(n) = (Subfactorial(n+2))/(n+1). - Alexander R. Povolotsky, Jan 26 2011
G.f.: 1/(1-x-2x^2/(1-3x-6x^2/(1-5x-12x^2/(1-7x-20x^2/(1-.../(1-(2n+1)x-(n+1)(n+2)x^2/(1-... (continued fraction). - Paul Barry, Apr 11 2011
G.f.: hypergeom([1,2],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Sep 24 2012 - Feb 05 2014: (Start)
Continued fractions:
E.g.f. 1/E(0) where E(k) = 1 - 2*x/(1 + x/(2 - x - 2/(1 + x*(k+1)/E(k+1)))).
G.f.: S(x)/x - 1/x = Q(0)/x - 1/x where S(x) = Sum_{k>=0} k!*(x/(1+x))^k, Q(k) = 1 + (2*k + 1)*x/(1 + x - 2*x*(1+x)*(k+1)/(2*x*(k+1) + (1+x)/Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 + x - x*(k+2)/(1 - x*(k+1)/Q(k+1)).
G.f.: 1/x/Q(0) where Q(k) = 1/x - (2*k+1) - (k+2)*(k+1)/Q(k+1).
G.f.: (1+x)/(x*Q(0)) - 1/x where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: 2/x/G(0) - 1/x where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+1) - 1 + x*(2*k+2)/ G(k+1))).
G.f.: ((Sum_{k>=0} k!*(x/(1+x))^k) - 1)/x = Q(0)/(2*x) - 1/x where Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1+x)/Q(k+1))).
G.f.: W(0) where W(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+2)/(x*(k+1) - 1/W(k+1)))).
G.f.: G(0)/(1-x) where G(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - (1-x*(1+2*k))*(1-x*(3+2*k))/G(k+1)). (End)
From Peter Bala, Sep 20 2013: (Start)
The sequence b(n) := n!*(n + 2) satisfies the defining recurrence for a(n) but with the starting values b(0) = 2 and b(1) = 3. This leads to the finite continued fraction expansion a(n) = n!*(n+2)*( 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/n)))) ), valid for n >= 2.
Also a(n) = n!*(n+2)*( Sum_{k = 0..n} (-1)^k/(k+2)! ). Letting n -> infinity gives the infinite continued fraction expansion 1/e = 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/(n + ...)))) ) due to Euler. (End)
0 = a(n)*(+a(n+1) + 2*a(n+2) - a(n+3)) + a(n+1)*(+2*a(n+2) - a(n+3)) + a(n+2)*(+a(n+2)) if n >= 0. - Michael Somos, May 06 2014
a(n-3) = (n-2)*A000757(n-2) + (2*n-5)*A000757(n-3) + (n-3)*A000757(n-4), n >= 3. - Luis Manuel Rivera Martínez, Mar 14 2015
a(n) = A000240(n) + A000240(n+1), n >= 1. Let D(n) = A000240(n) be the permutations of [n] having no substring in {12,23,...,(n-1)n,n1}. Let d(n) = a(n-1) be the permutations of [n] having no substring in {12,23,...,(n-1)n}. Let d_n1 = A000240(n-1) be the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. Then the link "Forbidden Patterns" shows the bijection d_n1 ~ D(n-1) and since dn = d_n1 U D(n), we get dn = D(n-1) U D(n). Taking cardinalities we get the result for n-1, i.e., a(n-1) = A000240(n-1) + A000240(n). For example, for n=4 in this last equation, we get a(4) = 11 = 3+8. - Enrique Navarrete, Jan 16 2017
a(n) = (n+1)!*hypergeom([-n], [-n-1], -1). - Peter Luschny, Nov 02 2018
Sum_{n>=0} (-1)^n*n!/(a(n)*a(n+1)) = e - 2 (Herzig, 1998). - Amiram Eldar, Mar 07 2022
a(n) = KummerU(-n, -n - 1, -1). - Peter Luschny, May 10 2022

cp's OEIS Frontend

A070315 Third diagonal of triangle in A046739.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A008292 Triangle of Eulerian numbers T(n,k) (n >= 1, 1 <= k <= n) read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

R

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

PARI

SageMath

Formula

A000255 a(n) = n*a(n-1) + (n-1)*a(n-2), a(0) = 1, a(1) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A000274 Number of permutations of length n with 2 consecutive ascending pairs.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

A000255 a(n) = na(n-1) + (n-1)a(n-2), a(0) = 1, a(1) = 1.

A081658 Triangle read by rows: T(n, k) = (-2)^kbinomial(n, k)Euler(k, 1/2).