A008306 -id:A008306 - cp's OEIS frontend

A000166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, 44750731559645106, 895014631192902121, 18795307255050944540, 413496759611120779881, 9510425471055777937262

Offset: 0

N. J. A. Sloane

Euler (1809) not only gives the first ten or so terms of the sequence, he also proves both recurrences a(n) = (n-1)*(a(n-1) + a(n-2)) and a(n) = n*a(n-1) + (-1)^n.
a(n) is the permanent of the matrix with 0 on the diagonal and 1 elsewhere. - Yuval Dekel, Nov 01 2003
a(n) is the number of desarrangements of length n. A desarrangement of length n is a permutation p of {1,2,...,n} for which the smallest of all the ascents of p (taken to be n if there are no ascents) is even. Example: a(3) = 2 because we have 213 and 312 (smallest ascents at i = 2). See the J. Désarménien link and the Bona reference (p. 118). - Emeric Deutsch, Dec 28 2007
a(n) is the number of deco polyominoes of height n and having in the last column an even number of cells. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. - Emeric Deutsch, Dec 28 2007
Attributed to Nicholas Bernoulli in connection with a probability problem that he presented. See Problem #15, p. 494, in "History of Mathematics" by David M. Burton, 6th edition. - Mohammad K. Azarian, Feb 25 2008
a(n) is the number of permutations p of {1,2,...,n} with p(1)!=1 and having no right-to-left minima in consecutive positions. Example a(3) = 2 because we have 231 and 321. - Emeric Deutsch, Mar 12 2008
a(n) is the number of permutations p of {1,2,...,n} with p(n)! = n and having no left to right maxima in consecutive positions. Example a(3) = 2 because we have 312 and 321. - Emeric Deutsch, Mar 12 2008
Number of wedged (n-1)-spheres in the homotopy type of the Boolean complex of the complete graph K_n. - Bridget Tenner, Jun 04 2008
The only prime number in the sequence is 2. - Howard Berman (howard_berman(AT)hotmail.com), Nov 08 2008
From Emeric Deutsch, Apr 02 2009: (Start)
a(n) is the number of permutations of {1,2,...,n} having exactly one small ascent. A small ascent in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. (Example: a(3) = 2 because we have 312 and 231; see the Charalambides reference, pp. 176-180.) [See also David, Kendall and Barton, p. 263. - N. J. A. Sloane, Apr 11 2014]
a(n) is the number of permutations of {1,2,...,n} having exactly one small descent. A small descent in a permutation (p_1,p_2,...,p_n) is a position i such that p_i - p_{i+1} = 1. (Example: a(3)=2 because we have 132 and 213.) (End)
For n > 2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11, 53, ...). - Gary W. Adamson, Apr 16 2009
Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610.) - Gary W. Adamson, Apr 17 2009
From Emeric Deutsch, Jul 18 2009: (Start)
a(n) is the sum of the values of the largest fixed points of all non-derangements of length n-1. Example: a(4)=9 because the non-derangements of length 3 are 123, 132, 213, and 321, having largest fixed points 3, 1, 3, and 2, respectively.
a(n) is the number of non-derangements of length n+1 for which the difference between the largest and smallest fixed point is 2. Example: a(3) = 2 because we have 1'43'2 and 32'14'; a(4) = 9 because we have 1'23'54, 1'43'52, 1'53'24, 52'34'1, 52'14'3, 32'54'1, 213'45', 243'15', and 413'25' (the extreme fixed points are marked).
(End)
a(n), n >= 1, is also the number of unordered necklaces with n beads, labeled differently from 1 to n, where each necklace has >= 2 beads. This produces the M2 multinomial formula involving partitions without part 1 given below. Because M2(p) counts the permutations with cycle structure given by partition p, this formula gives the number of permutations without fixed points (no 1-cycles), i.e., the derangements, hence the subfactorials with their recurrence relation and inputs. Each necklace with no beads is assumed to contribute a factor 1 in the counting, hence 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 01 2010
From Emeric Deutsch, Sep 06 2010: (Start)
a(n) is the number of permutations of {1,2,...,n, n+1} starting with 1 and having no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 1324 and 1432.
a(n) is the number of permutations of {1,2,...,n} that do not start with 1 and have no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 213 and 321.
(End)
Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleave except on the leftmost path, there is no vertex of outdegree one on the leftmost path. - Wenjin Woan, May 23 2011
a(n) is the number of zeros in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 2 pure options. - Raimundas Vidunas, Jan 22 2014
Convolution of sequence A135799 with the sequence generated by 1+x^2/(2*x+1). - Thomas Baruchel, Jan 08 2016
The number of interior lattice points of the subpolytope of the n-dimensional permutohedron whose vertices correspond to permutations avoiding 132 and 312. - Robert Davis, Oct 05 2016
Consider n circles of different radii, where each circle is either put inside some bigger circle or contains a smaller circle inside it (no common points are allowed). Then a(n) gives the number of such combinations. - Anton Zakharov, Oct 12 2016
If we partition the permutations of [n+1] in A000240 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n), i.e., A000240(n+1) = (n+1)*a(n), hence a(n) is the size of each class of permutations of [n+1] in A000240. For example, for n = 4 we have 45 = 5*9. - Enrique Navarrete, Jan 10 2017
Call d_n1 the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. If we partition them according to their starting digit, we will get (n-1) equinumerous classes each of size A000166(n-2) (the class starting with the digit 1 is empty since we must have the substring n1). Hence d_n1 = (n-1)*A000166(n-2) and A000166(n-2) is the size of each nonempty class in d_n1. For example, d_71 = 6*44 = 264, so there are 264 permutations in d_71 distributed in 6 nonempty classes of size A000166(5) = 44. (To get permutations in d_n1 recursively from more basic ones see the link "Forbidden Patterns" below.) - Enrique Navarrete, Jan 15 2017
Also the number of maximum matchings and minimum edge covers in the n-crown graph. - Eric W. Weisstein, Jun 14 and Dec 24 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) for all n and k, which in turn is easily proved by induction making use of the recurrence a(n) = n*a(n-1) + (-1)^n. - Peter Bala, Nov 21 2017
a(n) is the number of distinct possible solutions for a directed, no self loop containing graph (not necessarily connected) that has n vertices, and each vertex has an in- and out-degree of exactly 1. - Patrik Holopainen, Sep 18 2018
a(n) is the dimension of the kernel of the random-to-top and random-to-random shuffling operators over a collection of n objects (in a vector space of size n!), as noticed by M. Wachs and V. Reiner. See the Reiner, Saliola and Welker reference below. - Nadia Lafreniere, Jul 18 2019
a(n) is the number of distinct permutations for a Secret Santa gift exchange with n participants. - Patrik Holopainen, Dec 30 2019
a(2*n+1) is even. More generally, a(m*n+1) is divisible by m*n, which follows from a(n+1) = n*(a(n) + a(n-1)) = n*A000255(n-1) for n >= 1. a(2*n) is odd; in fact, a(2*n) == 1 (mod 8). Other divisibility properties include a(6*n) == 1 (mod 24), a(9*n+4) == a(9*n+7) == 0 (mod 9), a(10*n) == 1 (mod 40), a(11*n+5) == 0 (mod 11) and a(13*n+8 ) == 0 (mod 13). - Peter Bala, Apr 05 2022
Conjecture: a(n) with n > 2 is a perfect power only for n = 4 with a(4) = 3^2. This has been verified for n <= 1000. - Zhi-Wei Sun, Jan 09 2025

			a(2) = 1, a(3) = 2 and a(4) = 9 since the possibilities are {BA}, {BCA, CAB} and {BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA}. - _Henry Bottomley_, Jan 17 2001
The Boolean complex of the complete graph K_4 is homotopy equivalent to the wedge of 9 3-spheres.
Necklace problem for n = 6: partitions without part 1 and M2 numbers for n = 6: there are A002865(6) = 4 such partitions, namely (6), (2,4), (3^2) and (2^3) in A-St order with the M2 numbers 5!, 90, 40 and 15, respectively, adding up to 265 = a(6). This corresponds to 1 necklace with 6 beads, two necklaces with 2 and 4 beads respectively, two necklaces with 3 beads each and three necklaces with 2 beads each. - _Wolfdieter Lang_, Jun 01 2010
G.f. = 1 + x^2 + 9*x^3 + 44*x^4 + 265*x^5 + 1854*x^6 + 14833*x^7 + 133496*x^8 + ...

U. Abel, Some new identities for derangement numbers, Fib. Q., 56:4 (2018), 313-318.
M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 32.
R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section 7.2, p. 202.
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.
Florence Nightingale David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 168.
Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263, Table 7.5.1, row 1.
P. R. de Montmort, On the Game of Thirteen (1713), reprinted in Annotated Readings in the History of Statistics, ed. H. A. David and A. W. F. Edwards, Springer-Verlag, 2001, pp. 25-29.
J. M. de Saint-Martin, "Le problème des rencontres" in Quadrature, No. 61, pp. 14-19, 2006, EDP-Sciences Les Ulis (France).
H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 19.
Leonhard Euler, Solution quaestionis curiosae ex doctrina combinationum, Mémoires Académie sciences St. Pétersburg 3 (1809/1810), 57-64; also E738 in his Collected Works, series I, volume 7, pages 435-440.
J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
A. Hald, A History of Probability and Statistics and Their Applications Before 1750, Wiley, NY, 1990 (Chapter 19).
Irving Kaplansky, John Riordan, The problème des ménages. Scripta Math. 12 (1946), 113-124. See Eq(1).
Arnold Kaufmann, "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
Florian Kerschbaum and Orestis Terzidis, Filtering for Private Collaborative Benchmarking, in Emerging Trends in Information and Communication Security, Lecture Notes in Computer Science, Volume 3995/2006.
E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see p. 152.
P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 102.
M. S. Petković, "Non-attacking rooks", Famous Puzzles of Great Mathematicians, pp. 265-268, Amer. Math. Soc.(AMS), 2009.
V. Reiner, F. Saliola, and V. Welker. Spectra of Symmetrized Shuffling Operators, Memoirs of the American Mathematical Society, vol. 228, Amer. Math. Soc., Providence, RI, 2014, pp. 1-121. See section VI.9.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 23.
T. Simpson, Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
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).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 122.
D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 82.
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=1).

Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..200 from T. D. Noe)
Christian Aebi and Grant Cairns, Generalizations of Wilson's Theorem for Double-, Hyper-, Sub-and Superfactorials, The American Mathematical Monthly 122.5 (2015): 433-443.
Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).
Joerg Arndt, Matters Computational (The Fxtbook), p. 280.
Etor Arza, Aritz Perez, Ekhine Irurozki, and Josu Ceberio, Kernels of Mallows Models under the Hamming Distance for solving the Quadratic Assignment Problem, arXiv:1910.08800 [stat.ML], 2019.
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7.
Roland Bacher and P. De La Harpe, Conjugacy growth series of some infinitely generated groups, arXiv:1603.07943 [math.GR], 2016.
B. Balof and H. Jenne, Tilings, Continued Fractions, Derangements, Scramblings, and e, Journal of Integer Sequences, 17 (2014), #14.2.7.
V. Baltic, On the number of certain types of strongly restricted permutations, Appl. An. Disc. Math. 4 (2010), 119-135; Doi:10.2298/AADM1000008B.
E. Barcucci, A. Del Lungo, and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.
Arthur T. Benjamin and Joel Ornstein, A bijective proof of a derangement recurrence, Fibonacci Quart., 55(5):28-29, 2017.
H. Bergeron, E. M. F. Curado, J. P. Gazeau, and L. M. C. S. Rodrigues, A note about combinatorial sequences and Incomplete Gamma function, arXiv preprint arXiv: 1309.6910 [math.CO], 2013.
Natasha Blitvić and Einar Steingrímsson, Permutations, moments, measures, arXiv:2001.00280 [math.CO], 2020.
Stefano Capparelli, Margherita Maria Ferrari, Emanuele Munarini, and Norma Zagaglia Salvi, A Generalization of the "Problème des Rencontres", J. Int. Seq. 21 (2018), #18.2.8.
Lapo Cioni and Luca Ferrari, Preimages under the Queuesort algorithm, arXiv preprint arXiv:2102.07628 [math.CO], 2021; Discrete Math., 344 (2021), #112561.
P. Cvitanovic, Group theory for Feynman diagrams in non-Abelian gauge theories, Phys. Rev. D14 (1976), 1536-1553.
S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
R. Davis and B. Sagan, Pattern-Avoiding Polytopes, arXiv preprint arxiv:1609.01782 [math.CO], 2016.
J. Désarménien, Une autre interprétation du nombre de dérangements, Sem. Loth. Comb. B08b (1982) 11-16.
Emeric Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792 [math.CO], 2009.
R. M. Dickau, Derangement diagrams.
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019).
P. Duchon and R. Duvignau, A new generation tree for permutations, FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 679-690.
J. East and R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359 [math.GR], 2014.
Sergi Elizalde, A simple bijective proof of a familiar derangement recurrence, arXiv:2005.11312 [math.CO], 2020.
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.
FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation.
H. Fripertinger, The Rencontre Numbers. [Broken link]
Hannah Fry and Brady Haran, The Problems with Secret Santa, Numberphile video (2016).
Jason Fulman and Robert Guralnick, Derangements in simple and primitive groups, arXiv:math/0208022 [math.GR], 2002.
J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83. [Annotated scanned copy]
Zbigniew Gołębiewski and Mateusz Klimczak, Protection Number of Recursive Trees, 2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO).
O. Gonzalez, C. Beltran, and I. Santamaria, On the Number of Interference Alignment Solutions for the K-User MIMO Channel with Constant Coefficients, arXiv preprint arXiv:1301.6196 [cs.IT], 2013.
G. Gordon and E. McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly, 117 (2010), 865-88.
Shyam Sunder Gupta, Fascinating Factorials, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 16, 411-442.
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993. [Annotated scanned copy]
Amihay Hanany, Vishnu Jejjala, Sanjaye Ramgoolam, and Rak-Kyeong Seong, Consistency and Derangements in Brane Tilings, arXiv:1512.09013 [hep-th], 2015.
Mehdi Hassani, Derangements and Applications, Journal of Integer Sequences, Vol. 6 (2003), #03.1.2.
M. Hassani, Counting and computing by e, arXiv:math/0606613 [math.CO], 2006.
Nick Hobson, Python program.
Q.-H. Hou, Z.-W. Sun and H.-M. Wen, On monotonicity of some combinatorial sequences, arXiv:1208.3903 [math.CO], 2012-2014.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 21.
E. Irurozki, B. Calvo, and J. A. Lozano, Sampling and learning the Mallows and Weighted Mallows models under the Hamming distance, 2014.
Ekhine Irurozki, B. Calvo, and J. A. Lozano, PerMallows: An R Package for Mallows and Generalized Mallows Models, Journal of Statistical Software, August 2016, Volume 71, Issue 12. doi: 10.18637/jss.v071.i12.
Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
Shirali Kadyrov and Farukh Mashurov, Generalized continued fraction expansions for Pi and E, arXiv:1912.03214 [math.NT], 2019.
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 220.
A. R. Kräuter, Über die Permanente gewisser zirkulärer Matrizen..., Séminaire Lotharingien de Combinatoire, B11b (1984), 11 pp.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Les Tablettes du Chercheur, 52. Combinaisons, pp. 10-11, Dec 01 1890.
Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
E. Lucas, Théorie des nombres (annotated scans of a few selected pages).
T. Mansour and M. Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., 339 (2016), 1368-1376.
Richard J. Martin and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
Ivica Martinjak and Dajana Stanić, A Short Combinatorial Proof of Derangement Identity, arXiv:1711.04537 [math.CO], 2017.
R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72:411--425, 1997.
J. R. G. Mendonça, On the uniform generation of random derangements, arXiv:1809.04571 [stat.CO], 2018.
Romeo Mestrovic, Variations of Kurepa's left factorial hypothesis, arXiv preprint arXiv:1312.7037 [math.NT], 2013.
Emanuele Munarini, q-Derangement Identities, J. Int. Seq., Vol. 23 (2020), Article 20.3.8.
Emanuele Munarini, Two-Parameter Identities for q-Appell Polynomials, Journal of Integer Sequences, Vol. 26 (2023), Article 23.3.1.
Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.
Andrew O'Desky and David Harry Richman, Derangements and the p-adic incomplete gamma function, arXiv:2012.04615 [math.NT], 2020.
R. Ondrejka, The first 100 exact subfactorials (Review), Math. Comp., 21 (1967), 502.
Hyungju Park, An Asymptotic Formula for the Number of Stabilized-Interval-Free Permutations, J. Int. Seq. (2023) Vol. 26, Art. 23.9.3.
P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
Simon Plouffe, Exact formulas for integer sequences.
K. Ragnarsson and B. E. Tenner, Homotopy type of the Boolean complex of a Coxeter system, Adv. Math. 222 (2009), 409-430.
J. B. Remmel, A note on a recursion for the number of derangements, European J. Combin., 4(4):371-374, 1983.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381-382.
M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381-382. [Annotated scanned copy]
E. Sandifer, How Euler Did It, Derangements.
M. Shattuck, Combinatorial proofs of some Bell number formulas, arXiv preprint arXiv:1401.6588 [math.CO], 2014.
T. Simpson, Permutations with unique fixed and reflected points, Preprint. (Annotated scanned copy)
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
R. J. Stones, S. Lin, X. Liu, and G. Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1.
Xinyu Sun, New Lower Bound On The Number of Ternary Square-Free Words, J. Integer Seqs., Vol. 6, 2003.
L. Takacs, The Problem of Coincidences, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp. 229-244, paragraph 3.
R. Vidunas, MacMahon's master theorem and totally mixed Nash equilibria, arXiv:1401.5400 [math.CO], 2014, see (7).
G. Villemin's Almanach of Numbers, Sous-factorielle.
Chenying Wang, Piotr Miska, and István Mezo, The r-derangement numbers, Discrete Mathematics 340.7 (2017): 1681-1692.
Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595 [math.CO], 2013.
Eric Weisstein's World of Mathematics, Crown Graph.
Eric Weisstein's World of Mathematics, Derangement.
Eric Weisstein's World of Mathematics, Edge Cover.
Eric Weisstein's World of Mathematics, Exponential Distribution.
Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set.
Eric Weisstein's World of Mathematics, Rooks Problem.
Eric Weisstein's World of Mathematics, Subfactorial.
Wikipedia, Derangement.
Wikipedia, Rencontres numbers.
Herbert S. Wilf, A bijection in the theory of derangements, Mathematics Magazine, 57(1):37-40, 1984.
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=1).
E. M. Wright, Arithmetical properties of Euler's rencontre number, J. London Math. Soc., (2) (1971/1972), 437-442.
D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.
OEIS Wiki, Derangement numbers.
OEIS Wiki, Rencontres numbers.
Index entries for "core" sequences.
Index entries for sequences related to binary matrices.

Cf. A000142, A002467, A003221, A000522, A000240, A000387, A000449, A000475, A129135, A092582, A000255, A002469, A159610, A068985, A068996, A047865, A038205, A008279, A281682.
For the probabilities a(n)/n!, see A053557/A053556 and A103816/A053556.
A diagonal of A008291 and A068106. Column A008290(n,0).
A001120 has a similar recurrence.
For other derangement numbers see also A053871, A033030, A088991, A088992.
Pairwise sums of A002741 and A000757. Differences of A001277.
Cf. A101560, A101559, A000110, A101033, A101032, A000204, A100492, A099731, A000045, A094216, A094638, A000108.
A diagonal in triangles A008305 and A010027.
a(n)/n! = A053557/A053556 = (N(n, n) of A103361)/(D(n, n) of A103360).
Column k=0 of A086764 and of A334715. Column k=1 of A364068.
Row sums of A216963 and of A323671.

a000166 n = a000166_list !! n
a000166_list = 1 : 0 : zipWith (*) [1..]
                       (zipWith (+) a000166_list $ tail a000166_list)
-- Reinhard Zumkeller, Dec 09 2012

I:=[0,1]; [1] cat [n le 2 select I[n] else (n-1)*(Self(n-1)+Self(n-2)): n in [1..30]]; // Vincenzo Librandi, Jan 07 2016

A000166 := proc(n) option remember; if n<=1 then 1-n else (n-1)*(procname(n-1)+procname(n-2)); fi; end;
a:=n->n!*sum((-1)^k/k!, k=0..n): seq(a(n), n=0..21); # Zerinvary Lajos, May 17 2007
ZL1:=[S,{S=Set(Cycle(Z,card>1))},labeled]: seq(count(ZL1,size=n),n=0..21); # Zerinvary Lajos, Sep 26 2007
with (combstruct):a:=proc(m) [ZL,{ZL=Set(Cycle(Z,card>=m))},labeled]; end: A000166:=a(2):seq(count(A000166,size=n),n=0..21); # Zerinvary Lajos, Oct 02 2007
Z := (x, m)->m!^2*sum(x^j/((m-j)!^2), j=0..m): R := (x, n, m)->Z(x, m)^n: f := (t, n, m)->sum(coeff(R(x, n, m), x, j)*(t-1)^j*(n*m-j)!, j=0..n*m): seq(f(0, n, 1), n=0..21); # Zerinvary Lajos, Jan 22 2008
a:=proc(n) if `mod`(n,2)=1 then sum(2*k*factorial(n)/factorial(2*k+1), k=1.. floor((1/2)*n)) else 1+sum(2*k*factorial(n)/factorial(2*k+1), k=1..floor((1/2)*n)-1) end if end proc: seq(a(n),n=0..20); # Emeric Deutsch, Feb 23 2008
G(x):=2*exp(-x)/(1-x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n]/2,n=0..21); # Zerinvary Lajos, Apr 03 2009
seq(simplify(KummerU(-n, -n, -1)), n = 0..23); # Peter Luschny, May 10 2022

a[0] = 1; a[n_] := n*a[n - 1] + (-1)^n; a /@ Range[0, 21] (* Robert G. Wilson v *)
a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 (* Michael Taktikos, May 26 2006 *)
Range[0, 20]! CoefficientList[ Series[ Exp[ -x]/(1 - x), {x, 0, 20}], x]
dr[{n_,a1_,a2_}]:={n+1,a2,n(a1+a2)}; Transpose[NestList[dr,{0,0,1},30]][[3]] (* Harvey P. Dale, Feb 23 2013 *)
a[n_] := (-1)^n HypergeometricPFQ[{- n, 1}, {}, 1]; (* Michael Somos, Jun 01 2013 *)
a[n_] := n! SeriesCoefficient[Exp[-x] /(1 - x), {x, 0, n}]; (* Michael Somos, Jun 01 2013 *)
Table[Subfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Jan 10 2014 *)
RecurrenceTable[{a[n] == n*a[n - 1] + (-1)^n, a[0] == 1}, a, {n, 0, 23}] (* Ray Chandler, Jul 30 2015 *)
Subfactorial[Range[0, 20]] (* Eric W. Weisstein, Dec 31 2017 *)
nxt[{n_,a_}]:={n+1,a(n+1)+(-1)^(n+1)}; NestList[nxt,{0,1},25][[All,2]] (* Harvey P. Dale, Jun 01 2019 *)

s[0]:1$
s[n]:=n*s[n-1]+(-1)^n$
makelist(s[n],n,0,12); /* Emanuele Munarini, Mar 01 2011 */

{a(n) = if( n<1, 1, n * a(n-1) + (-1)^n)}; /* Michael Somos, Mar 24 2003 */

{a(n) = n! * polcoeff( exp(-x + x * O(x^n)) / (1 - x), n)}; /* Michael Somos, Mar 24 2003 */

{a(n)=polcoeff(sum(m=0,n,m^m*x^m/(1+(m+1)*x+x*O(x^n))^(m+1)),n)} /* Paul D. Hanna */

A000166=n->n!*sum(k=0,n,(-1)^k/k!) \\ M. F. Hasler, Jan 26 2012

a(n)=if(n,round(n!/exp(1)),1) \\ Charles R Greathouse IV, Jun 17 2012

apply( {A000166(n)=n!\/exp(n>0)}, [0..22]) \\ M. F. Hasler, Nov 09 2024

Python
```
See Hobson link.
```

A000166_list, m, x = [], 1, 1
for n in range(10*2):
    x, m = x*n + m, -m
    A000166_list.append(x) # Chai Wah Wu, Nov 03 2014

(A000166 + A000522)/2 = A009179, (A000166 - A000522)/2 = A009628.
a(n) = A008290(n,0).
a(n) + A003048(n+1) = 2*n!. - D. G. Rogers, Aug 26 2006
a(n) = {(n-1)!/exp(1)}, n > 1, where {x} is the nearest integer function. - Simon Plouffe, March 1993 [This uses offset 1, see below for the version with offset 0. - Charles R Greathouse IV, Jan 25 2012]
a(0) = 1, a(n) = round(n!/e) = floor(n!/e + 1/2) for n > 0.
a(n) = n!*Sum_{k=0..n} (-1)^k/k!.
D-finite with recurrence a(n) = (n-1)*(a(n-1) + a(n-2)), n > 0.
a(n) = n*a(n-1) + (-1)^n.
E.g.f.: exp(-x)/(1-x).
a(n) = Sum_{k=0..n} binomial(n, k)*(-1)^(n-k)*k! = Sum_{k=0..n} (-1)^(n-k)*n!/(n-k)!. - Paul Barry, Aug 26 2004
The e.g.f. y(x) satisfies y' = x*y/(1-x).
Inverse binomial transform of A000142. - Ross La Haye, Sep 21 2004
In Maple notation, representation as n-th moment of a positive function on [-1, infinity]: a(n)= int( x^n*exp(-x-1), x=-1..infinity ), n=0, 1... . a(n) is the Hamburger moment of the function exp(-1-x)*Heaviside(x+1). - Karol A. Penson, Jan 21 2005
a(n) = A001120(n) - n!. - Philippe Deléham, Sep 04 2005
a(n) = Integral_{x=0..oo} (x-1)^n*exp(-x) dx. - Gerald McGarvey, Oct 14 2006
a(n) = Sum_{k=2,4,...} T(n,k), where T(n,k) = A092582(n,k) = k*n!/(k+1)! for 1 <= k < n and T(n,n)=1. - Emeric Deutsch, Feb 23 2008
a(n) = n!/e + (-1)^n*(1/(n+2 - 1/(n+3 - 2/(n+4 - 3/(n+5 - ...))))). Asymptotic result (Ramanujan): (-1)^n*(a(n) - n!/e) ~ 1/n - 2/n^2 + 5/n^3 - 15/n^4 + ..., where the sequence [1,2,5,15,...] is the sequence of Bell numbers A000110. - Peter Bala, Jul 14 2008
From William Vaughn (wvaughn(AT)cvs.rochester.edu), Apr 13 2009: (Start)
a(n) = Integral_{p=0..1} (log(1/(1-p)) - 1)^n dp.
Proof: Using the substitutions 1=log(e) and y = e(1-p) the above integral can be converted to ((-1)^n/e) Integral_{y=0..e} (log(y))^n dy.
From CRC Integral tables we find the antiderivative of (log(y))^n is (-1)^n n! Sum_{k=0..n} (-1)^k y(log(y))^k / k!.
Using the fact that e(log(e))^r = e for any r >= 0 and 0(log(0))^r = 0 for any r >= 0 the integral becomes n! * Sum_{k=0..n} (-1)^k / k!, which is line 9 of the Formula section. (End)
a(n) = exp(-1)*Gamma(n+1,-1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009
G.f.: 1/(1-x^2/(1-2x-4x^2/(1-4x-9x^2/(1-6x-16x^2/(1-8x-25x^2/(1-... (continued fraction). - Paul Barry, Nov 27 2009
a(n) = Sum_{p in Pano1(n)} M2(p), n >= 1, with Pano1(n) the set of partitions without part 1, and the multinomial M2 numbers. See the characteristic array for partitions without part 1 given by A145573 in Abramowitz-Stegun (A-S) order, with A002865(n) the total number of such partitions. The M2 numbers are given for each partition in A-St order by the array A036039. - Wolfdieter Lang, Jun 01 2010
a(n) = row sum of A008306(n), n > 1. - Gary Detlefs, Jul 14 2010
a(n) = ((-1)^n)*(n-1)*hypergeom([-n+2, 2], [], 1), n>=1; 1 for n=0. - Wolfdieter Lang, Aug 16 2010
a(n) = (-1)^n * hypergeom([ -n, 1], [], 1), n>=1; 1 for n=0. From the binomial convolution due to the e.g.f. - Wolfdieter Lang, Aug 26 2010
Integral_{x=0..1} x^n*exp(x) = (-1)^n*(a(n)*e - n!).
O.g.f.: Sum_{n>=0} n^n*x^n/(1 + (n+1)*x)^(n+1). - Paul D. Hanna, Oct 06 2011
Abs((a(n) + a(n-1))*e - (A000142(n) + A000142(n-1))) < 2/n. - Seiichi Kirikami, Oct 17 2011
G.f.: hypergeom([1,1],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Nov 25 2011, Jul 05 2012, Sep 23 2012, Oct 13 2012, Mar 09 2013, Mar 10 2013, Oct 18 2013: (Start)
Continued fractions:
In general, e.g.f. (1+a*x)/exp(b*x) = U(0) with U(k) = 1 + a*x/(1-b/(b-a*(k+1)/U(k+1))). For a=-1, b=-1: exp(-x)/(1-x) = 1/U(0).
E.g.f.: (1-x/(U(0)+x))/(1-x), where U(k) = k+1 - x + (k+1)*x/U(k+1).
E.g.f.: 1/Q(0) where Q(k) = 1 - x/(1 - 1/(1 - (k+1)/Q(k+1))).
G.f.: 1/U(0) where U(k) = 1 + x - x*(k+1)/(1 - x*(k+1)/U(k+1)).
G.f.: Q(0)/(1+x) where 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 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: T(0) where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2-(1-2*x*k)*(1-2*x-2*x*k)/T(k+1)). (End)
0 = a(n)*(a(n+1) + a(n+2) - a(n+3)) + a(n+1)*(a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2)*a(n+2) if n>=0. - Michael Somos, Jan 25 2014
a(n) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^k*(k + x + 1)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^(n-k)*(k + x - 1)^k, for arbitrary x. - Peter Bala, Feb 19 2017
From Peter Luschny, Jun 20 2017: (Start)
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(-j-1, -n-1)*abs(Stirling1(j, k)).
a(n) = Sum_{k=0..n} (-1)^(n-k)*Pochhammer(n-k+1, k) (cf. A008279). (End)
a(n) = n! - Sum_{j=0..n-1} binomial(n,j) * a(j). - Alois P. Heinz, Jan 23 2019
Sum_{n>=2} 1/a(n) = A281682. - Amiram Eldar, Nov 09 2020
a(n) = KummerU(-n, -n, -1). - Peter Luschny, May 10 2022
a(n) = (-1)^n*Sum_{k=0..n} Bell(k)*Stirling1(n+1, k+1). - Mélika Tebni, Jul 05 2022

Minor edits by M. F. Hasler, Jan 16 2017

A340556 E2(n, k), the second-order Eulerian numbers with E2(0, k) = δ_{0, k}. Triangle read by rows, E2(n, k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 8, 6, 0, 1, 22, 58, 24, 0, 1, 52, 328, 444, 120, 0, 1, 114, 1452, 4400, 3708, 720, 0, 1, 240, 5610, 32120, 58140, 33984, 5040, 0, 1, 494, 19950, 195800, 644020, 785304, 341136, 40320, 0, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880

Offset: 0

Peter Luschny, Feb 05 2021

The second-order Eulerian number E2(n, k) is the number of Stirling permutations of order n with exactly k descents; here the last index is defined to be a descent. More formally, let Q_n denote the set of permutations of the multiset {1,1,2,2, ..., n,n} in which, for all j, all entries between two occurrences of j are larger than j, then E2(n, k) = card({s in Q_n with des(s) = k}), where des(s) = card({j: s(j) > s(j+1)}) is the number of descents of s.
Also the number of Riordan trapezoidal words of length n with k distinct letters (see Riordan 1976, p. 9).
Also the number of rooted plane trees on n + 1 vertices with k leaves (see Janson 2008, p. 543).
Let b(n) = (1/2)*Sum_{k=0..n-1} (-1)^k*E2(n-1, k+1) / C(2*n-1, k+1). Apparently b(n) = Bernoulli(n, 1) = -n*Zeta(1 - n) = Integral_{x=0..1}F_n(x) for n >= 1. Here F_n(x) are the signed Fubini polynomials (A278075). (See Rzadkowski and Urlinska, example 4.)

			Triangle starts:
  [0] 1;
  [1] 0, 1;
  [2] 0, 1, 2;
  [3] 0, 1, 8,    6;
  [4] 0, 1, 22,   58,    24;
  [5] 0, 1, 52,   328,   444,     120;
  [6] 0, 1, 114,  1452,  4400,    3708,    720;
  [7] 0, 1, 240,  5610,  32120,   58140,   33984,    5040;
  [8] 0, 1, 494,  19950, 195800,  644020,  785304,   341136,   40320;
  [9] 0, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880.
To illustrate the generating function for row 3: The expansion of (1 - x)^7*(x*exp(-x) + 16*x^2*exp(-x)^2 + (243*x^3*exp(-x)^3)/2) gives the polynomial x + 8*x^2 + 6*x^3. The coefficients of this polynomial give row 3.
.
Stirling permutations of order 3 with exactly k descents: (When counting the descents one may assume an invisible '0' appended to the permutations.)
  T[3, k=0]:
  T[3, k=1]: 112233;
  T[3, k=2]: 331122; 223311; 221133; 133122; 122331; 122133; 113322; 112332;
  T[3, k=3]: 332211; 331221; 233211; 221331; 133221; 123321.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270.

J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3), 2015.
Kenny Barrese, Jennifer Elder, Pamela E. Harris, and Anthony Simpson, Enumerating Flat Fubini Rankings, arXiv:2504.06466 [math.CO], 2025. Conjecture 4.4. p. 14.
Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.10.1), Thesis, Brandeis Univ., Aug. 2008, p. 58.
Sergi Elizalde, Descents on quasi-Stirling permutations, arXiv:2002.00985 [math.CO], 2020.
I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24, 24-33, 1978.
Svante Janson, Plane recursive trees, Stirling permutations and an urn model, Fifth Colloquium on Mathematics and Computer Science, 541-547, Discrete Math. Theor. Comput. Sci. Proc., AI, 2008.
Peter Luschny, A companion to A340556, A SageMath-Jupyter notebook, Feb. 2021.
Peter Luschny, How are the Eulerian numbers of the first-order related to the Eulerian numbers of the second-order?, MathOverflow, Feb. 2021.
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.
John Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16.
G. Rzadkowski and M. Urlinska, A Generalization of the Eulerian Numbers, arXiv:1612.06635 [math.CO], 2016.

Indexing the second-order Eulerian numbers comes in three flavors: A008517 (following Riordan and Comtet), A201637 (following Graham, Knuth, and Patashnik) and this indexing, extending the definition of Gessel and Stanley. (A008517 is the main entry of the numbers.) The corresponding triangles of the first-order Eulerian numbers are A008292, A173018, and A123125.
Row reversed: A163936 (with offset = 0).
Values: E2poly(n, 1) = A001147(n), E2poly(n, -1) ~ -A001662(n+1), E2poly(n, 2) = A112487(n), 2^n*E2poly(n, 1/2) = A000311(n+1), 2^n*E2poly(n, -1/2) = A341106(n).
Diagonals: A000142, A002538, A002539, A112008, A112485.
Columns: A000007, A000012, A005803, A004301, A006260.
Cf. A008299, A137375, A008306, A106828, A269939, A278075, A331998.

# Using the recurrence:
E2 := proc(n, k) option remember;
if k = 0 and n = 0 then return 1 fi; if n < 0 then return 0 fi;
E2(n-1, k)*k + E2(n-1, k-1)*(2*n - k) end: seq(seq(E2(n, k), k = 0..n), n = 0..9);
# Using the row generating function:
E2egf := n -> (1-x)^(2*n+1)*add(k^(n+k)/k!*(x*exp(-x))^k, k=0..n);
T := (n, k) -> coeftayl(E2egf(n), x=0, k): seq(print(seq(T(n, j),j=0..n)), n=0..7);
# Using the built-in function:
E2 := (n, k) -> `if`(k=0, k^n, combinat:-eulerian2(n, k-1)):
# Using the compositional inverse (series reversion):
E2triangle := proc(N) local r, s, C; Order := N + 2;
s := solve(y = series(x - t*(exp(x) - 1), x), x):
r := n -> -n!*(t - 1)^(2*n - 1)*coeff(s, y, n); C := [seq(expand(r(n)), n = 1..N)];
seq(print(seq(coeff(C[n+1], t, k), k = 0..n)), n = 0..N-1) end: E2triangle(10);

T[n_, k_] := T[n, k] = If[k == 0, Boole[n == 0], If[n < 0, 0, k T[n - 1, k] + (2 n - k) T[n - 1, k - 1]]]; Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten
(* Via row polynomials: *)
E2poly[n_] := If[n == 0, 1,
  Expand[Simplify[x (x - 1)^(2 n) D[((1 - x)^(1 - 2 n) E2poly[n - 1]), x]]]];
Table[CoefficientList[E2poly[n], x], {n, 0, 9}] // Flatten
(* Series reversion *)
Revert[gf_, len_] := Module[{S = InverseSeries[Series[gf, {x, 0, len + 1}], x]},
Table[CoefficientList[(n + 1)! (1 - t)^(2 n + 1) Coefficient[S, x, n + 1], t],
{n, 0, len}] // Flatten]; Revert[x + t - t Exp[x], 6]

E2poly(n) = if(n == 0, 1, x*(x-1)^(2*n)*deriv((1-x)^(1-2*n)*E2poly(n-1)));
{ for(n = 0, 9, print(Vecrev(E2poly(n)))) }

T(n, k) = sum(j=0, n-k, (-1)^(n-j)*binomial(2*n+1, j)*stirling(2*n-k-j+1, n-k-j+1, 1)); \\ Michel Marcus, Feb 11 2021

# See also link to notebook.
@cached_function
def E2(n, k):
    if n < 0: return 0
    if k == 0: return k^n
    return k * E2(n - 1, k) + (2*n - k) * E2(n - 1, k - 1)  # Peter Luschny, Mar 08 2025

E2(n, k) = E2(n-1, k)*k + E2(n-1, k-1)*(2*n - k) for n > 0 and 0 <= k <= n, and E2(0, 0) = 1; in all other cases E(n, k) = 0.
E2(n, k) = Sum_{j=0..n-k}(-1)^(n-j)*binomial(2*n+1, j)*Stirling1(2*n-k-j+1, n-k-j+1).
E2(n, k) = Sum_{j=0..k}(-1)^(k-j)*binomial(2*n + 1, k - j)*Stirling2(n + j, j).
Stirling1(x, x - n) = (-1)^n*Sum_{k=0..n} E2(n, k)*binomial(x + k - 1, 2*n).
Stirling2(x, x - n) = Sum_{k=0..n} E2(n, k)*binomial(x + n - k, 2*n).
E2poly(n, x) = Sum_{k=0..n} E2(n, k)*x^k, as row polynomials.
E2poly(n, x) = x*(x-1)^(2*n)*d_{x}((1-x)^(1-2*n)*E2poly(n-1)) for n>=1 and E2poly(0)=1.
E2poly(n, x) = (1 - x)^(2*n + 1)*Sum_{k=0..n}(k^(n + k)/k!)*(x*exp(-x))^k.
W(n, k) = [x^k] (1+x)^n*E2poly(n, x/(1 + x)) are the Ward numbers A269939.
E2(n, k) = [x^k] (1-x)^n*Wpoly(n, x/(1 - x)); Wpoly(n, x) = Sum_{k=0..n}W(n, k)*x^k.
W(n, k) = Sum_{j=0..k} E2(n, j)*binomial(n - j, n - k).
E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*W(n, j)*binomial(n - j, k - j).
The compositional inverse with respect to x of x - t*(exp(x) - 1) (see B. Drake):
T(n, k) = [t^k](n+1)!*(1-t)^(2*n+1)*[x^(n+1)] InverseSeries(x - t*(exp(x)-1), x).
AS1(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, j+1), where AS1(n, k) are the associated Stirling numbers of the first kind (A008306, A106828).
E2(n, k) = Sum_{j=0..n-k+1} (-1)^(n-k-j+1)*AS1(n+j, j)*binomial(n-j, n-k-j+1), for n >= 1.
AS2(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, n-k-j) for n >=1, where AS2(n, k) are the associated Stirling numbers of the second kind (A008299, A137375).
E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*AS2(n + j, j)*binomial(n - j, k - j).

A032188 Number of labeled series-reduced mobiles (circular rooted trees) with n leaves (root has degree 0 or >= 2).

Original entry on oeis.org

1, 1, 5, 41, 469, 6889, 123605, 2620169, 64074901, 1775623081, 54989743445, 1882140936521, 70552399533589, 2874543652787689, 126484802362553045, 5977683917752887689, 301983995802099667861, 16239818347465293071401, 926248570498763547197525, 55847464116157184894240201

Offset: 1

Christian G. Bower

With offset 0, a(n) = number of partitions of the multiset {1,1,2,2,...,n,n} into lists of strictly decreasing lists, called blocks, such that the concatenation of all blocks in a list has the Stirling property: all entries between the two occurrences of i exceed i, 1<=i<=n. For example, with slashes separating blocks, a(2) = 5 counts 1/1/2/2; 1/2/2/1; 2/2/1/1; 1/2/2 1; 2/2 1/1, but not, for instance, 2 1/2/1 because it fails the Stirling test for i=2. - David Callan, Nov 21 2011

			D^3(1) = (24*x^2-64*x+41)/(2*x-1)^6. Evaluated at x = 0 this gives a(4) = 41.
a(3) = 5: Denote the colors of the vertices by the letters a,b,c, .... The 5 possible increasing plane trees on 3 vertices with vertices of outdegree k coming in 2^(k-1) colors are
.
   1a       1a        1b        1a        1b
   |       /  \      /  \      /  \      /  \
   2a     2    3    2    3    3    2    3    2
   |
   3

Andrew Howroyd, Table of n, a(n) for n = 1..200
François Bergeron, Philippe Flajolet, and Bruno Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Bishal Deb and Alan D. Sokal, Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness, arXiv:2507.18959 [math.CO], 2025. See pp. 6, 16, 30.
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions arXiv:math/0501052 [math.CA], 2005.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 89
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See p. 12.
Index entries for sequences related to mobiles

Cf. A006351, A032034.

Order := 20; t1 := solve(series((ln(1-A)+2*A),A)=x,A); A000311 := n->n!*coeff(t1,x,n);
# With offset 0:
a := n -> add(combinat:-eulerian2(n,k)*2^k,k=0..n):
seq(a(n),n=0..19); # Peter Luschny, Jul 09 2015

For[y=x+O[x]^21; oldy=0, y=!=oldy, oldy=y; y=((1-y)Log[1-y]+x*y+y-x)/(2y-1), Null]; Table[n!Coefficient[y, x, n], {n, 1, 20}]
Rest[CoefficientList[InverseSeries[Series[2*x + Log[1-x],{x,0,20}],x],x] * Range[0,20]!] (* Vaclav Kotesovec, Jan 08 2014 *)

a(n):=sum((n+k-1)!*sum(1/(k-j)!*sum((2^l*(-1)^(n+l+1)*stirling1(n-l+j-1,j-l))/(l!*(n-l+j-1)!),l,0,j),j,0,k),k,0,n-1); /* Vladimir Kruchinin, Feb 06 2012 */

N = 66; x = 'x + O('x^N);
Q(k) = if(k>N, 1,  1 + (k+1)*x - 2*x*(k+1)/Q(k+1) );
gf = 1/Q(0); Vec(gf) \\ Joerg Arndt, May 01 2013

{my(n=20); Vec(serlaplace(serreverse(2*x+log(1-x + O(x*x^n)))))} \\ Andrew Howroyd, Jan 16 2018

Doubles (index 2+) under "CIJ" (necklace, indistinct, labeled) transform.
E.g.f. A(x) satisfies log(1-A(x))+2*A(x)-x = 0. - Vladeta Jovovic, Dec 06 2002
With offset 0, second Eulerian transform of the powers of 2 [A000079]. See A001147 for definition of SET. - Ross La Haye, Feb 14 2005
From Peter Bala, Sep 05 2011: (Start)
The generating function A(x) satisfies the autonomous differential equation A'(x) = (1-A)/(1-2*A) with A(0) = 0. Hence the inverse function A^-1(x) = int {t = 0..x} (1-2*t)/(1-t) = 2*x+log(1-x). The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1-x)/(1-2*x)*g(x)). Compare with A006351.
Applying [Bergeron et al., Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1-t)/(1-2*t) = 1+t+2*t^2+4*t^3+8*t^4+... leads to the following combinatorial interpretation for this sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >= 1 can be colored in 2^(k-1) ways. An example is given below. (End)
The integral from 0 to infinity w.r.t. w of exp(-2w)(1-z*w)^(-1/z) gives an o.g.f. for the series with offset 0. Consequently, a(n)= sum(j=1 to infinity): St1d(n,j)/(2^(n+j-1)) where St1d(n,j) is the j-th element of the n-th diagonal of A132393 with offset=1; e.g., a(3)= 5 = 0/2^3 + 2/2^4 + 11/2^5 + 35/2^6 + 85/2^7 + ... . - Tom Copeland, Sep 15 2011
A signed o.g.f., with Γ(v,x) the incomplete gamma function (see A111999 with u=1), is g(z) = (2/z)^(-(1/z)-1) exp(2/z) Γ((1/z)+1,2/z)/z. - Tom Copeland, Sep 16 2011
With offset 0, a(n) = Sum[T(n+k,k), k=1..n] where T(n,k) are the associated Stirling numbers of the first kind (A008306). For example, a(3) = 41 = 6 + 20 + 15. - David Callan, Nov 21 2011
a(n) = sum(k=0..n-1, (n+k-1)!*sum(j=0..k, 1/(k-j)!*sum(l=0..j, (2^l*(-1)^(n+l+1)*stirling1(n-l+j-1,j-l))/(l!*(n-l+j-1)!)))), n>0. - Vladimir Kruchinin, Feb 06 2012
G.f.: 1/Q(0), where Q(k)= 1 + (k+1)*x - 2*x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
a(n) ~ n^(n-1) / (2 * exp(n) * (1-log(2))^(n-1/2)). - Vaclav Kotesovec, Jan 08 2014
a(n) = A032034(n)/2. - Alois P. Heinz, Jul 04 2018
E.g.f: series reversion of 2*x + log(1-x). - Andrew Howroyd, Sep 19 2018

A136394 Triangle read by rows: T(n,k) is the number of permutations of an n-set having k cycles of size > 1 (0<=k<=floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 1, 5, 1, 20, 3, 1, 84, 35, 1, 409, 295, 15, 1, 2365, 2359, 315, 1, 16064, 19670, 4480, 105, 1, 125664, 177078, 56672, 3465, 1, 1112073, 1738326, 703430, 74025, 945, 1, 10976173, 18607446, 8941790, 1346345, 45045, 1, 119481284, 216400569, 118685336

Offset: 0

Vladeta Jovovic, May 03 2008

			Triangle (n,k) begins:
  1;
  1;
  1,    1;
  1,    5;
  1,   20,    3;
  1,   84,   35;
  1,  409,  295,  15;
  1, 2365, 2359, 315;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Jean-Luc Baril and Sergey Kirgizov, Transformation à la Foata for special kinds of descents and excedances, arXiv:2101.01928 [math.CO], 2021. See Theorem 2. p. 5.
FindStat - Combinatorial Statistic Finder, The number of nontrivial cycles of a permutation pi in its cycle decomposition
Bin Han, Jianxi Mao, and Jiang Zeng, Equidistributions around special kinds of descents and excedances, arXiv:2103.13092 [math.CO], 2021, see page 2.

Columns k=0-10 give: A000012, A006231, A289950, A289951, A289952, A289953, A289954, A289955, A289956, A289957, A289958.
Row sums give A000142.
Cf. A000276, A000483, A001147, A001705, A051577, A124324, A159964.

egf:= proc(k::nonnegint) option remember; x-> exp(x)* ((-x-ln(1-x))^k)/k! end; T:= (n,k)-> coeff(series(egf(k)(x), x=0, n+1), x, n) *n!; seq(seq(T(n,k), k=0..n/2), n=0..30); # Alois P. Heinz, Aug 14 2008
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(b(n-i)*
      `if`(i>1, x, 1)*binomial(n-1, i-1)*(i-1)!, i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..15);  # Alois P. Heinz, Sep 25 2016
# third Maple program:
T:= proc(n, k) option remember; `if`(k<0 or k>2*n, 0,
      `if`(n=0, 1, add(T(n-i, k-`if`(i>1, 1, 0))*
       mul(n-j, j=1..i-1), i=1..n)))
    end:
seq(seq(T(n,k), k=0..n/2), n=0..15);  # Alois P. Heinz, Jul 16 2017

max = 12; egf = Exp[x*(1-y)]/(1-x)^y; s = Series[egf, {x, 0, max}, {y, 0, max}] // Normal; t[n_, k_] := SeriesCoefficient[s, {x, 0, n}, {y, 0, k}]*n!; t[0, 0] = t[1, 0] = 1; Table[t[n, k], {n, 0, max}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Jan 28 2014 *)

E.g.f.: exp(x*(1-y))/(1-x)^y. Binomial transform of triangle A008306. exp(x)*((-x-log(1-x))^k)/k! is e.g.f. of k-th column.
From Alois P. Heinz, Jul 13 2017: (Start)
T(2n,n) = A001147(n).
T(2n+1,n) = A051577(n) = (2*n+3)!!/3 = A001147(n+2)/3. (End)
From Alois P. Heinz, Aug 17 2023: (Start)
Sum_{k=0..floor(n/2)} k * T(n,k) = A001705(n-1) for n>=1.
Sum_{k=0..floor(n/2)} (-1)^k * T(n,k) = A159964(n-1) for n>=1. (End)

A111999 T(n, k) = [x^k] (-1)^nSum_{k=0..n} E2(n, n-k)(1+x)^(n-k) where E2(n, k) are the second-order Eulerian numbers. Triangle read by rows, T(n, k) for n >= 1 and 0 <= k <= n.

Original entry on oeis.org

-1, 3, 2, -15, -20, -6, 105, 210, 130, 24, -945, -2520, -2380, -924, -120, 10395, 34650, 44100, 26432, 7308, 720, -135135, -540540, -866250, -705320, -303660, -64224, -5040, 2027025, 9459450, 18288270, 18858840, 11098780, 3678840, 623376, 40320, -34459425, -183783600, -416215800

Offset: 1

Wolfdieter Lang, Sep 12 2005

Previous name was: A triangle that converts certain binomials into triangle A008276 (diagonals of signed Stirling1 triangle A008275).
Stirling1(n,n-m) = A008275(n,n-m) = Sum_{k=0..m-1}a(m,k)*binomial(n,2*m-k).
The unsigned column sequences start with A001147, A000906 = 2*A000457, 2*|A112000|, 4*|A112001|.
The general results on the convolution of the refined partition polynomials of A133932, with u_1 = 1 and u_n = -t otherwise, can be applied here to obtain results of convolutions of these unsigned polynomials. - Tom Copeland, Sep 20 2016

			Triangle starts:
  [1]      -1;
  [2]       3,       2;
  [3]     -15,     -20,       -6;
  [4]     105,     210,      130,       24;
  [5]    -945,   -2520,    -2380,     -924,     -120;
  [6]   10395,   34650,    44100,    26432,     7308,     720;
  [7] -135135, -540540,  -866250,  -705320,  -303660,  -64224,  -5040;
  [8] 2027025, 9459450, 18288270, 18858840, 11098780, 3678840, 623376, 40320.

Charles Jordan, Calculus of Finite Differences, Chelsea 1965, p. 152. Table C_{m, nu}.

Peter Bala, Diagonals of triangles with generating function exp(t*F(x)).
Steve Butler and Pavel Karasik, A note on nested sums, J. Int. Seq. 13 (2010), 10.4.4, page 4.
Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
Bishal Deb and Alan D. Sokal, Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness, arXiv:2507.18959 [math.CO], 2025. See p. 6.
EqWorld, Integral Transforms
David J. Jeffrey, G. A. Kalugin, N. Murdoch, Lagrange inversion and Lambert W, 17th Int'l Symp. Symb. Numer. Algor. Sci. Comp. (SYNASC 2015).
Wolfdieter Lang, First 10 rows.
Lajos Takács, On the number of distinct forests, SIAM J. Discrete Math., 3 (1990), 574-581. Table 3 gives an unsigned version of the triangle.

Row sums give A032188(m+1)*(-1)^m, m>=1. Unsigned row sums give A032188(m+1), m>=1.
Cf. A008517 (second-order Eulerian triangle) for a similar formula for |Stirling1(n, n-m)|.
Cf. A000457, A000906, A001147, A008275, A008276, A008306, A112001, A133932,

CoeffList := p -> op(PolynomialTools:-CoefficientList(p, x)):
E2 := (n, k) -> combinat[eulerian2](n, k):
poly := n -> (-1)^n*add(E2(n, n-k)*(1+x)^(n-k), k = 0..n):
seq(CoeffList(poly(n)), n = 1..8); # Peter Luschny, Feb 05 2021

a[m_, k_] := a[m, k] = Which[m < k + 1, 0, And[m == 1, k == 0], -1, k == -1, 0, True, -(2 m - k - 1)*(a[m - 1, k] + a[m - 1, k - 1])]; Table[a[m, k], {m, 9}, {k, 0, m - 1}] // Flatten (* Michael De Vlieger, Sep 23 2016 *)

a(m, k)=0 if m

From Tom Copeland, May 05 2010 (updated Sep 12 2011): (Start)

The integral from 0 to infinity w.r.t. w of

exp[-w(u+1)] (1+u*z*w)^(1/z) gives a power series, f(u,z), in z for reversed row polynomials in u of A111999, related to an Euler transform of diagonals of A008275.

Let g(u,x) be obtained from f(u,z) by replacing z^n with x^(n+1)/(n+1)!;

g(u,x)= x - u^2 x^2/2! + (2 u^3 + 3 u^4) x^3/3! - (6 u^4 + 20 u^5 + 15 u^6) x^4/4! + ... , an e.g.f. associated to f(u,z).

Then g^(-1)(u,x)=(1+u)*x - log(1+u*x) is the comp. inverse of g(u,x) in x, and, consequently, A133932 is a refinement of A111999.

With h(u,x)= 1/(dg^(-1)/dx)= (1+u*x)/(1+(1+u)*u*x),

g(u,x)=exp[x*h(u,t)d/dt] t, evaluated at t=0. Also, dg(u,x)/dx = h(u,g(u,x)). (End)

From Tom Copeland, May 06 2010: (Start)

For m,k>0, a(m,k) = Sum(j=2 to 2m-k+1): (-1)^(2m-k+1+j) C(2m-k+1,j) St1d(j,m),

where C(n,j) is the binomial coefficient and St1d(j,m) is the (j-m)-th element of the m-th subdiagonal of A008275 for (j-m)>0 and is 0 otherwise,

e.g., St1d(1,1) = 0, St1d(2,1) = -1, St1d(3,1) = -3, St1d(4,1) = -6. (End)

From Tom Copeland, Sep 03 2011 (updated Sep 12 2011): (Start)

The integral from 0 to infinity w.r.t. w of

exp[-w*(u+1)/u] (1+u*z*w)^(1/(u^2*z)) gives a power series, F(u,z), in z for the row polynomials in u of A111999.

Let G(u,x) be obtained from F(u,z) by replacing z^n with x^(n+1)/(n+1)!;

G(u,x) = x - x^2/2! + (3 + 2 u) x^3/3! - (15 + 20 u + 6 u^2) x^4/4! + ... , an e.g.f. for A111999 associated to F(u,z).

G^(-1)(u,x) = ((1+u)*u*x - log(1+u*x))/u^2 is the comp. inverse of G(u,x) in x.

With H(u,x) = 1/(dG^(-1)/dx) = (1+u*x)/(1+(1+u)*x),

G(u,x) = exp[x*H(u,t)d/dt] t, evaluated at t=0. Also, dG(u,x)/dx = H(u,G(u,x)). (End)

From Tom Copeland, Sep 16 2011: (Start)

f(u,z) and F(u,z) are expressible in terms of the incomplete gamma function Γ(v,p)(see Laplace Transforms for Power-law Functions at EqWorld):

With K(p,s) = p^(-s-1) exp(p) Γ(s+1,p),

f(u,z) = K(p,s)/(u*z) with p=(u+1)/(u*z) and s=1/z , and

F(u,z) = K(p,s)/(u*z) with p=(u+1)/(u^2*z) and s=1/(u^2*z). (End)

Diagonals of A008306 are reversed rows of A111999 (see P. Bala). - Tom Copeland, May 08 2012

New name from Peter Luschny, Feb 05 2021

A000276 Associated Stirling numbers.

Original entry on oeis.org

3, 20, 130, 924, 7308, 64224, 623376, 6636960, 76998240, 967524480, 13096736640, 190060335360, 2944310342400, 48503818137600, 846795372595200, 15618926924697600, 303517672703078400, 6198400928176128000, 132720966600284160000, 2973385109386137600000

Offset: 4

N. J. A. Sloane

nonn

a(n) is also the number of permutations of n elements, without any fixed point, with exactly two cycles. - Shanzhen Gao, Sep 15 2010

			a(4) = 3 because we have: (12)(34),(13)(24),(14)(23). - _Geoffrey Critzer_, Nov 03 2012

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 256.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 75.
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).
Shanzhen Gao, Permutations with Restricted Structure (in preparation).

Alois P. Heinz, Table of n, a(n) for n = 4..150

A diagonal of triangle in A008306.

Cf. A052518, A052881, A259456.

nn=25;a=Log[1/(1-x)]-x;Drop[Range[0,nn]!CoefficientList[Series[a^2/2,{x,0,nn}],x],4]  (* Geoffrey Critzer, Nov 03 2012 *)
a[n_] := (n-1)!*(HarmonicNumber[n-2]-1); Table[a[n], {n, 4, 23}] (* Jean-François Alcover, Feb 06 2016, after Gary Detlefs *)

a(n) = (n-1)!*sum(i=2, n-2, 1/i); \\ Michel Marcus, Feb 06 2016

a(n) = (n-1)!*Sum_{i=2..n-2} 1/i = (n-1)!*(Psi(n-1)+gamma-1). - Vladeta Jovovic, Aug 19 2003
With alternating signs: Ramanujan polynomials psi_3(n-2, x) evaluated at 1. - Ralf Stephan, Apr 16 2004
E.g.f.: ((x+log(1-x))^2)/2. [Corrected by Vladeta Jovovic, May 03 2008]
a(n) = Sum_{i=2..floor((n-1)/2)} n!/((n-i)*i) + Sum_{i=ceiling(n/2)..floor(n/2)} n!/(2*(n-i)*i). - Shanzhen Gao, Sep 15 2010
a(n) = (n+3)!*(h(n+2)-1), with offset 0, where h(n)=sum(1/k,k=1..n). - Gary Detlefs, Sep 11 2010
Conjecture: (-n+2)*a(n) +(n-1)*(2*n-5)*a(n-1) -(n-1)*(n-2)*(n-3)*a(n-2)=0. - R. J. Mathar, Jul 18 2015
Conjecture: a(n) +2*(-n+2)*a(n-1) +(n^2-6*n+10)*a(n-2) +(n-3)*(n-4)*a(n-3)=0. - R. J. Mathar, Jul 18 2015
a(n) = A000254(n-1) - (n-1)! - (n-2)!. - Anton Zakharov, Sep 24 2016

More terms from Christian G. Bower

A106828 Triangle T(n,k) read by rows: associated Stirling numbers of first kind (n >= 0 and 0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 0, 0, 1, 0, 2, 0, 6, 3, 0, 24, 20, 0, 120, 130, 15, 0, 720, 924, 210, 0, 5040, 7308, 2380, 105, 0, 40320, 64224, 26432, 2520, 0, 362880, 623376, 303660, 44100, 945, 0, 3628800, 6636960, 3678840, 705320, 34650, 0, 39916800, 76998240, 47324376, 11098780, 866250, 10395

Offset: 0

N. J. A. Sloane, May 22 2005

Another version of the triangle is in A008306.

A signed version of this triangle is given by the exponential Riordan array [1, log(1+t)-t]. Its row sums are (-1)^n*(1-n). Another version is [1, log(1-t)+t], whose row sums are 1-n. - Paul Barry, May 10 2008

			Rows 0 though 7 are:
  1;
  0,
  0,   1;
  0,   2,
  0,   6,   3;
  0,  24,  20,
  0, 120, 130,  15;
  0, 720, 924, 210;

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 256.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 75.

Reinhard Zumkeller, Rows n = 0..124 of table, flattened
Bishal Deb and Alan D. Sokal, Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness, arXiv:2507.18959 [math.CO], 2025. See pp. 5, 8.
Feng-Zhen Zhao, Some Properties of Associated Stirling Numbers, Journal of Integer Sequences, Article 08.1.7, 2008.

See A008306 for more information.

Cf. A008619 (row lengths), A000166 (row sums).

a106828 n k = a106828_tabf !! n !! k
a106828_row n = a106828_tabf !! n
a106828_tabf = map (fst . fst) $ iterate f (([1], [0]), 1) where
   f ((us, vs), x) =
     ((vs, map (* x) $ zipWith (+) ([0] ++ us) (vs ++ [0])), x + 1)
-- Reinhard Zumkeller, Aug 05 2013

A106828 := (n,k) -> add(binomial(j,n-2*k)*combinat:-eulerian2(n-k,j),j=0..n-k):
seq(print(seq(A106828(n,k),k=0..iquo(n,2))),n=0..9); # Peter Luschny, Apr 20 2011 (revised Jan 13 2016)
# Second program, after David Callan in A008306:
A106828 := proc(n, k) option remember; if k = 0 then k^n elif k = 1 then (n-1)! elif n <= 2*k-1 then 0 else (n-1)*(procname(n-1, k) + procname(n-2, k-1)) fi end: seq((seq(A106828(n, k), k = 0..iquo(n, 2))), n=0..12); # Peter Luschny, Aug 24 2021

Eulerian2[n_, k_] := Eulerian2[n, k] = If[k == 0, 1, If[k == n, 0, Eulerian2[n - 1, k] (k + 1) + Eulerian2[n - 1, k - 1] (2 n - k - 1)]];
T[n_, k_] := Sum[Binomial[j, n - 2 k] Eulerian2[n - k, j], {j, 0, n - k}];
Table[T[n, k], {n, 0, 12}, {k, 0, n/2}] (* Jean-François Alcover, Jun 13 2019 *)

E2(n, m) = sum(k=0, n-m, (-1)^(n+k)*binomial(2*n+1, k)*stirling(2*n-m-k+1, n-m-k+1, 1)); \\ A008517
T(n, k) = if ((n==0) && (k==0), 1, sum(j=0, n-k, binomial(j, n-2*k)*E2(n-k, j+1))); \\ Michel Marcus, Dec 07 2021

from math import factorial
def A106828(n, k):
    return k**n if k == 0 else factorial(n-1) if k == 1 else 0 if n <= 2*k - 1 else (n - 1)*(A106828(n-1, k) + A106828(n-2, k-1))
for n in range(14): print([A106828(n, k) for k in range(n//2 + 1)])
# Mélika Tebni, Dec 07 2021, after second Maple script.

# uses[bell_transform from A264428]
# Computes the full triangle 0<=k<=n.
def A106828_row(n):
    g = lambda k: factorial(k) if k>0 else 0
    s = [g(k) for k in (0..n)]
    return bell_transform(n, s)
[A106828_row(n) for n in (0..8)] # Peter Luschny, Jan 13 2016

T(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, j), where E2 are the second-order Eulerian numbers (A008517). - Peter Luschny, Jan 13 2016

Also the Bell transform of the sequence g(k) = k! if k>0 else 0. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 13 2016

Removed extra 0 in row 1 from Michael Somos, Jan 19 2011

A000483 Associated Stirling numbers: second-order reciprocal Stirling numbers (Fekete) a(n) = [[n, 3]]. The number of 3-orbit permutations of an n-set with at least 2 elements in each orbit.

Original entry on oeis.org

15, 210, 2380, 26432, 303660, 3678840, 47324376, 647536032, 9418945536, 145410580224, 2377609752960, 41082721413120, 748459539843840, 14345340443665920, 288650580508961280, 6085390148673177600, 134167064248901376000, 3088040233895705088000, 74077507611407752704000, 1849221425299053367296000

Offset: 6

N. J. A. Sloane

nonn

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 256.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 75.
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).

Alois P. Heinz, Table of n, a(n) for n = 6..200
A. E. Fekete, Apropos two notes on notation, Amer. Math. Monthly, 101 (1994), 771-778.

Cf. A000907, A001784, A001785. A diagonal of triangle in A008306.

Cf. A000276.

nn=25;a=Log[1/(1-x)]-x;Drop[Range[0,nn]!CoefficientList[Series[a^3/3!, {x,0,nn}],x],6]  (* Geoffrey Critzer, Nov 03 2012 *)

With alternating signs: Ramanujan polynomials psi_4(n-3, x) evaluated at 1. - Ralf Stephan, Apr 16 2004
E.g.f.: -((x+log(1-x))^3)/6. - Vladeta Jovovic, May 03 2008
Conjecture: (n-2)*(n-4)*a(n) -(n-1)*(3*n^2-21*n+35)*a(n-1) +(n-1)*(n-2)*(3*n^2-24*n+47)*a(n-2) -(n-5)*(n-1)*(n-2)*(n-3)*(n-4)*a(n-3)=0. - R. J. Mathar, Jul 18 2015
Conjecture: 3*(-n+4)*a(n) +(9*n^2-59*n+90)*a(n-1) +(-9*n^3+96*n^2-348*n+436)*a(n-2) +(n-3)*(3*n^3-45*n^2+237*n-430)*a(n-3) +5*(n-5)*(n-6)*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 18 2015

More terms from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 14 2000

More terms from Sean A. Irvine, Nov 14 2010

A235706 (I + A132440)^3: Coefficients for normalized generalized Laguerre polynomials n!*Lag(n, 3-n, -x).

Original entry on oeis.org

1, 3, 1, 6, 6, 1, 6, 18, 9, 1, 0, 24, 36, 12, 1, 0, 0, 60, 60, 15, 1, 0, 0, 0, 120, 90, 18, 1, 0, 0, 0, 0, 210, 126, 21, 1, 0, 0, 0, 0, 0, 336, 168, 24, 1, 0, 0, 0, 0, 0, 0, 504, 216, 27, 1, 0, 0, 0, 0, 0, 0, 0, 720, 270, 30, 1

Offset: 0

Tom Copeland, Apr 20 2014

The associated Laguerre polynomials n!*Lag(n,3-n,-x) are related to the rook polynomials of a rectangular 3 X n chessboard by R(3,n,x) = n!*x^n*Lag(n,3-n,-1/x), which are also the matching polynomials, or generating function of the number of k-edge matchings, of the complete bipartite graph K(m,n), or biclique (cf. Wikipedia for details).

The formulas here and below can be naturally extended with 3 replaced by any positive integer m. For m = 1 and 2, see unsigned A132013 and A132014. The formulas there can be extrapolated to apply to this matrix.

			Triangle begins:
  1;
  3,  1;
  6,  6,  1;
  6, 18,  9,  1;
  0, 24, 36, 12,  1;
  0,  0, 60, 60, 15, 1;
  ...

Michel Marcus, Rows n = 0..50 of triangle, flattened

Cf. A007318, A008306 for a generalization, A132013, A132014, A132440, A238363, A238385.
....................................
With 0th row: 1
n-th row: n!*Lag(n,3-n,-x)
....................................
1st: 1!*Lag(1,2,-x)  = A062139(1,k,-x)
2nd: 2!*Lag(2,1,-x)  = A105278(2,k,x)
3rd: 3!*Lag(3,0,-x)  = A021009(3,k,-x)
4th: 4!*Lag(4,-1,-x) = A111596(4,k,-x)
5th: 5!*Lag(5,-2,-x) = cf. x^2*A062139(3,k,x)
6th: 6!*Lag(6,-3,-x) = cf. x^3*A062137(3,k,-x)
....................................
n-th row: x^(n-3)*3!*Lag(3,n-3,-x)
....................................
1st: x^(-2)*3!Lag(3,-2,-x) = cf. x^(-2)*[x^2*A062139(1,k,x)]
2nd: x^(-1)*3!Lag(3,-1,-x) = x^(-1)*A111596(3,k,-x)
3rd: x^0*3!Lag(3,0,-x)     = x^0*A021009(3,k,-x)
4th: x^1*3!Lag(3,1,-x)     = x^1*A105278(3,k,x)
5th: x^2*3!Lag(3,2,-x)     = x^2*A062139(3,k,-x)
6th: x^3*3!Lag(3,3,-x)     = x^3*A062137(3,k,-x)

/* As triangle */ [[Binomial(3, n-k)*Factorial(n)/Factorial(k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jul 28 2017

Table[Binomial[3, n - k] n! / k!, {n, 0, 9}, {k, 0, n}]//Flatten (* Vincenzo Librandi, Jul 28 2017 *)

T(n,k) = binomial(3,n-k)*n!/k!
tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, Jul 28 2017

row(n) = Vecrev(n!*pollaguerre(n, 3-n, -x)); \\ Michel Marcus, Feb 06 2021

T(n,k) = binomial(3,n-k)*n!/k! = binomial(n,k)*3!/(3-n+k)!.
E.g.f.: exp(y*x)(1+y)^3, so this is an Appell sequence of polynomials with lowering operator L= D= d/dx and raising operator R = x + 3/(1+D).
E.g.f. of inverse matrix is exp(x*y)/(1+y)^3.
Multiply the n-th diagonal of the Pascal matrix A007318 by d(0)=1, d(1)=3, d(2)=6, d(3)=6, and d(n)=0 for n>3 to obtain T.
Row polynomials: n!*Lag(n,3-n,-x) = x^(n-3)*3!*Lag(3,n-3,-x) =
(3!/(3-n)!)*K(-n,3-n+1,-x) where K is Kummer's confluent hypergeometric function (as a limit of n+c as c tends to zero).
T = (I + A132440)^3 = exp[3*(A238385-I)]. I = identity matrix.
Operationally, n!Lag(n,3-n,-:xD:) = x^(n-3)*:Dx:^n*x^(3-n) = x^(-3)*:xD:^n*x^3 = n!*binomial(xD+3,n) = n!*binomial(3,n)*K(-n,3-n+1,-:xD:) where :AB:^n = A^n*B^n for any two operators.
n-th row polynomial: n!*Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*Lag(k,3,-x). - Peter Bala, Jul 25 2021

Showing 1-10 of 22 results. Next

cp's OEIS Frontend

A349479 Irregular triangle read by rows: T(n,k) = S1(n,k)*2^k, where S1(n,k) is the associated Stirling number of the first kind (cf. A008306) (n >= 0, 0 <= k <= floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A000166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

PARI

PARI

Python

Python

Formula

Extensions

A340556 E2(n, k), the second-order Eulerian numbers with E2(0, k) = δ_{0, k}. Triangle read by rows, E2(n, k) for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

SageMath

Formula

A032188 Number of labeled series-reduced mobiles (circular rooted trees) with n leaves (root has degree 0 or >= 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

A136394 Triangle read by rows: T(n,k) is the number of permutations of an n-set having k cycles of size > 1 (0<=k<=floor(n/2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A111999 T(n, k) = [x^k] (-1)^n*Sum_{k=0..n} E2(n, n-k)*(1+x)^(n-k) where E2(n, k) are the second-order Eulerian numbers. Triangle read by rows, T(n, k) for n >= 1 and 0 <= k <= n.

A111999 T(n, k) = [x^k] (-1)^nSum_{k=0..n} E2(n, n-k)(1+x)^(n-k) where E2(n, k) are the second-order Eulerian numbers. Triangle read by rows, T(n, k) for n >= 1 and 0 <= k <= n.