cp's OEIS Frontend

Triangle read by rows: T(n,k) (n>=2, k=1..n-1) is the number of topologies t on n points having exactly k+2 open sets such that t contains exactly one open set of size m for each m in {0,1,2,...,s,n} where s is the size of the largest proper open set in t. - N. J. A. Sloane, Jan 29 2016 [clarified by Geoffrey Critzer, Feb 19 2017]

If n and d are two nonnegative integers, and d <= n, then the number of permutations is obtained by the formula nPd = n!/(n-d)!.

Also number of labeled pointed rooted trees (or vertebrates) on n nodes.

For n >= 1 a(n) is also the number of n X n (0,1) matrices in which each row contains exactly one entry equal to 1. - Avi Peretz (njk(AT)netvision.net.il), Apr 21 2001

Also the number of labeled rooted trees on (n+1) nodes such that the root is lower than its children. Also the number of alternating labeled rooted ordered trees on (n+1) nodes such that the root is lower than its children. - Cedric Chauve (chauve(AT)lacim.uqam.ca), Mar 27 2002

With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i=1..p(n)} (n!/(Product_{j=1..p(i)} p(i, j)!)) * ((n!/(n - p(i)))!/(Product_{j=1..d(i)} m(i, j)!)). - Thomas Wieder, May 18 2005

All rational solutions to the equation x^y = y^x, with x < y, are given by x = A000169(n+1)/A000312(n), y = A000312(n+1)/A007778(n), where n = 1, 2, 3, ... . - Nick Hobson, Nov 30 2006

a(n) is the total number of leaves in all (n+1)^(n-1) trees on {0,1,2,...,n} rooted at 0. For example, with edges directed away from the root, the trees on {0,1,2} are {0->1,0->2},{0->1->2},{0->2->1} and contain a total of a(2)=4 leaves. - David Callan, Feb 01 2007

Limit_{n->infinity} A000169(n+1)/a(n) = exp(1). Convergence is slow, e.g., it takes n > 74 to get one decimal place correct and n > 163 to get two of them. - Alonso del Arte, Jun 20 2011

Also smallest k such that binomial(k, n) is divisible by n^(n-1), n > 0. - Michel Lagneau, Jul 29 2013

For n >= 2 a(n) is represented in base n as "one followed by n zeros". - R. J. Cano, Aug 22 2014

Number of length-n words over the alphabet of n letters. - Joerg Arndt, May 15 2015

Number of prime parking functions of length n+1. - Rui Duarte, Jul 27 2015

The probability density functions p(x, m=q, n=q, mu=1) = A000312(q)*E(x, q, q) and p(x, m=q, n=1, mu=q) = (A000312(q)/A000142(q-1))*x^(q-1)*E(x, q, 1), with q >= 1, lead to this sequence, see A163931, A274181 and A008276. - Johannes W. Meijer, Jun 17 2016

Satisfies Benford's law [Miller, 2015]. - N. J. A. Sloane, Feb 12 2017

A signed version of this sequence apart from the first term (1, -4, -27, 256, 3125, -46656, ...), has the following property: for every prime p == 1 (mod 2n), (-1)^(n(n-1)/2)*n^n = A057077(n)*a(n) is always a 2n-th power residue modulo p. - Jianing Song, Sep 05 2018

From Juhani Heino, May 07 2019: (Start)

n^n is both Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)

and Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)*i.

The former is the familiar binomial distribution of a throw of n n-sided dice, according to how many times a required side appears, 0 to n. The latter is the same but each term is multiplied by its amount. This means that if the bank pays the player 1 token for each die that has the chosen side, it is always a fair game if the player pays 1 token to enter - neither bank nor player wins on average.

Examples:

2-sided dice (2 coins): 4 = 1 + 2 + 1 = 1*0 + 2*1 + 1*2 (0 omitted from now on);

3-sided dice (3 long triangular prisms): 27 = 8 + 12 + 6 + 1 = 12*1 + 6*2 + 1*3;

4-sided dice (4 long square prisms or 4 tetrahedrons): 256 = 81 + 108 + 54 + 12 + 1 = 108*1 + 54*2 + 12*3 + 1*4;

5-sided dice (5 long pentagonal prisms): 3125 = 1024 + 1280 + 640 + 160 + 20 + 1 = 1280*1 + 640*2 + 160*3 + 20*4 + 1*5;

6-sided dice (6 cubes): 46656 = 15625 + 18750 + 9375 + 2500 + 375 + 30 + 1 = 18750*1 + 9375*2 + 2500*3 + 375*4 + 30*5 + 1*6.

(End)

For each n >= 1 there is a graph on a(n) vertices whose largest independent set has size n and whose independent set sequence is constant (specifically, for each k=1,2,...,n, the graph has n^n independent sets of size k). There is no graph of smaller order with this property (Ball et al. 2019). - David Galvin, Jun 13 2019

For n >= 2 and 1 <= k <= n, a(n)*(n + 1)/4 + a(n)*(k - 1)*(n + 1 - k)/2*n is equal to the sum over all words w = w(1)...w(n) of length n over the alphabet {1, 2, ..., n} of the following quantity: Sum_{i=1..w(k)} w(i). Inspired by Problem 12432 in the AMM (see links). - Sela Fried, Dec 10 2023

Also, dimension of the unique cohomology group of the smallest interval containing the poset of partitions decorated by Perm, i.e. the poset of pointed partitions. - Bérénice Delcroix-Oger, Jun 25 2025

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

Total number of permutations of all subsets of an n-set.

Also the number of one-to-one sequences that can be formed from n distinct objects.

Old name "Total number of permutations of a set with n elements", or the same with the word "arrangements", both sound too much like A000142.

Related to number of operations of addition and multiplication to evaluate a determinant of order n by cofactor expansion - see A026243.

a(n) is also the number of paths (without loops) in the complete graph on n+2 vertices starting at one vertex v1 and ending at another v2. Example: when n=2 there are 5 paths in the complete graph with 4 vertices starting at the vertex 1 and ending at the vertex 2: (12),(132),(142),(1342),(1432) so a(2) = 5. - Avi Peretz (njk(AT)netvision.net.il), Feb 23 2001; comment corrected by Jonathan Coxhead, Mar 21 2003

Also row sums of Table A008279, which can be generated by taking the derivatives of x^k. For example, for y = 1*x^3, y' = 3x^2, y" = 6x, y'''= 6 so a(4) = 1 + 3 + 6 + 6 = 16. - Alford Arnold, Dec 15 1999

a(n) is the permanent of the n X n matrix with 2s on the diagonal and 1s elsewhere. - Yuval Dekel, Nov 01 2003

(A000166 + this_sequence)/2 = A009179, (A000166 - this_sequence)/2 = A009628.

Stirling transform of A006252(n-1) = [1,1,1,2,4,14,38,...] is a(n-1) = [1,2,5,16,65,...]. - Michael Somos, Mar 04 2004

Number of {12,12*,21*}- and {12,12*,2*1}-avoiding signed permutations in the hyperoctahedral group.

a(n) = b such that Integral_{x=0..1} x^n*exp(-x) dx = a-b*exp(-1). - Sébastien Dumortier, Mar 05 2005

a(n) is the number of permutations on [n+1] whose left-to-right record lows all occur at the start. Example: a(2) counts all permutations on [3] except 231 (the last entry is a record low but its predecessor is not). - David Callan, Jul 20 2005

a(n) is the number of permutations on [n+1] that avoid the (scattered) pattern 1-2-3|. The vertical bar means the "3" must occur at the end of the permutation. For example, 21354 is not counted by a(4): 234 is an offending subpermutation. - David Callan, Nov 02 2005

Number of deco polyominoes of height n+1 having no reentrant corners along the lower contour (i.e., no vertical step that is followed by a horizontal step). In other words, a(n)=A121579(n+1,0). A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(1)=2 because the only deco polyominoes of height 2 are the vertical and horizontal dominoes, having no reentrant corners along their lower contours. - Emeric Deutsch, Aug 16 2006

Unreduced numerators of partial sums of the Taylor series for e. - Jonathan Sondow, Aug 18 2006

a(n) is the number of permutations on [n+1] (written in one-line notation) for which the subsequence beginning at 1 is increasing. Example: a(2)=5 counts 123, 213, 231, 312, 321. - David Callan, Oct 06 2006

a(n) is the number of permutations (written in one-line notation) on the set [n + k], k >= 1, for which the subsequence beginning at 1,2,...,k is increasing. Example: n = 2, k = 2. a(2) = 5 counts 1234, 3124, 3412, 4123, 4312. - Peter Bala, Jul 29 2014

a(n) and (1,-2,3,-4,5,-6,7,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Nov 01 2007

Consider the subsets of the set {1,2,3,...,n} formed by the first n integers. E.g., for n = 3 we have {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Let the variable sbst denote a subset. For each subset sbst we determine its number of parts, that is nprts(sbst). The sum over all possible subsets is written as Sum_{sbst=subsets}. Then a(n) = Sum_{sbst=subsets} nprts(sbst)!. E.g., for n = 3 we have 1!+1!+1!+1!+2!+2!+2!+3!=16. - Thomas Wieder, Jun 17 2006

Equals row sums of triangle A158359(unsigned). - Gary W. Adamson, Mar 17 2009

Equals eigensequence of triangle A158821. - Gary W. Adamson, Mar 30 2009

For positive n, equals 1/BarnesG(n+1) times the determinant of the n X n matrix whose (i,j)-coefficient is the (i+j)th Bell number. - John M. Campbell, Oct 03 2011

a(n) is the number of n X n binary matrices with i) at most one 1 in each row and column and ii) the subset of rows that contain a 1 must also be the columns that contain a 1. Cf. A002720 where restriction ii is removed. - Geoffrey Critzer, Dec 20 2011

Number of restricted growth strings (RGS) [d(1),d(2),...,d(n)] such that d(k) <= k and d(k) <= 1 + (number of nonzero digits in prefix). The positions of nonzero digits determine the subset, and their values (decreased by 1) are the (left) inversion table (a rising factorial number) for the permutation, see example. - Joerg Arndt, Dec 09 2012

Number of a restricted growth strings (RGS) [d(0), d(1), d(2), ..., d(n)] where d(k) >= 0 and d(k) <= 1 + chg([d(0), d(1), d(2), ..., d(k-1)]) and chg(.) gives the number of changes of its argument. Replacing the function chg(.) by a function asc(.) that counts the ascents in the prefix gives A022493 (ascent sequences). - Joerg Arndt, May 10 2013

The sequence t(n) = number of i <= n such that floor(e*i!) is a square is mentioned in the abstract of Luca & Shparlinski. The values are t(n) = 0 for 0 <= n <= 2 and t(n) = 1 for at least 3 <= n <= 300. - R. J. Mathar, Jan 16 2014

a(n) = p(n,1) = q(n,1), where p and q are polynomials defined at A248664 and A248669. - Clark Kimberling, Oct 11 2014

a(n) is the number of ways at most n people can queue up at a (slow) ticket counter when one or more of the people may choose not to queue up. Note that there are C(n,k) sets of k people who quene up and k! ways to queue up. Since k can run from 0 to n, a(n) = Sum_{k=0..n} n!/(n-k)! = Sum_{k=0..n} n!/k!. For example, if n=3 and the people are A(dam), B(eth), and C(arl), a(3)=16 since there are 16 possible lineups: ABC, ACB, BAC, BCA, CAB, CBA, AB, BA, AC, CA, BC, CB, A, B, C, and empty queue. - Dennis P. Walsh, Oct 02 2015

As the row sums of A008279, Motzkin uses the abbreviated notation $n_<^\Sigma$ for a(n).

The piecewise polynomial function f defined by f(x) = a(n)*x^n/n! on each interval [ 1-1/a(n), 1-1/a(n+1) ) is continuous on [0,1) and lim_{x->1} f(x) = e. - Luc Rousseau, Oct 15 2019

a(n) is composite for 3 <= n <= 2015, but a(2016) is prime (or at least a strong pseudoprime): see Johansson link. - Robert Israel, Jul 27 2020 [a(2016) is prime, ECPP certificate generated with CM 0.4.3 and checked by factordb. - Jason H Parker, Jun 15 2025]

In general, sequences of the form a(0)=a, a(n) = n*a(n-1) + k, n>0, will have a closed form of n!*a + floor(n!*(e-1))*k. - Gary Detlefs, Oct 26 2020

From Peter Bala, Apr 03 2022: (Start)

a(2*n) is odd and a(2*n+1) is even. More generally, a(n+k) == a(n) (mod k) for all n and k. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with the exact period dividing k. Various divisibility properties of the sequence follow from this; for example, a(5*n+2) == a(5*n+4) == 0 (mod 5), a(25*n+7) == a(25*n+19) == 0 (mod 25) and a(13*n+4) == a(13*n+10)== a(13*n+12) == 0 (mod 13). (End)

Number of possible ranking options on a typical ranked choice voting ballot with n candidates (allowing undervotes). - P. Christopher Staecker, May 05 2024

From Thomas Scheuerle, Dec 28 2024: (Start)

Number of decorated permutations of size n.

Number of Le-diagrams with bounding box semiperimeter n, for n > 0.

By counting over all k = 1..n and n > 0, the number of positroid cells for the totally nonnegative real Grassmannian Gr(k, n), equivalently the number of Grassmann necklaces of type (k, n). (End)

Number of ways n labeled objects can be distributed into k nonempty parcels. Also number of special terms in n variables with maximal degree k.

In older terminology these are called differences of 0. - Michael Somos, Oct 08 2003

Number of surjections (onto functions) from an n-element set to a k-element set.

Also coefficients (in ascending order) of so-called ordered Bell polynomials.

(k-1)!*Stirling2(n,k-1) is the number of chain topologies on an n-set having k open sets [Stephen].

Number of set compositions (ordered set partitions) of n items into k parts. Number of k dimensional 'faces' of the n dimensional permutohedron (see Simion, p. 162). - Mitch Harris, Jan 16 2007

Correction of comment before: Number of (n-k)-dimensional 'faces' of the permutohedron of order n (an (n-1)-dimensional polytope). - Tilman Piesk, Oct 29 2014

This array is related to the reciprocal of an e.g.f. as sketched in A133314. For example, the coefficient of the fourth-order term in the Taylor series expansion of 1/(a(0) + a(1) x + a(2) x^2/2! + a(3) x^3/3! + ...) is a(0)^(-5) * {24 a(1)^4 - 36 a(1)^2 a(2) a(0) + [8 a(1) a(3) + 6 a(2)^2] a(0)^2 - a(4) a(0)^3}. The unsigned coefficients characterize the P3 permutohedron depicted on page 10 in the Loday link with 24 vertices (0-D faces), 36 edges (1-D faces), 6 squares (2-D faces), 8 hexagons (2-D faces) and 1 3-D permutohedron. Summing coefficients over like dimensions gives A019538 and A090582. Compare to A133437 for the associahedron. - Tom Copeland, Sep 29 2008, Oct 07 2008

Further to the comments of Tom Copeland above, the permutohedron of type A_3 can be taken as the truncated octahedron. Its dual is the tetrakis hexahedron, a simplicial polyhedron, with f-vector (1,14,36,24) giving the fourth row of this triangle. See the Wikipedia entry and [Fomin and Reading p. 21]. The corresponding h-vectors of permutohedra of type A give the rows of the triangle of Eulerian numbers A008292. See A145901 and A145902 for the array of f-vectors for type B and type D permutohedra respectively. - Peter Bala, Oct 26 2008

Subtriangle of triangle in A131689. - Philippe Deléham, Nov 03 2008

Since T(n,k) counts surjective functions and surjective functions are "consistent", T(n,k) satisfies a binomial identity, namely, T(n,x+y) = Sum_{j=0..n} C(n,j)*T(j,x)*T(n-j,y). For definition of consistent functions and a generalized binomial identity, see "Toy stories and combinatorial identities" in the link section below. - Dennis P. Walsh, Feb 24 2012

T(n,k) is the number of labeled forests on n+k vertices satisfying the following two conditions: (i) each forest consists of exactly k rooted trees with roots labeled 1, 2, ..., k; (ii) every root has at least one child vertex. - Dennis P. Walsh, Feb 24 2012

The triangle is the inverse binomial transform of triangle A028246, deleting the left column and shifting up one row. - Gary W. Adamson, Mar 05 2012

See A074909 for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014

E.g.f. for the shifted signed polynomials is G(x,t) = (e^t-1)/[1+(1+x)(e^t-1)] = 1-(1+x)(e^t-1) + (1+x)^2(e^t-1)^2 - ... (see also A008292 and A074909), which has the infinitesimal generator g(x,u)d/du = [(1-x*u)(1-(1+x)u)]d/du, i.e., exp[t*g(x,u)d/du]u eval. at u=0 gives G(x,t), and dG(x,t)/dt = g(x,G(x,t)). The compositional inverse is log((1-xt)/(1-(1+x)t)). G(x,t) is a generating series associated to the generalized Hirzebruch genera. See the G. Rzadowski link for the relation of the derivatives of g(x,u) to solutions of the Riccatt differential equation, soliton solns. to the KdV equation, and the Eulerian and Bernoulli numbers. In addition A145271 connects products of derivatives of g(x,u) and the refined Eulerian numbers to the inverse of G(x,t), which gives the normalized, reverse face polynomials of the simplices (A135278, divided by n+1). See A028246 for the generator g(x,u)d/dx. - Tom Copeland, Nov 21 2014

For connections to toric varieties and Eulerian polynomials, see the Dolgachev and Lunts and the Stembridge links. - Tom Copeland, Dec 31 2015

See A008279 for a relation between the e.g.f.s enumerating the faces of permutahedra (this entry) and stellahedra. - Tom Copeland, Nov 14 2016

T(n, k) appears in a Worpitzky identity relating monomials to binomials: x^n = Sum_{k=1..n} T(n, k)*binomial(x,k), n >= 1. See eq. (11.) of the Worpitzky link on p. 209. The relation to the Eulerian numbers is given there in eqs. (14.) and (15.). See the formula below relating to A008292. See also Graham et al. eq. (6.10) (relating monomials to falling factorials) on p. 248 (2nd ed. p. 262). The Worpitzky identity given in the Graham et al. reference as eq. (6.37) (2nd ed. p. 269) is eq. (5.), p. 207, of Worpitzky. - Wolfdieter Lang, Mar 10 2017

T(n, m) is also the number of minimum clique coverings and minimum matchings in the complete bipartite graph K_{m,n}. - Eric W. Weisstein, Apr 26 2017

From the Hasan and Franco and Hasan papers: The m-permutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5-cell. The first three are well-known from the study of elliptic models, brane tilings and brane brick models. The m+1 torus can be tiled by a single (m+2)-permutohedron. Relations to toric Calabi-Yau Kahler manifolds are also discussed. - Tom Copeland, May 14 2020

From Manfred Boergens, Jul 25 2021: (Start)

Number of n X k binary matrices with row sums = 1 and no zero columns. These matrices are a subset of the matrices defining A183109.

The distribution into parcels in the leading comment can be regarded as a covering of [n] by tuples (A_1,...,A_k) in P([n])^k with nonempty and disjoint A_j, with P(.) denoting the power set (corrected for clarity by Manfred Boergens, May 26 2024). For the non-disjoint case see A183109 and A218695.

For tuples with "nonempty" dropped see A089072. For tuples with "nonempty and disjoint" dropped see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). (End)

This triangle is an unsigned version of the triangle of Stirling numbers of the first kind, A008275, which is the main entry for these numbers. - N. J. A. Sloane, Jan 25 2011

Or, triangle T(n,k), 0 <= k <= n, read by rows given by [1,1,2,2,3,3,4,4,5,5,6,6,...] DELTA [1,0,1,0,1,0,1,0,1,0,1,0,...] where DELTA is the operator defined in A084938.

Reversal of A094638.

Equals A132393*A007318, as infinite lower triangular matrices. - Philippe Deléham, Nov 13 2007

From Johannes W. Meijer, Oct 07 2009: (Start)

The higher order exponential integrals E(x,m,n) are defined in A163931. The asymptotic expansion of the exponential integrals E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + n*(n+1)/x^2 - n*(n+1)*(n+2)/x^3 + ...), see Abramowitz and Stegun. This formula follows from the general formula for the asymptotic expansion, see A163932. We rewrite E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) and observe that the T(n,m) are the polynomials coefficients in the denominators. Looking at the a(n,m) formula of A028421, A163932 and A163934, and shifting the offset given above to 1, we can write T(n-1,m-1) = a(n,m) = (-1)^(n+m)*Stirling1(n,m), see the Maple program.

The asymptotic expansion leads for values of n from one to eleven to known sequences, see the cross-references. With these sequences one can form the triangles A008279 (right-hand columns) and A094587 (left-hand columns).

See A163936 for information about the o.g.f.s. of the right-hand columns of this triangle.

(End)

The number of elements greater than i to the left of i in a permutation gives the i-th element of the inversion vector. (Skiena-Pemmaraju 2003, p. 69.) T(n,k) is the number of n-permutations that have exactly k 0's in their inversion vector. See evidence in Mathematica code below. - Geoffrey Critzer, May 07 2010

T(n,k) counts the rooted trees with k+1 trunks in forests of "naturally grown" rooted trees with n+2 nodes. This corresponds to sums of coefficients of iterated derivatives representing vectors, Lie derivatives, or infinitesimal generators for flow fields and formal group laws. Cf. links in A139605. - Tom Copeland, Mar 23 2014

A refinement is A036039. - Tom Copeland, Mar 30 2014

From Tom Copeland, Apr 05 2014: (Start)

With initial n=1 and row polynomials of T as p(n,x)=x(x+1)...(x+n-1), the powers of x correspond to the number of trunks of the rooted trees of the "naturally-grown" forest referred to above. With each trunk allowed m colors, p(n,m) gives the number of such non-plane colored trees for the forest with each tree having n+1 vertices.

p(2,m) = m + m^2 = A002378(m) = 2*A000217(m) = 2*(first subdiag of |A238363|).

p(3,m) = 2m + 3m^2 + m^3 = A007531(m+2) = 3*A007290(m+2) = 3*(second subdiag A238363).

p(4,m) = 6m + 11m^2 + 6m^3 + m^4 = A052762(m+3) = 4*A033487(m) = 4*(third subdiag).

From the Joni et al. link, p(n,m) also represents the disposition of n distinguishable flags on m distinguishable flagpoles.

The chromatic polynomial for the complete graph K_n is the falling factorial, which encodes the colorings of the n vertices of K_n and gives a shifted version of p(n,m).

E.g.f. for the row polynomials: (1-y)^(-x).

(End)

A relation to derivatives of the determinant |V(n)| of the n X n Vandermonde matrix V(n) in the indeterminates c(1) thru c(n):

|V(n)| = Product_{1<=jTom Copeland, Apr 10 2014

From Peter Bala, Jul 21 2014: (Start)

Let M denote the lower unit triangular array A094587 and for k = 0,1,2,... define M(k) to be the lower unit triangular block array

/I_k 0\

\ 0 M/

having the k X k identity matrix I_k as the upper left block; in particular, M(0) = M. Then the present triangle equals the infinite matrix product M(0)*M(1)*M(2)*... (which is clearly well defined). See the Example section. (End)

For the relation of this rising factorial to the moments of Viennot's Laguerre stories, see the Hetyei link, p. 4. - Tom Copeland, Oct 01 2015

Can also be seen as the Bell transform of n! without column 0 (and shifted enumeration). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}. Some early references to this sequence are Izquierdo (1659), Caramuel de Lobkowitz (1670), Prestet (1675) and Bernoulli (1713). - Don Knuth, Oct 16 2001, Aug 16 2004

Stirling transform of A006252(n-1) = [0,1,1,2,4,14,38,...] is a(n-1) = [0,1,4,15,64,...]. - Michael Somos, Mar 04 2004

In particular, for n >= 1 a(n) is the number of nonempty sequences with n or fewer terms, each a distinct element of {1,...,n}. - Rick L. Shepherd, Jun 08 2005

a(n) = VarScheme(1,n). See A128195 for the definition of VarScheme(k,n). - Peter Luschny, Feb 26 2007

if s(n) is a sequence of the form s(0)=x, s(n)= n(s(n-1)+k), then s(n)= n!*x + a(n)*k. - Gary Detlefs, Jun 06 2010

Exponential convolution of factorials (A000142) and nonnegative integers (A001477). - Vladimir Reshetnikov, Oct 07 2016

For n > 0, a(n) is the number of maps f: {1,...,n} -> {1,...,n} satisfying equal(x,y) <= equal(f(x),f(y)) for all x,y, where equal(x,y) is n if x and y are equal and min(x,y) if not. Here equal(x,y) is the equality predicate in the n-valued Gödel logic, see e. g. the Wikipedia chapter on many-valued logics. - Mamuka Jibladze, Mar 12 2025

Also, table of Pochhammer sequences read by antidiagonals (see Rudolph-Lilith, 2015). - N. J. A. Sloane, Mar 31 2016

Reverse of A008279. Row sums are A000522. Diagonal sums are A003470. Rows of inverse matrix begin {1}, {-1,1}, {0,-2,1}, {0,0,-3,1}, {0,0,0,-4,1} ... The signed lower triangular matrix (-1)^(n+k)n!/k! has as row sums the signed rencontres numbers Sum_{k=0..n} (-1)^(n+k)n!/k!. (See A000166). It has matrix inverse 1 1,1 0,2,1 0,0,3,1 0,0,0,4,1,...

Exponential Riordan array [1/(1-x),x]; column k has e.g.f. x^k/(1-x). - Paul Barry, Mar 27 2007

From Tom Copeland, Nov 01 2007: (Start)

T is the umbral extension of n!*Lag[n,(.)!*Lag[.,x,-1],0] = (1-D)^(-1) x^n = (-1)^n * n! * Lag(n,x,-1-n) = Sum_{j=0..n} binomial(n,j) * j! * x^(n-j) = Sum_{j=0..n} (n!/j!) x^j. The inverse operator is A132013 with generalizations discussed in A132014.

b = T*a can be characterized several ways in terms of a(n) and b(n) or their o.g.f.'s A(x) and B(x).

1) b(n) = n! Lag[n,(.)!*Lag[.,a(.),-1],0], umbrally,

2) b(n) = (-1)^n n! Lag(n,a(.),-1-n)

3) b(n) = Sum_{j=0..n} (n!/j!) a(j)

4) B(x) = (1-xDx)^(-1) A(x), formally

5) B(x) = Sum_{j=0,1,...} (xDx)^j A(x)

6) B(x) = Sum_{j=0,1,...} x^j * D^j * x^j A(x)

7) B(x) = Sum_{j=0,1,...} j! * x^j * L(j,-:xD:,0) A(x) where Lag(n,x,m) are the Laguerre polynomials of order m, D the derivative w.r.t. x and (:xD:)^j = x^j * D^j. Truncating the operator series at the j = n term gives an o.g.f. for b(0) through b(n).

c = (0!,1!,2!,3!,4!,...) is the sequence associated to T under the list partition transform and the associated operations described in A133314 so T(n,k) = binomial(n,k)*c(n-k). The reciprocal sequence is d = (1,-1,0,0,0,...). (End)

From Peter Bala, Jul 10 2008: (Start)

This array is the particular case P(1,1) of the generalized Pascal triangle P(a,b), a lower unit triangular matrix, shown below:

n\k|0.....................1...............2.......3......4

----------------------------------------------------------

0..|1.....................................................

1..|a....................1................................

2..|a(a+b)...............2a..............1................

3..|a(a+b)(a+2b).........3a(a+b).........3a........1......

4..|a(a+b)(a+2b)(a+3b)...4a(a+b)(a+2b)...6a(a+b)...4a....1

...

The entries A(n,k) of this array satisfy the recursion A(n,k) = (a+b*(n-k-1))*A(n-1,k) + A(n-1,k-1), which reduces to the Pascal formula when a = 1, b = 0.

Various cases are recorded in the database, including: P(1,0) = Pascal's triangle A007318, P(2,0) = A038207, P(3,0) = A027465, P(2,1) = A132159, P(1,3) = A136215 and P(2,3) = A136216.

When b <> 0 the array P(a,b) has e.g.f. exp(x*y)/(1-b*y)^(a/b) = 1 + (a+x)*y + (a*(a+b)+2a*x+x^2)*y^2/2! + (a*(a+b)*(a+2b) + 3a*(a+b)*x + 3a*x^2+x^3)*y^3/3! + ...; the array P(a,0) has e.g.f. exp((x+a)*y).

We have the matrix identities P(a,b)*P(a',b) = P(a+a',b); P(a,b)^-1 = P(-a,b).

An analog of the binomial expansion for the row entries of P(a,b) has been proved by [Echi]. Introduce a (generally noncommutative and nonassociative) product ** on the ring of polynomials in two variables by defining F(x,y)**G(x,y) = F(x,y)G(x,y) + by^2*d/dy(G(x,y)).

Define the iterated product F^(n)(x,y) of a polynomial F(x,y) by setting F^(1) = F(x,y) and F^(n)(x,y) = F(x,y)**F^(n-1)(x,y) for n >= 2. Then (x+a*y)^(n) = x^n + C(n,1)*a*x^(n-1)*y + C(n,2)*a*(a+b)*x^(n-2)*y^2 + ... + C(n,n)*a*(a+b)*(a+2b)*...*(a+(n-1)b)*y^n. (End)

(n+1) * n-th row = reversal of triangle A068424: (1; 2,2; 6,6,3; ...) - Gary W. Adamson, May 03 2009

Let G(m, k, p) = (-p)^k*Product_{j=0..k-1}(j - m - 1/p) and T(n,k,p) = G(n-1,n-k,p) then T(n, k, 1) is this sequence, T(n, k, 2) = A112292(n, k) and T(n, k, 3) = A136214. - Peter Luschny, Jun 01 2009, revised Jun 18 2019

The higher order exponential integrals E(x,m,n) are defined in A163931. For a discussion of the asymptotic expansions of the E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) see A130534. The asymptotic expansion of E(x,m=1,n) leads for n >= 1 to the left hand columns of the triangle given above. Triangle A165674 is generated by the asymptotic expansions of E(x,m=2,n). - Johannes W. Meijer, Oct 07 2009

T(n,k) = n!/k! = number of permutations of [n+1] with exactly k+1 cycles and with elements 1,2,...,k+1 in separate cycles. See link and example below. - Dennis P. Walsh, Jan 24 2011

T(n,k) is the number of n permutations that leave some size k subset of {1,2,...,n} fixed. Sum_{k=0..n}(-1)^k*T(n,k) = A000166(n) (the derangements). - Geoffrey Critzer, Dec 11 2011

T(n,k) = A162995(n-1,k-1), 2 <= k <= n; T(n,k) = A173333(n,k), 1 <= k <= n. - Reinhard Zumkeller, Jul 05 2012

The row polynomials form an Appell sequence. The matrix is a special case of a group of general matrices sketched in A132382. - Tom Copeland, Dec 03 2013

For interpretations in terms of colored necklaces, see A213936 and A173333. - Tom Copeland, Aug 18 2016

See A008279 for a relation of this entry to the e.g.f.s enumerating the faces of permutahedra and stellahedra. - Tom Copeland, Nov 14 2016

Also, T(n,k) is the number of ways to arrange n-k nonattacking rooks on the n X (n-k) chessboard. - Andrey Zabolotskiy, Dec 16 2016

The infinitesimal generator of this triangle is the generalized exponential Riordan array [-log(1-x), x] and equals the unsigned version of A238363. - Peter Bala, Feb 13 2017

Formulas for exponential and power series infinitesimal generators for this triangle T are given in Copeland's 2012 and 2014 formulas as T = unsigned exp[(I-A238385)] = 1/(I - A132440), where I is the identity matrix. - Tom Copeland, Jul 03 2017

If A(0) = 1/(1-x), and A(n) = d/dx(A(n-1)), then A(n) = n!/(1-x)^(n+1) = Sum_{k>=0} (n+k)!/k!*x^k = Sum_{k>=0} T(n+k, k)*x^k. - Michael Somos, Sep 19 2021

Triangle in which the n-th row begins with n and the k-th term is obtained by multiplying the (k-1)-th term by (n-k+1) until n-k+1 = 1. - Amarnath Murthy, Nov 11 2002

Has many diagonals in common with A105725. - Zerinvary Lajos, Apr 14 2006

Also: the square array of rising factorials A(n,k) = n*(n+1)*(n+2)*...*(n+k-1) read by antidiagonals downwards. There are no perfect squares in T(n,k) for k >= 2 [see Rigge]. T(n,k) is divisible by a prime exceeding k, if n >= 2*k [see Saradha and Shorey]. - R. J. Mathar, May 02 2007

T(n,k) is the number of injective functions f from {1,...,k} into {1,...,n}, since there are n choices for f(1), then (n-1) choices for f(2), ... and (n-k+1) choices for f(k). E.g., T(3,2)=6 because there are exactly 6 injective functions f:{1,2}->{1,2,3}, namely, f1={(1,1),(2,2)}, f2={(1,1),(2,3)}, f3={(1,2),(2,1)}, f4={(1,2),(2,3)}, f5={(1,3),(2,1)} and f6={(1,3),(2,2)}. - Dennis P. Walsh, Oct 18 2007

Permuted words defined by the connectivity of regular simplices are related to T by T = A135278 * (1!, 2!, 3!, 4!, ...). E.g., for T(4,k) with k-1 = simplex number, label the vertices of a tetrahedron with a, b, c, d, then the 0-simplex, the points, a,b,c,d gives 4 * 1 = 4 words; the 1-simplex, the edges: (ab or ba), (ac or ca), (ad or da), (bc or cb), (bd or db), (cd or dc) gives 6 * 2 = 12 words; the 2-simplex, the faces: (abc or ...), (acd or ...), (adb or ...), (bcd or ...) gives 4 * 6 = 24 words; the 3-simplex, (abcd or ....) gives 1 * 24 = 24 words. - Tom Copeland, Dec 08 2007

Reversal of the triangle by rows = (n+1) * n-th row of triangle A094587. - Gary W. Adamson, May 03 2009

From Geoffrey Critzer, May 06 2009: (Start)

The rectangular array R(n,k), read by diagonals is the number of ways n people can queue up in k (possibly empty) distinct queues. R(n,k) = (n+k-1)!/(k-1)!; R(n,k) = (n+k-1)*R(n-1,k).

Northwest corner:

1, 2, 3, 4, 5, ...;

2, 6, 12, 20, 30, ...;

6, 24, 60, 120, 210, ...;

24, 120, 360, 840, 1680, ...;

120, 720, 2520, 6720, 15120, ...;

...

Example: R(2,2)=6 because there are six ways that two people can get in line at a fast food restaurant that has two order windows open. Let 1 and 2 represent the two people and a | will separate the lines. 12|; 21|; |12; |21; 1|2; 2|1. (End)

Cf. [Hardy and Wright], Theorem 34.

The e.g.f. of the Norlund generalized Bernoulli (Appell) polynomials of order m, NB(n,x;m), is given by exponentiation of the e.g.f. of the Bernoulli numbers, i.e., multiple binomial self-convolutions of the Bernoulli numbers, through the e.g.f. exp[NB(.,x;m)t] = [t/(e^t-1)]^(m+1) * e^(xt). Norlund gave the relation to the factorials (x-1)!/(x-1-k)! = (x-1) ... (x-k) = NB(k,x;k), so T(n,k) = NB(k,n+1;k). - Tom Copeland, Oct 01 2015

T(n,k) is the number of sequences without repetition (partial permutations) of k elements taken from an n-set. For sequences with repetition (k-tuples) cf. A075363. - Manfred Boergens, Jun 18 2023