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

Triangle of coefficients of the polynomial (x+1)(x+2)...(x+n), expanded in decreasing powers of x. - T. D. Noe, Feb 22 2008

Row n also gives the number of permutation of 1..n with complexity 0,1,...,n-1. See the comments in A008275. - N. J. A. Sloane, Feb 08 2019

T(n,k) is the number of deco polyominoes of height n and having k columns. 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: T(2,1)=1 and T(2,2)=1 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having, respectively, 1 and 2 columns. - Emeric Deutsch, Aug 14 2006

Sum_{k=1..n} k*T(n,k) = A121586. - Emeric Deutsch, Aug 14 2006

Let the triangle U(n,k), 0 <= k <= n, read by rows, be given by [1,0,1,0,1,0,1,0,1,0,1,...] DELTA [1,1,2,2,3,3,4,4,5,5,6,...] where DELTA is the operator defined in A084938; then T(n,k) = U(n-1,k-1). - Philippe Deléham, Jan 06 2007

From Tom Copeland, Dec 15 2007: (Start)

Consider c(t) = column vector(1, t, t^2, t^3, t^4, t^5, ...).

Starting at 1 and sampling every integer to the right, we obtain (1,2,3,4,5,...). And T * c(1) = (1, 1*2, 1*2*3, 1*2*3*4,...), giving n! for n > 0. Call this sequence the right factorial (n+)!.

Starting at 1 and sampling every integer to the left, we obtain (1,0,-1,-2,-3,-4,-5,...). And T * c(-1) = (1, 1*0, 1*0*-1, 1*0*-1*-2,...) = (1, 0, 0, 0, ...), the left factorial (n-)!.

Sampling every other integer to the right, we obtain (1,3,5,7,9,...). T * c(2) = (1, 1*3, 1*3*5, ...) = (1,3,15,105,945,...), giving A001147 for n > 0, the right double factorial, (n+)!!.

Sampling every other integer to the left, we obtain (1,-1,-3,-5,-7,...). T * c(-2) = (1, 1*-1, 1*-1*-3, 1*-1*-3*-5,...) = (1,-1,3,-15,105,-945,...) = signed A001147, the left double factorial, (n-)!!.

Sampling every 3 steps to the right, we obtain (1,4,7,10,...). T * c(3) = (1, 1*4, 1*4*7,...) = (1,4,28,280,...), giving A007559 for n > 0, the right triple factorial, (n+)!!!.

Sampling every 3 steps to the left, we obtain (1,-2,-5,-8,-11,...), giving T * c(-3) = (1, 1*-2, 1*-2*-5, 1*-2*-5*-8,...) = (1,-2,10,-80,880,...) = signed A008544, the left triple factorial, (n-)!!!.

The list partition transform A133314 of [1,T * c(t)] gives [1,T * c(-t)] with all odd terms negated; e.g., LPT[1,T*c(2)] = (1,-1,-1,-3,-15,-105,-945,...) = (1,-A001147). And e.g.f. for [1,T * c(t)] = (1-xt)^(-1/t).

The above results hold for t any real or complex number. (End)

Let R_n(x) be the real and I_n(x) the imaginary part of Product_{k=0..n} (x + I*k). Then, for n=1,2,..., we have R_n(x) = Sum_{k=0..floor((n+1)/2)}(-1)^k*Stirling1(n+1,n+1-2*k)*x^(n+1-2*k), I_n(x) = Sum_{k=0..floor(n/2)}(-1)^(k+1)*Stirling1(n+1,n-2*k)*x^(n-2*k). - Milan Janjic, May 11 2008

T(n,k) is also the number of permutations of n with "reflection length" k (i.e., obtained from 12..n by k not necessarily adjacent transpositions). For example, when n=3, 132, 213, 321 are obtained by one transposition, while 231 and 312 require two transpositions. - Kyle Petersen, Oct 15 2008

From Tom Copeland, Nov 02 2010: (Start)

[x^(y+1) D]^n = x^(n*y) [T(n,1)(xD)^n + T(n,2)y (xD)^(n-1) + ... + T(n,n)y^(n-1)(xD)], with D the derivative w.r.t. x.

E.g., [x^(y+1) D]^4 = x^(4*y) [(xD)^4 + 6 y(xD)^3 + 11 y^2(xD)^2 + 6 y^3(xD)].

(xD)^m can be further expanded in terms of the Stirling numbers of the second kind and operators of the form x^j D^j. (End)

With offset 0, 0 <= k <= n: T(n,k) is the sum of products of each size k subset of {1,2,...,n}. For example, T(3,2) = 11 because there are three subsets of size two: {1,2},{1,3},{2,3}. 1*2 + 1*3 + 2*3 = 11. - Geoffrey Critzer, Feb 04 2011

The Kn11, Fi1 and Fi2 triangle sums link this triangle with two sequences, see the crossrefs. For the definitions of these triangle sums see A180662. The mirror image of this triangle is A130534. - Johannes W. Meijer, Apr 20 2011

T(n+1,k+1) is the elementary symmetric function a_k(1,2,...,n), n >= 0, k >= 0, (a_0(0):=1). See the T. D. Noe and Geoffrey Critzer comments given above. For a proof see the Stanley reference, p. 19, Second Proof. - Wolfdieter Lang, Oct 24 2011

Let g(t) = 1/d(log(P(j+1,-t)))/dt (see Tom Copeland's 2007 formulas). The Mellin transform (t to s) of t*Dirac[g(t)] gives Sum_{n=1..j} n^(-s), which as j tends to infinity gives the Riemann zeta function for Re(s) > 1. Dirac(x) is the Dirac delta function. The complex contour integral along a circle of radius 1 centered at z=1 of z^s/g(z) gives the same result. - Tom Copeland, Dec 02 2011

Rows are coefficients of the polynomial expansions of the Pochhammer symbol, or rising factorial, Pch(n,x) = (x+n-1)!/(x-1)!. Expansion of Pch(n,xD) = Pch(n,Bell(.,:xD:)) in a polynomial with terms :xD:^k=x^k*D^k gives the Lah numbers A008297. Bell(n,x) are the unsigned Bell polynomials or Stirling polynomials of the second kind A008277. - Tom Copeland, Mar 01 2014

From Tom Copeland, Dec 09 2016: (Start)

The Betti numbers, or dimension, of the pure braid group cohomology. See pp. 12 and 13 of the Hyde and Lagarias link.

Row polynomials and their products appear in presentation of the Jack symmetric functions of R. Stanley. See Copeland link on the Witt differential generator.

(End)

From Tom Copeland, Dec 16 2019: (Start)

The e.g.f. given by Copeland in the formula section appears in a combinatorial Dyson-Schwinger equation of quantum field theory in Yeats in Thm. 2 on p. 62 related to a Hopf algebra of rooted trees. See also the Green function on p. 70.

Per comments above, this array contains the coefficients in the expansion in polynomials of the Euler, or state number, operator xD of the rising factorials Pch(n,xD) = (xD+n-1)!/(xD-1)! = x [:Dx:^n/n!]x^{-1} = L_n^{-1}(-:xD:), where :Dx:^n = D^n x^n and :xD:^n = x^n D^n. The polynomials L_n^{-1} are the Laguerre polynomials of order -1, i.e., normalized Lah polynomials.

The Witt differential operators L_n = x^(n+1) D and the row e.g.f.s appear in Hopf and dual Hopf algebra relations presented by Foissy. The Witt operators satisfy L_n L_k - L_k L_n = (k-n) L_(n+k), as for the dual Hopf algebra. (End)

The numbers (4, 20, 120, 840, 6720, ...) arise from the divisor values in the general formula a(n) = n*(n+1)*(n+2)*(n+3)* ... *(n+k)*(n*(n+k) + (k-1)*k/6)/((k+3)!/6) (which covers the following sequences: A000578, A000537, A024166, A101094, A101097, A101102). - Alexander R. Povolotsky, May 17 2008

a(n) is also the number of decreasing 3-cycles in the decomposition of permutations as product of disjoint cycles, a(3)=1, a(4)=4, a(5)=20. - Wenjin Woan, Dec 21 2008

Equals eigensequence of triangle A130128 reflected. - Gary W. Adamson, Dec 23 2008

a(n) is the number of n-permutations having 1, 2, and 3 in three distinct cycles. - Geoffrey Critzer, Apr 26 2009

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

The asymptotic expansion of the higher order exponential integral E(x,m=1,n=4) ~ exp(-x)/x*(1 - 4/x + 20/x^2 - 120/x^3 + 840/x^4 - 6720/x^5 + 60480/x^6 - 604800/x^7 + ...) leads to the sequence given above. See A163931 and A130534 for more information.

(End)

From Wolfdieter Lang, Jun 27 2012: (Start)

T(n-1,k), k=1,...,n-1, gives the number of representative necklaces with n beads (C_N symmetry) of n+1-k distinct colors, say c[1],c[2],...,c[n-k+1], corresponding to the color signature determined by the partition k,1^(n-k) of n. The representative necklaces have k beads of color c[1]. E.g., n=4, k=2: partition 2,1,1, color signature (parts as exponents) c[1]c[1]c[2]c[3], 3=T(3,2) necklaces (write j for color c[j]): cyclic(1123), cyclic(1132) and cyclic(1213). See A212359 for the numbers for general partitions or color signatures. (End)

The asymptotic expansion of the higher order exponential integral E(x,m=1,n=8) ~ exp(-x)/x*(1 - 8/x + 72/x^2 - 720/x^3 + 7920/x^4 - 95040/x^5 + 235520/x^6 - 17297280/x^7 + ...) leads to the sequence given above. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009

row(0) = {1}; row(n+1) = row(n) multiplied by n and prepended with (n+1);

A111063(n+1) = sum of n-th row;

T(2*n,n) = A002690(n), central terms;

T(n,0) = n + 1;

T(n,1) = A000290(n), n > 0;

T(n,2) = A011379(n-1), n > 1;

T(n,3) = A047927(n), n > 2;

T(n,4) = A192849(n-1), n > 3;

T(n,5) = A000142(5) * A027810(n-5), n > 4;

T(n,6) = A000142(6) * A027818(n-6), n > 5;

T(n,7) = A000142(7) * A056001(n-7), n > 6;

T(n,8) = A000142(8) * A056003(n-8), n > 7;

T(n,9) = A000142(9) * A056114(n-9), n > 8;

T(n,n-10) = 11 * A051431(n-10), n > 9;

T(n,n-9) = 10 * A049398(n-9), n > 8;

T(n,n-8) = 9 * A049389(n-8), n > 7;

T(n,n-7) = 8 * A049388(n-7), n > 6;

T(n,n-6) = 7 * A001730(n), n > 5;

T(n,n-5) = 6 * A001725(n), n > 5;

T(n,n-4) = 5 * A001720(n), n > 4;

T(n,n-3) = 4 * A001715(n), n > 2;

T(n,n-2) = A070960(n), n > 1;

T(n,n-1) = A052849(n), n > 0;

T(n,n) = A000142(n);

T(n,k) = A137948(n,k) * A007318(n,k), 0 <= k <= n.

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=5 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al. Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003

a(n+4)=:b(n), n>=1, enumerates the ways to distribute n beads labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and k=5 indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as a beadless cords contribute each a factor 1 in the counting, e.g., b(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads.

This produces for b(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A001720(n+4) = (n+4)!/4!}. See the necklaces and cords problem comment in A000153. Therefore also the recurrence b(n) = (n+4)*b(n-1) + (n-1)*b(n-2) with b(-1)=0 and b(0)=1 holds. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 02 2010

The asymptotic expansion of the higher-order exponential integral E(x,m=1,n=9) ~ exp(-x)/x*(1 - 9/x + 90/x^2 - 990/x^3 + 11880/x^4 - 154440/x^5 + ...) leads to the sequence given above. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009

The p=9 member of the p-family of sequences {(n+p-1)!/p!}, n >= 1.

The asymptotic expansion of the higher order exponential integral E(x,m=1,n=10) ~ exp(-x)/x*(1 - 10/x + 110/x^2 - 1320/x^3 + 17160/x^4 - 240240/x^5 + 3603600/x^6 - ...) leads to the sequence given above. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009