cp's OEIS Frontend

Determinant of n X n matrix M=[m(i,j)] where m(i,i)=i, m(i,j)=1 if i > j, m(i,j)=i-j if j > i. - Vladeta Jovovic, Jan 19 2003

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

Consider all n! permutations of the integer sequence [n] = 1,2,3,...,n. The i-th permutation, i=1,2,...,n!, consists of Z(i) permutation cycles. Such a cycle has the length lc(i,j), j=1,...,Z(i). For a given permutation we form the product of all its cycle lengths Product_{j=1..Z(i)} lc(i,j). Furthermore, we sum up all such products for all permutations of [n] which gives Sum_{i=1..n!} Product_{j=1..Z(i)} lc(i,j) = A000262(n). For n=4 we have Sum_{i=1..n!} Product_{j=1..Z(i)} lc(i,j) = 1*1*1*1 + 2*1*1 + 3*1 + 2*1*1 + 3*1 + 2*1 + 3*1 + 4 + 3*1 + 4 + 2*2 + 2*1*1 + 3*1 + 4 + 3*1 + 2*1*1 + 2*2 + 4 + 2*2 + 4 + 3*1 + 2*1*1 + 3*1 + 4 = 73 = A000262(4). - Thomas Wieder, Oct 06 2006

For a finite set S of size n, a chain gang G of S is a partially ordered set (S,<=) consisting only of chains. The number of chain gangs of S is a(n). For example, with S={a, b}and n=2, there are a(2)=3 chain gangs of S, namely, {(a,a),(b,b)}, {(a,a),(a,b),(b,b)} and {(a,a),(b,a),(b,b)}. - Dennis P. Walsh, Feb 22 2007

(-1)*A000262 with the first term set to 1 and A084358 form a reciprocal pair under the list partition transform and associated operations described in A133314. Cf. A133289. - Tom Copeland, Oct 21 2007

Consider the distribution of n unlabeled elements "1" onto n levels where empty levels are allowed. In addition, the empty levels are labeled. Their names are 0_1, 0_2, 0_3, etc. This sequence gives the total number of such distributions. If the empty levels are unlabeled ("0"), then the answer is A001700. Let the colon ":" separate two levels. Then, for example, for n=3 we have a(3)=13 arrangements: 111:0_1:0_2, 0_1:111:0_2, 0_1:0_2:111, 111:0_2:0_1, 0_2:111:0_1, 0_2:0_1:111, 11:1:0, 11:0:1, 0:11:1, 1:11:0, 1:0:11, 0:1:11, 1:1:1. - Thomas Wieder, May 25 2008

Row sums of exponential Riordan array [1,x/(1-x)]. - Paul Barry, Jul 24 2008

a(n) is the number of partitions of [n] (A000110) into lists of noncrossing sets. For example, a(3)=3 counts 12, 1-2, 2-1 and a(4) = 73 counts the 75 partitions of [n] into lists of sets (A000670) except for 13-24, 24-13 which fail to be noncrossing. - David Callan, Jul 25 2008

a(i-j)/(i-j)! gives the value of the non-null element (i, j) of the lower triangular matrix exp(S)/exp(1), where S is the lower triangular matrix - of whatever dimension - having all its (non-null) elements equal to one. - Giuliano Cabrele, Aug 11 2008, Sep 07 2008

a(n) is also the number of nilpotent partial one-one bijections (of an n-element set). Equivalently, it is the number of nilpotents in the symmetric inverse semigroup (monoid). - Abdullahi Umar, Sep 14 2008

A000262 is the exp transform of the factorial numbers A000142. - Thomas Wieder, Sep 10 2008

If n is a positive integer then the infinite continued fraction (1+n)/(1+(2+n)/(2+(3+n)/(3+...))) converges to the rational number A052852(n)/A000262(n). - David Angell (angell(AT)maths.unsw.edu.au), Dec 18 2008

Vladeta Jovovic's formula dated Sep 20 2006 can be restated as follows: a(n) is the n-th ascending factorial moment of the Poisson distribution with parameter (mean) 1. - Shai Covo (green355(AT)netvision.net.il), Jan 25 2010

The umbral exponential generating function for a(n) is (1-x)^{-B}. In other words, write (1-x)^{-B} as a power series in x whose coefficients are polynomials in B, and then replace B^k with the Bell number B_k. We obtain a(0) + a(1)x + a(2)x^2/2! + ... . - Richard Stanley, Jun 07 2010

a(n) is the number of Dyck n-paths (A000108) with its peaks labeled 1,2,...,k in some order, where k is the number of peaks. For example a(2)=3 counts U(1)DU(2)D, U(2)DU(1)D, UU(1)DD where the label at each peak is in parentheses. This is easy to prove using generating functions. - David Callan, Aug 23 2011

a(n) = number of permutations of the multiset {1,1,2,2,...,n,n} such that for 1 <= i <= n, all entries between the two i's exceed i and if any such entries are present, they include n. There are (2n-1)!! permutations satisfying the first condition, and for example: a(3)=13 counts all 5!!=15 of them except 331221 and 122133 which fail the second condition. - David Callan, Aug 27 2014

a(n) is the number of acyclic, injective functions from subsets of [n] to [n]. Let subset D of [n] have size k. The number of acyclic, injective functions from D to [n] is (n-1)!/(n-k-1)! and hence a(n) = Sum_{k=0..n-1} binomial(n,k)*(n-1)!/(n-k-1)!. - Dennis P. Walsh, Nov 05 2015

a(n) is the number of acyclic, injective, labeled directed graphs on n vertices with each vertex having outdegree at most one. - Dennis P. Walsh, Nov 05 2015

For n > 0, a(n) is the number of labeled-rooted skinny-tree forests on n nodes. A skinny tree is a tree in which each vertex has at most one child. Let k denote the number of trees. There are binomial(n,k) ways to choose the roots, binomial(n-1,k-1) ways to choose the number of descendants for each root, and (n-k)! ways to permute those descendants. Summing over k, we obtain a(n) = Sum_{k=1..n} C(n,k)*C(n-1,k-1)*(n-k)!. - Dennis P. Walsh, Nov 10 2015

This is the Sheffer transform of the Bell numbers A000110 with the Sheffer matrix S = |Stirling1| = (1, -log(1-x)) = A132393. See the e.g.f. formula, a Feb 21 2017 comment on A048993, and R. Stanley's Jun 07 2010 comment above. - Wolfdieter Lang, Feb 21 2017

All terms = {1, 3} mod 10. - Muniru A Asiru, Oct 01 2017

We conjecture that for k = 2,3,4,..., the difference a(n+k) - a(n) is divisible by k: if true, then for each k the sequence a(n) taken modulo k is periodic with period dividing k. - Peter Bala, Nov 14 2017

The above conjecture is true - see the Bala link. - Peter Bala, Jan 20 2018

The terms of this sequence can be derived from the numerators of the fractions, produced by the recursion: b(0) = 1, b(n) = 1 + ((n-1) * b(n-1)) / (n-1 + b(n-1)) for n > 0. The denominators give A002720. - Dimitris Valianatos, Aug 01 2018

a(n) is the number of rooted labeled forests on n nodes that avoid the patterns 213, 312, and 123. It is also the number of rooted labeled forests that avoid 312, 213, and 132, as well as the number of rooted labeled forests that avoid 132, 213, and 321. - Kassie Archer, Aug 30 2018

For n > 0, a(n) is the number of partitions of [2n-1] whose nontrivial blocks are of type {a,b}, with a <= n and b > n. In fact, for n > 0, a(n) = A056953(2n-1). - Francesca Aicardi, Nov 03 2022

For n > 0, a(n) is the number of ways to split n people into nonempty groups, have each group sit around a circular table, and select one person from each table (where two seating arrangements are considered identical if each person has the same left neighbors in both of them). - Enrique Navarrete, Oct 01 2023

Coefficients may be generated from a modified Riordan array (MRA) formed from Rgf(z,t) = (t/(1+z))/(exp(-z/(1+z))-t) with each row of the array acting to generate the succeeding polynomial P(n,t) from the preceding n polynomials.

The MRA is constructed by appending an n! to the left of the n-th row of the Riordan array A129652 and removing the unit diagonal.

The MRA is partially

1;

1, 1;

2, 3, 2;

6, 13, 9, 3;

24, 73, 52, 18, 4;

120, 501, 365, 130, 30, 5;

720, 4051, 3006, 1095, 260, 45, 6;

For the MRA:

1) First column is the n!'s.

2) Second column is A000262.

Then, e.g., from the terms in the MRA,

P(0,t) = 0!*(t-1)^0 = 1 from the n=0 row,

P(1,t) = 1!*(t-1)^1 + 1*P(0,t) = t from the n=1 row,

P(2,t) = 2!*(t-1)^2 + 3*P(0,t)*(t-1)^1 + 2*P(1,t)

P(3,t) = 3!*(t-1)^3 + 13*P(0,t)*(t-1)^2 + 9*P(1,t)*(t-1)^1 + 3*P(2,t)

generating

P(0,t) = (1)

P(1,t) = (0, 1)

P(2,t) = (-1, 1, 2)

P(3,t) = (4, -14, 10, 6) = 4 + -14 t + 10 t^2 + 6 t^3

P(4,t) = (-15, 83, -157, 89, 24)

P(5,t) = (56, -424, 1266, -1724, 826, 120)

P(6,t) = (-185, 1887, -8038, 17642, -19593, 8287, 720)

P(7,t) = (204, -4976, 36226, -126944, 239576, -234688, 90602, 5040)

For the polynomial array:

1) The first column is A009940 = (-1)^n * n!*Lag(n,1) =(-1)^n* n!* Lag(n,-1,-1).

2) Row sums are n!.

3) Highest order coefficient is n!.

4) Alternating row sum is below.

Then, with Rf(n,t) = [ t/(1-t)^(n+1) ] * P(n,t)/n!, the polylogs are given umbrally by

Li(-n,t)/n! = [ 1 + Rf(.,t) ]^n for n = 0,1,2,... so conversely

Rf(n,t) = {[ Li(-(.),t))/(.)! ]-1}^n.

Note umbrally [ Rf(.,t) ]^n = Rf(n,t) and

(1+Rf)^0 = 1^0 * [ Rf(.,t) ]^0 = Rf(0,t) = t/(1-t) = Li(0,t).

More generally, Newton interpolation holds and for Re(s) >= 0,

Li(-s,t)/(s)! = [ 1 + Rf(.,t) ]^s, when convergent in t.

Alternatively, the Rf's may be formed through differentiation of their o.g.f., the Rgf(z,t) above, which may also be written as

Rgf(z,t) = Sum_{k>=1} [ t^k ] * exp[ k * z/(z+1) ]/(z+1)

= Sum_{n>=0} [ (-z)^n ] * Sum_{k>=1} [ (t^k * Lag(n,k) ]

= Sum_{k>=0} [ (-z)^k ] * Lag(k,Li(-(.),t))

= Sum_{k>=0} [ z^k ] * {[ Li(-(.),t))/(.)! ]-1}^k

= exp[ Li(-(.),t)*z/(1+z) ]/(1+z),

and operationally as

Rgf(z,t) = {Sum_{k>=0} (-z)^k * Lag(k,tD)} [ t/(1-t) ]

= {Sum_{k>=0} (-z)^k * Lag(k,T(.,:tD:))} [ t/(1-t) ]

= {Sum_{k>=0} (-z)^k * Sum_{j>=0} Lag(k,j) (tD)^j /j!} [ x/(1-x) ]

where D is w.r.t. x at 0

= {Sum_{k>=0} (-z)^k*Sum_{j=0..k} (-1)^j*[ 1-Lag(k,.) ]^j*(:tD:)^j/ j!} [ t/(1-t) ]

= {Sum_{k>=0} (-z)^k * exp[ -[ 1-Lag(k,.) ]* :tD: ]} [ t/(1-t) ]

where (:tD:)^n = t^n * D^n, D is the derivative w.r.t. t unless otherwise stated, Lag(n,x) is a Laguerre polynomial and T(n,t) is a Touchard / Bell / exponential polynomial.

Hence [ t/(1-t)^(n+1) ] * P(n,t)/n! = Rf(n,t)

= {Sum_{k=0..n} (-1)^n-k)*[ C(m,k)/k! ]*(tD)^k} [ t/(1-t) ]

= {Sum_{k=0..n} (-1)^(n-k)*[ C(m,k)/k! ]*Sum_{j=0..k} S2(k,j)*(:tD:)^j} [ t/(1-t) ]

= {Sum_{k>=0} (-1)^(n-k) * Lag(n,k) * (tD)^k/k!} [ x/(1-x) ] where D is w.r.t. x at 0

= {Sum_{k=0..n} (-1)^(n-k)* [ 1-Lag(n,.) ]^k *(:tD:)^k/k!}[ t/(1-t) ],

where S2(k,j) are the Stirling numbers of the second kind and C(m,k), binomial coefficients.

The P(n,t) are related to the Laguerre polynomials through

P(n,t) = (-1)^n n! [ (1-t)^(n+1)} ] Sum_{k>=0} [ (t^k*Lag(n,k+1) ] = Sum_{m=0..n} a(n,m) * t^m

where a(n,m) = (-1)^n n! [ Sum_{k=0..m} (-1)^k * C(n+1,k) *Lag(n,m-k+1) ] .

Conjecture for the polynomial array:

The greatest common divisor of the coefficients of each polynomial is given by A060872(n)/n or, equivalently, by A038548(n).

Some e.g.f.'s for the Rf's are

exp[ -Rf(.,t)*z ] = exp{[ 1-Li(-(.),t)/(.)! ]*z}

= Sum_{n>=0} { (z^n/n!) * Sum_{k>=1} [ t^k * Lag(n,k) ] }

= Sum_{k>=1} { t^k * (e^z) * J_0[ 2*sqrt(k*z)}

= Sum_{n>=0} {(-1)^n*(z^n/n!)*(z^/j!)*Lag(n,-1)*Sum_{k>=1} [ t^k*k^n*(k+1)^j ]}

where J_0(x) is the zeroth Bessel function of the first kind.

The expressions (:tD:)^j}[ t/(1-t) ] and the Laguerre polynomials are intimately connected to Lah numbers and rook polynomials.

Some interesting relations to physics, probability and number theory are, for abs(t) < 1 and abs(z) < 1 at least,

BE(t,z) = Sum_{k>=0} [ (-z)^k ] *[ 1 + Rf(.,t) ]^k

= Rgf(-z/(1+z),t)/(1+z) = t/{exp(z)-t}, a Bose-Einstein distribution,

FD(t,z) = Sum_{k>=0} [ (-z)^k+1 ] *[ 1 + Rf(.,-t) ]^k

= -Rgf(-z/(1+z),-t)/(1+z) = t/{exp(z)+t}, a Fermi-Dirac distribution

and as t tends to 1 from below, z*BE(t,z) tends to the Bernoulli e.g.f., which is related by the Mellin transform to (s-1)!*Zeta(s). Taking Mellin transforms of BE and FD w.r.t. z gives the polylogarithm over different domains.

Since BE(2,z) is essentially the e.g.f. for the ordered Bell numbers, it follows that umbrally

n! * Lag(n,OB(.)) = P(n,2) and

n! * Lag(n,P(.,2)) = OB(n)

where OB(n) are the signed ordered Bell/Fubini numbers A000670.

I.e., P(n,2) and the ordered Bell numbers form a reciprocal Laguerre combinatorial transform pair,

or, equivalently, P(n,2)/n! and OB(n)/n! form a reciprocal finite difference pair, so

P(n,2)/n! = (-1)^(n+1) * Rf(n,2) = -{1-[ Li(-(.),2))/(.)! ]}^n and

OB(n) = -Li(-n,2).

Note that n!*Lag(n,(.)!*Lag(.,x)) = x^n is a true identity for general Laguerre polynomials Lag(n,x,a) with a = -1,0,1,..., so one could look at analogous higher-order reciprocal pairs containing OB(n).

In addition, a mixed-order iterated Laguerre transform gives

n!*Lag{n,(.)!*Lag[ .,P(.,2),0 ],-1}

= P(n,2) - n*P(n-1,2)

= n!*Lag[ n,OB(.),-1 ] = A084358(n), lists of sets of lists.

For Eulerian polynomials, E(n,t), given by A173018 (A008292),

E(n,t)/n! = [ 1-t+P(.,t)/(.)! ]^n

P(n,t)/n! = [ E(.,t)/(.)!-(1-t) ]^n, or equivalently

[ E(.,t)/(1-t) ]^n = n!*Lag[ n,-P(.,t)/(1-t) ]

[ -P(.,t)/(1-t) ]^n = n!*Lag[ n,E(.,t)/(1-t) ], a Laguerre transform pair.

Then from known relations for the Eulerian polynomials, the alternating row sum of the polynomial array is

P(n,-1) = (-2)^(n+1) * n! * Lag[ n,c(.)*Zeta(-(.)) ]

where c(n) = [ 2^(n+1) - 1 ] and Zeta is the Riemann zeta function. And so

Zeta(-n) = n! * Lag[ n,-P(.,-1)/2 ] / [ 2 - 2^(n+2) ],

which also holds, with the summation limit of Lag extended to infinity, for n = s, any complex number with Re(s) > 0.

Then from standard formulas for the signed Euler numbers EN(n), the Bernoulli numbers Ber(n), the Genocchi numbers GN(n), the Euler polynomials EP(n,t), the Eulerian polynomials E(n,t), the Touchard / Bell polynomials T(n,t) and the binomial C(x,y) = x!/[ (x-y)!*y! ]

2^(n+1) * (1-2^(n+1)) * (-1)^n * Zeta(-n)

= 2^(n+1) * (1-2^(n+1)) * Ber(n+1)/(n+1)

= [ -(1+EN(.)) ]^n

= 2^n * GN(n+1)/(n+1)

= 2^n * EP(n,0)

= (-1)^n * E(n,-1)

= (-2)^n * n! * Lag[ n,-P(.,-1)/2 ]

= (-2)^n * n! * C{T[ .,P(.,-1)/2 ] + n, n}

= an integer = Q(n)

These are related to the zag numbers A000182 by Zag(n) = abs[ Q(2*n-1) ]. And, abs[ Q(2*n-1) ] / 2^q(n) = Zag(n) / 2^q(n) = A002425(n) with q(n) = A101921.

These may be generalized by letting n = s, a complex number, (or interpolating) to obtain generalized Laguerre functions or confluent hypergeometric functions of the first kind, M(a,b,x), or second kind, U(a,b,x), whose arguments are P(.,-1)/2, such as

E(s,-1)/[ 2^s*s! ] = -2*Li(-s,-1)/s! = (2-2^(s+2)) * Zeta(-s)/s!

= C{T[ .,P(.,-1)/2 ] + s, s} = Lag[ s,-P(.,-1)/2 ] = M[ -s,1,-P(.,-1)/2 ] or,

GN(s+1)/(s+1)! = EP(s,0)/s! = C{-T[ .,P(.,-1)/2 ]-1, n} = U[ -s,1,-P(.,-1)/2 ]/(s)!

And even more generally

E(s,t)/(1-t)^s = [ (1-t)/t ] Li(-s,t) = s!*Lag[ s,-P(.,t)/(1-t) ]

= s! * C{T[ .,P(.,t)/(1-t) ] + s, s} = s! * M[ -s,1,-P(.,t)/(1-t) ] .

The Laguerre polynomial expressions are fundamental as they can be interpolated to form general M[ a,b,-P(.,t)/(1-t) ] or U[ a,b,-P(.,t)/(1-t) ] which can then be related either directly or by binomial transforms to many important Sheffer sequences, not to mention group theory and Riemann surfaces.

Note for frequently occurring expressions above: The Laguerre polynomials of order -1 and 0 are intimately connected to Lah numbers and rook polynomials and (tD)^n [t/(1-t)] = T(n,:tD:) [t/(1-t)] generates an Eulerian polynomial in the numerator of a rational function. - Tom Copeland, Sep 09 2008

The deformed Todd operator on p. 12 of Gunnells and Villegas is Td(a,D) = -D / (a*exp(-D) - 1) = [-D/(1-D)] * Rgf(D/(1-D), 1/a) = -D * BE(1/a,-D) = D * FD(-1/a,-D), where BE and FD are the Bose-Einstein and Fermi-Dirac distributions given above. See also connections among the Eulerian polynomials, Ehrhart polynomials, and the Todd operator in Beck and Robins, especially pages 31 and 37. - Tom Copeland, Jun 20 2017