cp's OEIS Frontend

For n >= 3, a(n-1) is also the number of ways that a 3-cycle in the symmetric group S_n can be written as a product of 2 long cycles (of length n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 14 2001

a(n) is the number of Hamiltonian circuit masks for an n X n adjacency matrix of an undirected graph. - Chad Brewbaker, Jan 31 2003

a(n-1) is the number of necklaces one can make with n distinct beads: n! bead permutations, divide by two to represent flipping the necklace over, divide by n to represent rotating the necklace. Related to Stirling numbers of the first kind, Stirling cycles. - Chad Brewbaker, Jan 31 2003

Number of increasing runs in all permutations of [n-1] (n>=2). Example: a(4)=12 because we have 12 increasing runs in all the permutations of [3] (shown in parentheses): (123), (13)(2), (3)(12), (2)(13), (23)(1), (3)(2)(1). - Emeric Deutsch, Aug 28 2004

Minimum permanent over all n X n (0,1)-matrices with exactly n/2 zeros. - Simone Severini, Oct 15 2004

The number of permutations of 1..n that have 2 following 1 for n >= 1 is 0, 1, 3, 12, 60, 360, 2520, 20160, ... . - Jon Perry, Sep 20 2008

Starting (1, 3, 12, 60, ...) = binomial transform of A000153: (1, 2, 7, 32, 181, ...). - Gary W. Adamson, Dec 25 2008

First column of A092582. - Mats Granvik, Feb 08 2009

The asymptotic expansion of the higher order exponential integral E(x,m=1,n=3) ~ exp(-x)/x*(1 - 3/x + 12/x^2 - 60/x^3 + 360/x^4 - 2520/x^5 + 20160/x^6 - 81440/x^7 + ...) leads to the sequence given above. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009

For n>1: a(n) = A173333(n,2). - Reinhard Zumkeller, Feb 19 2010

Starting (1, 3, 12, 60, ...) = eigensequence of triangle A002260, (a triangle with k terms of (1,2,3,...) in each row given k=1,2,3,...). Example: a(6) = 360, generated from (1, 2, 3, 4, 5) dot (1, 1, 3, 12, 60) = (1 + 2 + 9 + 48 + 300). - Gary W. Adamson, Aug 02 2010

For n>=2: a(n) is the number of connected 2-regular labeled graphs on (n+1) nodes (Cf. A001205). - Geoffrey Critzer, Feb 16 2011.

The Fi1 and Fi2 triangle sums of A094638 are given by the terms of this sequence (n>=1). For the definition of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011

Also [1, 1] together with the row sums of triangle A162608. - Omar E. Pol, Mar 09 2012

a(n-1) is, for n>=2, also the number of necklaces with n beads (only C_n symmetry, no turnover) with n-1 distinct colors and signature c[.]^2 c[.]^(n-2). This means that two beads have the same color, and for n=2 the second factor is omitted. Say, cyclic(c[1]c[1]c[2]c[3]..c[n-1]), in short 1123...(n-1), taken cyclically. E.g., n=2: 11, n=3: 112, n=4: 1123, 1132, 1213, n=5: 11234, 11243, 11324, 11342, 11423, 11432, 12134, 12143, 13124, 13142, 14123, 14132. See the next-to-last entry in line n>=2 of the representative necklace partition array A212359. - Wolfdieter Lang, Jun 26 2012

For m >= 3, a(m-1) is the number of distinct Hamiltonian circuits in a complete simple graph with m vertices. See also A001286. - Stanislav Sykora, May 10 2014

In factorial base (A007623) these numbers have a simple pattern: 1, 1, 1, 11, 200, 2200, 30000, 330000, 4000000, 44000000, 500000000, 5500000000, 60000000000, 660000000000, 7000000000000, 77000000000000, 800000000000000, 8800000000000000, 90000000000000000, 990000000000000000, etc. See also the formula based on this observation, given below. - Antti Karttunen, Dec 19 2015

Also (by definition) the independence number of the n-transposition graph. - Eric W. Weisstein, May 21 2017

Number of permutations of n letters containing an even number of even cycles. - Michael Somos, Jul 11 2018

Equivalent to Brewbaker's and Sykora's comments, a(n - 1) is the number of undirected cycles covering n labeled vertices, hence the logarithmic transform of A002135. - Gus Wiseman, Oct 20 2018

For n >= 2 and a set of n distinct leaf labels, a(n) is the number of binary, rooted, leaf-labeled tree topologies that have a caterpillar shape (column k=1 of A306364). - Noah A Rosenberg, Feb 11 2019

Also the clique covering number of the n-Bruhat graph. - Eric W. Weisstein, Apr 19 2019

a(n) is the number of lattices of the form [s,w] in the weak order on S_n, for a fixed simple reflection s. - Bridget Tenner, Jan 16 2020

For n > 3, a(n) = p_1^e_1*...*p_m^e_m, where p_1 = 2 and e_m = 1. There exists p_1^x where x <= e_1 such that p_1^x*p_m^e_m is a primitive Zumkeller number (A180332) and p_1^e_1*p_m^e_m is a Zumkeller number (A083207). Therefore, for n > 3, a(n) = p_1^e_1*p_m^e_m*r, where r is relatively prime to p_1*p_m, is also a Zumkeller number. - Ivan N. Ianakiev, Mar 11 2020

For n>1, a(n) is the number of permutations of [n] that have 1 and 2 as cycle-mates, that is, 1 and 2 are contained in the same cycle of a cyclic representation of permutations of [n]. For example, a(4) counts the 12 permutations with 1 and 2 as cycle-mates, namely, (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2 3) (4), (1 3 2) (4), (1 2 4 )(3), (1 4 2)(3), (1 2)(3 4), and (1 2)(3)(4). Since a(n+2)=row sums of A162608, our result readily follows. - Dennis P. Walsh, May 28 2020

This is the case r = 2 of the r-Stirling numbers of the second kind. The 2-Stirling numbers of the second kind give the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the elements 1 and 2 belong to distinct subsets.

More generally, the r-Stirling numbers of the second kind give the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the numbers 1, 2, ..., r belong to distinct subsets. The case r = 1 gives the usual Stirling numbers of the second kind A008277; for other cases see A143495 (r = 3) and A143496 (r = 4).

The lower unitriangular array of r-Stirling numbers of the second kind equals the matrix product P^(r-1) * S (with suitable offsets in the row and column indexing), where P is Pascal's triangle, A007318 and S is the array of Stirling numbers of the second kind, A008277.

For the definition of and entries relating to the corresponding r-Stirling numbers of the first kind see A143491. For entries on r-Lah numbers refer to A143497. The theory of r-Stirling numbers of both kinds is developed in [Broder].

From Peter Bala, Sep 19 2008: (Start)

Let D be the derivative operator d/dx and E the Euler operator x*d/dx. Then x^(-2)*E^n*x^2 = Sum_{k = 0..n} T(n+2,k+2)*x^k*D^k.

The row generating polynomials R_n(x) := Sum_{k= 2..n} T(n,k)*x^k satisfy the recurrence R_(n+1)(x) = x*R_n(x) + x*d/dx(R_n(x)) with R_2(x) = x^2. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).

Relation with the 2-Eulerian numbers E_2(n,j) := A144696(n,j): T(n,k) = 2!/k!*Sum_ {j = n-k..n-2} E_2(n,j)*binomial(j,n-k) for n >= k >= 2. (End)

From Wolfdieter Lang, Sep 29 2011: (Start)

T(n,k) = S(n,k,2), n>=k>=2, in Mikhailov's first paper, eq.(28) or (A3). E.g.f. column no. k from (A20) with k->2, r->k. Therefore, with offset [0,0], this triangle is the Sheffer triangle (exp(2*x),exp(x)-1) with e.g.f. of column no. m>=0: exp(2*x)*((exp(x)-1)^m)/m!. See one of the formulas given below. For Sheffer matrices see the W. Lang link under A006232 with the S. Roman reference, also found in A132393. (End)

Essentially the same as A136124 but with column numbers differing by one. See A049444 for a signed version of this array. The unsigned 2-Stirling numbers of the first kind count the permutations of the set {1,2,...,n} into k disjoint cycles, with the restriction that the elements 1 and 2 belong to distinct cycles. This is the particular case r = 2 of the unsigned r-Stirling numbers of the first kind, which count the permutations of the set {1,2,...,n} into k disjoint cycles, with the restriction that the numbers 1, 2, ..., r belong to distinct cycles. The case r = 1 gives the usual unsigned Stirling numbers of the first kind, abs(A008275); for other cases see A143492 (r = 3) and A143493 (r = 4). The corresponding 2-Stirling numbers of the second kind can be found in A143494.

In general, the lower unitriangular array of unsigned r-Stirling numbers of the first kind (with suitable offsets in the row and column indexing) equals the matrix product St1 * P^(r-1), where St1 is the array of unsigned Stirling numbers of the first kind, abs(A008275) and P is Pascal's triangle, A007318. The theory of r-Stirling numbers of both kinds is developed in [Broder]. For details of the related r-Lah numbers see A143497.

This sequence also represents the number of permutations in the alternating group An of length k, where the length is taken with respect to the generators set {(12)(ij)}. For a bijective proof of the relation between these numbers and the 2-Stirling numbers of the first kind see the Rotbart link. - Aviv Rotbart, May 05 2011

With offset n=0,k=0 : triangle T(n,k), read by rows, given by [2,1,3,2,4,3,5,4,6,5,...] DELTA [1,0,1,0,1,0,1,0,1,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Sep 29 2011

With offset n=0 and k=0, this is the Sheffer triangle (1/(1-x)^2,-log(1-x)) (in the umbral notation of S. Roman's book this would be called Sheffer for (exp(-2*t),1-exp(-t))). See the e.g.f. given below. Compare also with the e.g.f. for the signed version A049444. - Wolfdieter Lang, Oct 10 2011

Reversed rows correspond to the Betti numbers of the moduli space M(0,n) of smooth Riemann surfaces (see Murri link). - Tom Copeland, Sep 19 2012

Row sums give A177885.

The Abel polynomials are associated with the Abel operator t*exp(y*t)*p(x) = t*p(x+y).

From Peter Luschny, Jan 14 2009: (Start)

Abs(T(n,k)) is the number of rooted labeled trees on n+1 vertices with a root degree k (Clarke's formula).

The row sums in the unsigned case, Sum_{k=0..n} abs(T(n,k)), count the trees on n+1 labeled nodes, A000272(n+1). (End)

Exponential Riordan array [1, W(x)], W(x) the Lambert W-function. - Paul Barry, Nov 19 2010

The inverse array is the exponential Riordan array [1, x*exp(x)], which is A059297. - Peter Bala, Apr 08 2013

The inverse Bell transform of [1,2,3,...]. See A264428 for the Bell transform and A264429 for the inverse Bell transform. - Peter Luschny, Dec 20 2015

Also the Bell transform of (-1)^n*(n+1)^n. - Peter Luschny, Jan 18 2016

T(n,k) is the number of ways to place n distinguishable balls into k indistinguishable bins. - Geoffrey Critzer, Mar 22 2011

From Mark Wildon, Aug 10 2015: (Start)

T(n,k) is the number of partitions of a set of size n into at most k parts.

T(n,k) is the number of sequences of n top-to-random shuffles of a deck of k cards that leave the deck invariant.

T(n,k) = where pi is the natural permutation character of the symmetric group Sym_k. This gives another combinatorial interpretation of T(n,k) as counting sequences of box moves on Young diagrams. Reference linked to below. (End)

Diagonal entries T(n,n) are the Bell numbers A000110. - Robert Israel, Aug 10 2015

From Manfred Boergens, Mar 18 2025: (Start)

The partitions in the second comment can be described as disjoint collections of subsets of [n] without the empty set with union = [n]. For instance, T(4,2)=8 is the number of partitions of [4] into 1 or 2 parts: 1234, 1 234, 2 134, 3 124, 4 123, 12 34, 13 24, 14 23.

For disjoint collections which may include one empty set see A381682.

For arbitrary collections without the empty set see A369950.

For arbitrary collections which may include one empty set see A381683. (End)

From Wolfdieter Lang, Jun 20 2011: (Start)

The row polynomials s(n,x) := Sum_{j=0..n} T(n,k)*x^k satisfy risefac(x-1,n) = s(n,x), with the rising factorials risefac(x-1,n) := Product_{j=0..n-1} (x-1+j), n >= 1, risefac(x-1,0) = 1. Compare with the formula risefac(x,n) = s1(n,x), with the row polynomials s1(n,x) of A132393 (unsigned Stirling1).

This is the lower triangular Sheffer array with e.g.f.

T(x,z) = (1-z)*exp(-x*log(1-z)) (the rewritten e.g.f. from the formula section). See the W. Lang link under A006232 for Sheffer matrices and the Roman reference. In the notation which indicates the column e.g.f.s this is Sheffer (1-z,-log(1-z)). In the umbral notation (cf. Roman) this is called Sheffer for (exp(t),1-exp(-t)).

The row polynomials satisfy s(n,x) = (x+n-1)*s(n-1,x), s(0,x)=1, and s(n,x) = (x-1)*s1(n-1,x), n >= 1, s1(0,x) = 1, with the unsigned Stirling1 row polynomials s1(n,x).

The row polynomials also satisfy

s(n,x) - s(n,x-1) = n*s(n-1,x), n > 1, s(0,x) = 1

(from the Meixner identity, see the Meixner reference given at A060338).

The row polynomials satisfy as well (from corollary 3.7.2. p. 50 of the Roman reference)

s(n,x) = (x-1)*s(n-1,x+1), n >= 1, s(0,n) = 1.

The exponential convolution identity is

s(n,x+y) = Sum_{k=0..n} binomial(n,k)*s(k,y)*s1(n-k,x),

n >= 0, with symmetry x <-> y.

The row sums are 1 for n=0 and 0 otherwise, and the alternating row sums are 1,-2,2, followed by zeros, with e.g.f. (1-x)^2.

The Sheffer a-sequence Sha(n) = A164555(n)/A027642(n) with e.g.f. x/(1-exp(-x)), and the z-sequence is Shz(n) = -1 with e.g.f. -exp(x).

The inverse Sheffer matrix is ((-1)^(n-k))*A105794(n,k) with e.g.f. exp(z)*exp(x*(1-exp(-z))). (End)

Triangle T(n,k), read by rows, given by (-1, 1, 0, 2, 1, 3, 2, 4, 3, 5, ...) DELTA (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Jan 16 2012

Also coefficients of t in t*(t-1)*Sum[(-1)^(n+m) t^(m-1) StirlingS1[n,m], {m,n}] in which setting t^k equal to k gives n!, from this follows that the dot product of row n with [0,...,n] equals (n-1)!. - Wouter Meeussen, May 15 2012

Left column = Bell numbers (A000110) starting (1, 2, 5, 15, 52, 203, ...). Row sums = A005493(n+1): (1, 3, 10, 37, 151, 674, ...).

Corresponding to the generalized Stirling number triangle of first kind A049444. - Peter Luschny, Sep 18 2011

a(n,m)= ^10P_n^m in the notation of the given reference with a(0,0) := 1. The monic row polynomials s(n,x) := sum(a(n,m)*x^m,m=0..n) which are s(n,x)= product(x-(10+k),k=0..n-1), n >= 1 and s(0,x)=1 satisfy s(n,x+y) = sum(binomial(n,k)*s(k,x)*S1(n-k,y),k=0..n), with the Stirling1 polynomials S1(n,x)=sum(A008275(n,m)*x^m, m=1..n) and S1(0,x)=1. In the umbral calculus (see the S. Roman reference given in A048854) the s(n,x) polynomials are called Sheffer for (exp(10*t),exp(t)-1).