login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A134264 Coefficients, T(j,k), of a partition transform for Lagrange inversion. 12
1, 1, 1, 1, 1, 3, 1, 1, 4, 2, 6, 1, 1, 5, 5, 10, 10, 10, 1, 1, 6, 6, 3, 15, 30, 5, 20, 30, 15, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

Matrix begins

1;

1;

1, 1;

1, 3, 1;

1, 4, 2, 6, 1;

1, 5, 5, 10, 10, 10, 1;

1, 6, 6, 3, 15, 30, 5, 20, 30, 15, 1;

...

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

Lagrange inversion gives the compositional inverse about t=0 as g(t) = sum(j=1,2,...) { t^j * (1/j) * sum(over all permutations 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,3,...) { 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 5th 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 ] + ...

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 number of 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 eval. 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)

From Tom Copeland, Nov 03 2014: (Start)

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 Lukasiewicz, 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. (End)

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

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 Catalans. 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^2 + a*c^2 + b*c^2] is mapped to [3 * h_2] + 2 * [3 * h_1 * h_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 3 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.

The Abramowitz and Stegun gives 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)

LINKS

Table of n, a(n) for n=1..30.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

F. Ardila, F. Rincon, L. Williams, Positroids and non-crossing partitions, arXiv preprint arXiv:1308.2698v2, 2013 (pg. 25).

Tom Copeland, Compositional inversion and Appell sequences

Tom Copeland, The Hirzebruch criterion for the Todd class Dec. 14, 2014

Wikipedia, Noncrossing partition

FORMULA

For j>1, there are P(j,m;a...) = j! / [ (j-m)! (a_1)! (a_2)! ... (a_(j-1))! ] permutations of h_0 through h_(j-1) in which h_0 is repeated (j-m) times; h_1, repeated a_1 times; and so on with a_1 + a_2 + ... + a_(j-1) = m.

If, in addition, a_1 + 2 * a_2 + ... + (j-1) * a_(j-1) = j-1, then each distinct combination of these arrangements is correlated with a partition of j-1.

T(j,k) is [ P(j,m;a...) / j ] for the k-th partition of j-1 as described in the comments.

For example from g(t) above, T(5,4) = [ 5! / ((5-3)! * 2!) ] / 5 = 6 for the 4th partition under n=5-1=4 with m=3 parts in A&S.

From Tom Copeland, Sep 30 2011: (Start)

Let W(x) = 1/(df(x)/dx)= 1/{d[x/h(x)]/dx}

  = [(h_0)-1+:1/(1-h.*x):]^2 / {(h_0)-:[h.x/(1-h.x)]^2:}

  = [(h_0)+(h_1)x+(h_2)x^2+...]^2 / [(h_0)-(h_2)x^2-2(h_3)x^3-3(h_4)x^4-...], where :" ": denotes umbral evaluation of the expression within the colons and h. is an umbral coefficient.

Then for the partition polynomials of A134264,

  Poly[n;h_0,...,h_(n-1)]=(1/n!)(W(x)*d/dx)^n x, evaluated at x=0, and the compositional inverse of f(t) is g(t)= exp(t*W(x)*d/dx) x, evaluated at x=0. Also, dg(t)/dt = W(g(t)), and g(t) gives A001263 with (h_0)=u and (h_n)=1 for n>0 and A000108 with u=1. (End)

From Tom Copeland, Oct 20 2011: (Start)

With exp[x* PS(.,t)] = exp[t*g(x)]=exp[x*W(y)d/dy] exp(t*y) eval. at y=0, the raising (creation) and lowering (annihilation) operators defined by R PS(n,t)=PS(n+1,t) and L PS(n,t)= n*PS(n-1,t) are

R = t*W(d/dt) = t* [(h_0)+(h_1)d/dt+(h_2)(d/dt)^2+...]^2 / [(h_0)-(h_2)(d/dt)^2-2(h_3)(d/dt)^3-3(h_4)(d/dt)^4+...],  and

L =(d/dt)/h(d/dt)=(d/dt) 1/[(h_0)+(h_1)*d/dt+(h_2)*(d/dt)^2+...]

Then  P(n,t) = (t^n/n!) dPS(n,z)/dz  eval. at z=0 are the row polynomials of A134264. (Cf. A139605, A145271, and link therein to Mathemagical Forests for relation to planted trees on p. 13.) (End)

EXAMPLE

1) With f(t) = t / (t-1), then h(t) = -(1-t), giving h_0 = -1, h_1 = 1 and h_n = 0 for n>1. Then g(t) = -t - t^2 - t^3 - ... = t / (t-1).

2) With f(t) = t*(1-t), then h(t) = 1 / (1-t), giving h_n = 1 for all n. The compositional inverse of this f(t) is g(t) = t*A(t) where A(t) is the o.g.f. for the Catalan numbers; therefore the sum over k of T(j,k), i.e., the row sum, is the Catalan number A000108(j-1).

3) With f(t) = [ exp(-a*t)-1 ] / (-a), then h(t) = sum(n=0,1,...) Bernoulli(n) * (-a*t)^n / n! and g(t) = log(1-a*t) / (-a) = sum(n=1,...) a^(n-1) * t^n / n. Therefore with h_n = Bernoulli(n) * (-a)^n / n!, { sum(over all permutations with s(1) + s(2) + ... + s(j)=j-1) [ h_s(1) * h_s(2) * ... h_s(j) ] } = { j * sum(k=1,..., # of partitions for j-1) [ T(j,k) * H(j-1,k ; h_0,h_1,...) ] } = a^(j-1). Note, in turn, sum(a=1 to m) a^(j-1) = [ Bernoulli(j,m+1) - Bernoulli(j) ] / j for the Bernoulli polynomials and numbers, for j>1.

4) With f(t,x)= t/[x-1+1/(1-t)], then h(t,x)=[x-1+1/(1-t)], giving (h_0)=x and (h_n)=1 for n>1. Then g(t,x) = {1-(1-x)*t-sqrt[1-2*(1+x)*t+[(x-1)*t]^2]}/2, a shifted o.g.f. in t for the Narayana polynomials in x of A001263.

5) With h(t)= o.g.f. of A075834, but with A075834(1)=2 rather than 1, which is the o.g.f. for the number of connected positroids on [n] (cf. Ardila et al., p. 25), g(t) is the o.g.f. for A000522, which is the o.g.f. for the number of positroids on [n]. (Added Oct 13 2014 by author.)

CROSSREFS

Cf. A145271, (A001263,A119900) = (reduced array, associated g(x)).

Cf. A119900 (e.g.f. for reduced W(x) with (h_0)=t and (h_n)=1 for n>0).

Cf. A248927 and A248120, "scaled" versions of this Lagrange inversion.

Cf. A125181, A091867 for relations to lattice paths and trees.

Cf. A000108, A007317, A005043, A000045, A000957, A104597, A075834, A000522, A001764.

Cf. A249548 for use of Appell properties to generate the polynomials.

Cf. A133314, A049019, A019538, A127671, and A008292 for relations to permutahedra, Eulerians.

Cf. A036038.

Sequence in context: A188139 A134557 A219842 * A125181 A157076 A049999

Adjacent sequences:  A134261 A134262 A134263 * A134265 A134266 A134267

KEYWORD

nonn,tabf,more,changed

AUTHOR

Tom Copeland, Jan 14 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 20 19:35 EST 2014. Contains 252289 sequences.