cp's OEIS Frontend

Prime p divides a(p+1). - Alexander Adamchuk, Jul 05 2006

Also number of lists of elements from {1,..,n} with (1st element) = (smallest element), where a list means an ordered subset (cf. A000262), see also Haskell program. - Reinhard Zumkeller, Oct 26 2010

a(n+1) = p_n(-1) where p_n(x) is the unique degree-n polynomial such that p_n(k) = A133942(k) for k = 0, 1, ..., n. - Michael Somos, Apr 30 2012

a(n) = A006231(n) + n. - Geoffrey Critzer, Oct 04 2012

Coefficients are listed in Abramowitz and Stegun order (A036036).

Given an invertible function f(t) analytic about t=0 (or a formal power series) with f(0)=0 and Df(0) not equal to 0, form h(t) = t / f(t) and let h_n denote the coefficient of t^n in h(t).

Lagrange inversion gives the compositional inverse about t=0 as g(t) = Sum_{j>=1} ( t^j * (1/j) * Sum_{permutations s with s(1) + s(2) + ... + s(j) = j - 1} h_s(1) * h_s(2) * ... * h_s(j) ) = t * T(1,1) * h_0 + Sum_{j>=2} ( t^j * Sum_{k=1..(# of partitions for j-1)} T(j,k) * H(j-1,k ; h_0,h_1,...) ), where H(j-1,k ; h_0,h_1,...) is the k-th partition for h_1 through h_(j-1) corresponding to n=j-1 on page 831 of Abramowitz and Stegun (ordered as in A&S) with (h_0)^(j-m)=(h_0)^(n+1-m) appended to each partition subsumed under n and m of A&S.

Denoting h_n by (n') for brevity, to 8th order in t,

g(t) = t * (0')

+ t^2 * [ (0') (1') ]

+ t^3 * [ (0')^2 (2') + (0') (1')^2 ]

+ t^4 * [ (0')^3 (3') + 3 (0')^2 (1') (2') + (0') (1')^3 ]

+ t^5 * [ (0')^4 (4') + 4 (0')^3 (1') (3') + 2 (0')^3 (2')^2 + 6 (0')^2 (1')^2 (2') + (0') (1')^4 ]

+ t^6 * [ (0')^5 (5') + 5 (0')^4 (1') (4') + 5 (0')^4 (2') (3') + 10 (0')^3 (1')^2 (3') + 10 (0')^3 (1') (2')^2 + 10 (0')^2 (1')^3 (2') + (0') (1')^5 ]

+ t^7 * [ (0')^6 (6') + 6 (0')^5 (1') (5') + 6 (0')^5 (2') (4') + 3 (0')^5 (3')^2 + 15 (0')^4 (1')^2 (4') + 30 (0')^4 (1') (2') (3') + 5 (0')^4 (2')^3 + 20 (0')^3 (1')^3 (3') + 30 (0')^3 (1')^2 (2')^2 + 15 (0')^2 (1')^4 (2') + (0') (1')^6]

+ t^8 * [ (0')^7 (7') + 7 (0')^6 (1') (6') + 7 (0')^6 (2') (5') + 7 (0')^6 (3') (4') + 21 (0')^5 (1')^2* (5') + 42 (0')^5 (1') (2') (4') + 21 (0')^5 (1') (3')^2 + 21 (0')^5 (2')^2 (3') + 35 (0')^4 (1')^3 (4') + 105 (0)^4 (1')^2 (2') (3') + 35 (0')^4 (1') (2')^3 + 35 (0')^3 (1')^4 (3') + 70 (0')^3 (1')^3 (2')^2 + 21 (0')^2 (1')^5 (2') + (0') (1')^7 ]

+ ..., where from the formula section, for example, T(8,1',2',...,7') = 7! / ((8 - (1'+ 2' + ... + 7'))! * 1'! * 2'! * ... * 7'!) are the coefficients of the integer partitions (1')^1' (2')^2' ... (7')^7' in the t^8 term.

A125181 is an extended, reordered version of the above sequence, omitting the leading 1, with alternate interpretations.

If the coefficients of partitions with the same exponent for h_0 are summed within rows, A001263 is obtained, omitting the leading 1.

From identification of the elements of the inversion with those on page 25 of the Ardila et al. link, the coefficients of the irregular table enumerate non-crossing partitions on [n]. - Tom Copeland, Oct 13 2014

From Tom Copeland, Oct 28-29 2014: (Start)

Operating with d/d(1') = d/d(h_1) on the n-th partition polynomial Prt(n;h_0,h_1,..,h_n) in square brackets above associated with t^(n+1) generates n * Prt(n-1;h_0,h_1,..,h_(n-1)); therefore, the polynomials are an Appell sequence of polynomials in the indeterminate h_1 when h_0=1 (a special type of Sheffer sequence).

Consequently, umbrally, [Prt(.;1,x,h_2,..) + y]^n = Prt(n;1,x+y,h_2,..); that is, Sum_{k=0..n} binomial(n,k) * Prt(k;1,x,h_2,..) * y^(n-k) = Prt(n;1,x+y,h_2,..).

Or, e^(x*z) * exp[Prt(.;1,0,h_2,..) * z] = exp[Prt(.;1,x,h_2,..) * z]. Then with x = h_1 = -(1/2) * d^2[f(t)]/dt^2 evaluated at t=0, the formal Laplace transform from z to 1/t of this expression generates g(t), the comp. inverse of f(t), when h_0 = 1 = df(t)/dt eval. at t=0.

I.e., t / (1 - t*(x + Prt(.;1,0,h_2,..))) = t / (1 - t*Prt(.;1,x,h_2,..)) = g(t), interpreted umbrally, when h_0 = 1.

(End)

Connections to and between arrays associated to the Catalan (A000108 and A007317), Riordan (A005043), Fibonacci (A000045), and Fine (A000957) numbers and to lattice paths, e.g., the Motzkin, Dyck, and Łukasiewicz, can be made explicit by considering the inverse in x of the o.g.f. of A104597(x,-t), i.e., f(x) = P(Cinv(x),t-1) = Cinv(x) / (1 + (t-1)*Cinv(x)) = x*(1-x) / (1 + (t-1)*x*(1-x)) = (x-x^2) / (1 + (t-1)*(x-x^2)), where Cinv(x) = x*(1-x) is the inverse of C(x) = (1 - sqrt(1-4*x)) / 2, a shifted o.g.f. for the Catalan numbers, and P(x,t) = x / (1+t*x) with inverse Pinv(x,t) = -P(-x,t) = x / (1-t*x). Then h(x,t) = x / f(x,t) = x * (1+(t-1)Cinv(x)) / Cinv(x) = 1 + t*x + x^2 + x^3 + ..., i.e., h_1=t and all other coefficients are 1, so the inverse of f(x,t) in x, which is explicitly in closed form finv(x,t) = C(Pinv(x,t-1)), is given by A091867, whose coefficients are sums of the refined Narayana numbers above obtained by setting h_1=(1')=t in the partition polynomials and all other coefficients to one. The group generators C(x) and P(x,t) and their inverses allow associations to be easily made between these classic number arrays. - Tom Copeland, Nov 03 2014

From Tom Copeland, Nov 10 2014: (Start)

Inverting in x with t a parameter, let F(x;t,n) = x - t*x^(n+1). Then h(x) = x / F(x;t,n) = 1 / (1-t*x^n) = 1 + t*x^n + t^2*x^(2n) + t^3*x^(3n) + ..., so h_k vanishes unless k = m*n with m an integer in which case h_k = t^m.

Finv(x;t,n) = Sum_{j>=0} {binomial((n+1)*j,j) / (n*j + 1)} * t^j * x^(n*j + 1), which gives the Catalan numbers for n=1, and the Fuss-Catalan sequences for n>1 (see A001764, n=2). [Added braces to disambiguate the formula. - N. J. A. Sloane, Oct 20 2015]

This relation reveals properties of the partitions and sums of the coefficients of the array. For n=1, h_k = t^k for all k, implying that the row sums are the Catalan numbers. For n = 2, h_k for k odd vanishes, implying that there are no blocks with only even-indexed h_k on the even-numbered rows and that only the blocks containing only even-sized bins contribute to the odd-row sums giving the Fuss-Catalan numbers for n=2. And so on, for n > 2.

These relations are reflected in any combinatorial structures enumerated by this array and the partitions, such as the noncrossing partitions depicted for a five-element set (a pentagon) in Wikipedia.

(End)

From Tom Copeland, Nov 12 2014: (Start)

An Appell sequence possesses an umbral inverse sequence (cf. A249548). The partition polynomials here, Prt(n;1,h_1,...), are an Appell sequence in the indeterminate h_1=u, so have an e.g.f. exp[Prt(.;1,u,h_2...)*t] = e^(u*t) * exp[Prt(.;1,0,h2,...)*t] with umbral inverses with an e.g.f e^(-u*t) / exp[Prt(.;1,0,h2,...)*t]. This makes contact with the formalism of A133314 (cf. also A049019 and A019538) and the signed, refined face partition polynomials of the permutahedra (or their duals), which determine the reciprocal of exp[Prt(.,0,u,h2...)*t] (cf. A249548) or exp[Prt(.;1,u,h2,...)*t], forming connections among the combinatorics of permutahedra and the noncrossing partitions, Dyck paths and trees (cf. A125181), and many other important structures isomorphic to the partitions of this entry, as well as to formal cumulants through A127671 and algebraic structures of Lie algebras. (Cf. relationship of permutahedra with the Eulerians A008292.)

(End)

From Tom Copeland, Nov 24 2014: (Start)

The n-th row multiplied by n gives the number of terms in the homogeneous symmetric monomials generated by [x(1) + x(2) + ... + x(n+1)]^n under the umbral mapping x(m)^j = h_j, for any m. E.g., [a + b + c]^2 = [a^2 + b^2 + c^2] + 2 * [a*b + a*c + b*c] is mapped to [3 * h_2] + 2 * [3 * h_1^2], and 3 * A134264(3) = 3 *(1,1)= (3,3) the number of summands in the two homogeneous polynomials in the square brackets. For n=3, [a + b + c + d]^3 = [a^3 + b^3 + ...] + 3 [a*b^2 + a*c^2 + ...] + 6 [a*b*c + a*c*d + ...] maps to [4 * h_3] + 3 [12 * h_1 * h_2] + 6 [4 * (h_1)^3], and the number of terms in the brackets is given by 4 * A134264(4) = 4 * (1,3,1) = (4,12,4).

The further reduced expression is 4 h_3 + 36 h_1 h_2 + 24 (h_1)^3 = A248120(4) with h_0 = 1. The general relation is n * A134264(n) = A248120(n) / A036038(n-1) where the arithmetic is performed on the coefficients of matching partitions in each row n.

Abramowitz and Stegun give combinatorial interpretations of A036038 and relations to other number arrays.

This can also be related to repeated umbral composition of Appell sequences and topology with the Bernoulli numbers playing a special role. See the Todd class link.

(End)

These partition polynomials are dubbed the Voiculescu polynomials on page 11 of the He and Jejjala link. - Tom Copeland, Jan 16 2015

See page 5 of the Josuat-Verges et al. reference for a refinement of these partition polynomials into a noncommutative version composed of nondecreasing parking functions. - Tom Copeland, Oct 05 2016

(Per Copeland's Oct 13 2014 comment.) The number of non-crossing set partitions whose block sizes are the parts of the n-th integer partition, where the ordering of integer partitions is first by total, then by length, then lexicographically by the reversed sequence of parts. - Gus Wiseman, Feb 15 2019

With h_0 = 1 and the other h_n replaced by suitably signed partition polynomials of A263633, the refined face partition polynomials for the associahedra of normalized A133437 with a shift in indices are obtained (cf. In the Realm of Shadows). - Tom Copeland, Sep 09 2019

Number of primitive parking functions associated to each partition of n. See Lemma 3.8 on p. 28 of Rattan. - Tom Copeland, Sep 10 2019

With h_n = n + 1, the d_k (A006013) of Table 2, p. 18, of Jong et al. are obtained, counting the n-point correlation functions in a quantum field theory. - Tom Copeland, Dec 25 2019

By inspection of the diagrams on Robert Dickau's website, one can see the relationship between the monomials of this entry and the connectivity of the line segments of the noncrossing partitions. - Tom Copeland, Dec 25 2019

Speicher has examples of the first four inversion partition polynomials on pp. 22 and 23 with his k_n equivalent to h_n = (n') here with h_0 = 1. Identifying z = t, C(z) = t/f(t) = h(t), and M(z) = f^(-1)(t)/t, then statement (3), on p. 43, of Theorem 3.26, C(z M(z)) = M(z), is equivalent to substituting f^(-1)(t) for t in t/f(t), and statement (4), M(z/C(z)) = C(z), to substituting f(t) for t in f^(-1)(t)/t. - Tom Copeland, Dec 08 2021

Given a Laurent series of the form f(z) = 1/z + h_1 + h_2 z + h_3 z^2 + ..., the compositional inverse is f^(-1)(z) = 1/z + Prt(1;1,h_1)/z^2 + Prt(2;1,h_1,h_2)/z^3 + ... = 1/z + h_1/z^2 + (h_1^2 + h_2)/z^3 + (h_1^3 + 3 h_1 h_2 + h_3)/z^4 + (h_1^4 + 6 h_1^2 h_2 + 4 h_1 h_3 + 2 h_2^2 + h_4)/z^5 + ... for which the polynomials in the numerators are the partition polynomials of this entry. For example, this formula applied to the q-expansion of Klein's j-invariant / function with coefficients A000521, related to monstrous moonshine, gives the compositional inverse with the coefficients A091406 (see He and Jejjala). - Tom Copeland, Dec 18 2021

The partition polynomials of A350499 'invert' the polynomials of this entry giving the indeterminates h_n. A multinomial formula for the coefficients of the partition polynomials of this entry, equivalent to the multinomial formula presented in the first four sentences of the formula section below, is presented in the MathOverflow question referenced in A350499. - Tom Copeland, Feb 19 2022

Related to Incomplete Gamma Function at 1/2. - Michael Somos, Mar 26 1999

For positive n, a(n) is equal to 2^n times the permanent of the n X n matrix with 3/2's along the main diagonal, and 1's everywhere else. - John M. Campbell, Jul 09 2011

Number of ways to sort a spreadsheet with n columns. (A subset of columns is chosen to sort on. These columns are ordered from major to minor, and each designated as to whether to sort by ascending or descending order. For example a spreadsheet with columns A,B,C,D could be sorted by column D ascending, then by column B descending, or any of 632 other ways.) - Marc LeBrun, Dec 07 2013

a(n) is a specific instance of sequences having the form b(0) = x, b(n) = a*n*b(n-1) + k for n >= 1. (Here x = 1, a = 2, and k = 1). Sequences of this form have a closed form of b(n) = n!*a^n*x + k*Sum_{j=1..n} n!*a^(n-j)/j!. - Gary Detlefs, Mar 26 2018

p divides a(p-1) for prime p = {2, 5, 13, 37, 463, ...} which apparently coincides with A064384(n) = {2, 5, 13, 37, 463, ...} Primes p such that p divides 0!-1!+2!-3!+...+(-1)^{p-1}(p-1)!. - Alexander Adamchuk, Jun 14 2007

GCD(a(n), a(n+2)) = A124779(n) is either 1 or a prime 2, 5, 13, 37, 463, ... = A064384. - Jonathan Sondow, Jun 12 2007

For proofs of Adamchuk's and my Comments, see the link "The Taylor series for e ...". - Jonathan Sondow, Jun 18 2007

A010843, A000023, A000166, A000142, A000522, A010842, A053486, A053487 are successive binomial transforms with the e.g.f. exp(k*x)/(1-x) and recurrence b(n) = n*b(n-1)+k^n and are related to incomplete gamma functions at k. In this case k=-2, a(n) = n*a(n-1)+(-2)^n = Gamma(n+1,k)*exp(k) = Sum_{i=0..n} (-1)^(n-i)*binomial(n,i)*i^(n-i)*(i+k)^i. - Vladeta Jovovic, Aug 19 2002

a(n) is the permanent of the n X n matrix with -1's on the diagonal and 1's elsewhere. - Philippe Deléham, Dec 15 2003

Incomplete Gamma Function at 2, more precisely: a(n) = exp(2)*Gamma(1+n,2).

Let P(A) be the power set of an n-element set A. Then a(n) = the total number of ways to add 0 or more elements of A to each element x of P(A) where the elements to add are not elements of x and order of addition is important. - Ross La Haye, Nov 19 2007

a(n) is the number of ways to split the set {1,2,...,n} into two disjoint subsets S,T with S union T = {1,2,...,n} and linearly order S and then choose a subset of T. - Geoffrey Critzer, Mar 10 2009

Numerators of successive convergents to e using continued fraction 1 + 2/(1 + 1/(6 + 1/(10 + 1/(14 + 1/(18 + 1/(22 + 1/26 + ...)))))).

Number of ways to use the elements of {1,...,k}, n <= k <= 2n, once each to form a collection of n lists, each having length 1 or 2. - Bob Proctor, Apr 18 2005, Jun 26 2006

The a-sequence for this Sheffer matrix is A027641(n)/A027642(n) (Bernoulli numbers) and the z-sequence is A130189(n)/ A130190(n). See the W. Lang link.

Take the lower triangular matrix in A049020 and invert it, then read by rows! - N. J. A. Sloane, Feb 07 2009

Exponential Riordan array [exp(x), log(1/(1-x))]. Equal to A007318*A132393. - Paul Barry, Apr 23 2009

A signed version of the triangle appears in [Gessel]. - Peter Bala, Aug 31 2012

T(n,k) is the number of permutations over all subsets of {1,2,...,n} (Cf. A000522) that have exactly k cycles. T(3,2) = 6: We permute the elements of the subsets {1,2}, {1,3}, {2,3}. Each has one permutation with 2 cycles. We permute the elements of {1,2,3} and there are three permutations that have 2 cycles. 3*1 + 1*3 = 6. - Geoffrey Critzer, Feb 24 2013

From Wolfdieter Lang, Jul 28 2017: (Start)

In Chihara's book the row polynomials (with rising powers) are the Charlier polynomials (-1)^n*C^(a)_n(-x), with a = -1, n >= 0. See p. 170, eq. (1.4).

In Ismail's book the present Charlier polynomials are denoted by C_n(-x;a=1) on p. 177, eq. (6.1.25). (End)

The triangle T(n,k) is a representative of the parametric family of triangles T(m,n,k), whose columns are the coefficients of the standard expansion of the function f(x) = (-log(1-x))^(k)*exp(-m*x)/k! for the case m=-1. See A381082. - Igor Victorovich Statsenko, Feb 14 2025

T(n,k) is the number of positroid cells of the totally nonnegative Grassmannian G+(k,n) (cf. Postnikov/Williams). It is the triangle of the h-vectors of the stellahedra. - Tom Copeland, Oct 10 2014

See A248727 for a simple transformation of the row polynomials of this entry that produces the umbral compositional inverses of the polynomials of A074909, related to the face polynomials of the simplices. - Tom Copeland, Jan 21 2015

From Tom Copeland, Jan 24 2015: (Start)

The reciprocal of this entry's e.g.f. is [t e^(-xt) - e^(-x)] / (t-1) = 1 - (1+t) x + (1+t+t^2) x^2/2! - (1+t+t^2+t^3) x^3/3! + ... = e^(q.(0;t)x), giving the base sequence (q.(0;t))^n = q_n(0;t) = (-1)^n [1-t^(n+1)] / (1-t) for the umbral compositional inverses (q.(0;t)+z)^n = q_n(z;t) of the Appell polynomials associated with this entry, p_n(z;t) below, i.e., q_n(p.(z;t)) = z^n = p_n(q.(z;t)), in umbral notation. The relations in A133314 then apply between the two sets of base polynomials. (Inserted missing index in a formula - Mar 03 2016.)

The associated o.g.f. for the umbral inverses is Og(x) = x / (1-x q.(0:t)) = x / [(1+x)(1+tx)] = x / [1+(1+t)x+tx^2]. Applying A134264 to h(x) = x / Og(x) = 1 + (1+t) x + t x^2 leads to an o.g.f. for the Narayana polynomials A001263 as the comp. inverse Oginv(x) = [1-(1+t)x-sqrt[1-2(1+t)x+((t-1)x)^2]] / (2xt). Note that Og(x) gives the signed h-polynomials of the simplices and that Oginv(x) gives the h-polynomials of the simplicial duals of the Stasheff polynomials, or type A associahedra. Contrast this with A248727 = A046802 * A007318, which has o.g.f.s related to the corresponding f-polynomials. (End)

The Appell polynomials p_n(x;t) in the formulas below specialize to the Swiss-knife polynomials of A119879 for t = -1, so the Springer numbers A001586 are given by 2^n p_n(1/2;-1). - Tom Copeland, Oct 14 2015

The row polynomials are the h-polynomials associated to the stellahedra, whose f-polynomials are the row polynomials of A248727. Cf. page 60 of the Buchstaber and Panov link. - Tom Copeland, Nov 08 2016

The row polynomials are the h-polynomials of the stellohedra, which enumerate partial permutations according to descents. Cf. Section 10.4 of the Postnikov-Reiner-Williams reference. - Lauren Williams, Jul 05 2022

From p. 60 of the Buchstaber and Panov link, S = P * C / T where S, P, C, and T are the bivariate e.g.f.s of the h vectors of the stellahedra, permutahedra, hypercubes, and (n-1)-simplices, respectively. - Tom Copeland, Jan 09 2017

The number of Le-diagrams of type (k, n) this means the diagram uses the bounding box size k x (n-k), equivalently the number of Grassmann necklaces of type (k, n) and also the number of decorated permutations with k anti-exceedances. - Thomas Scheuerle, Dec 29 2024