A049019 -id:A049019 - cp's OEIS frontend

A120774 Number of ordered set partitions of [n] where equal-sized blocks are ordered with increasing least elements.

1, 1, 2, 8, 31, 147, 899, 5777, 41024, 322488, 2749325, 25118777, 245389896, 2554780438, 28009868787, 323746545433, 3933023224691, 49924332801387, 661988844566017, 9138403573970063, 131043199040556235, 1949750421507432009, 30031656711776544610

Offset: 0

Alford Arnold, Jul 12 2006

Old name was: Row sums of A179233.

a(n) is the number of ways to linearly order the blocks in each set partition of {1,2,...,n} where two blocks are considered identical if they have the same number of elements. - Geoffrey Critzer, Sep 29 2011

			A179233 begins 1; 1; 1 1; 6 1 1; 8 3 18 1 1 ... with row sums 1, 1 2 8 31 147 ...
a(3) = 8: 123, 1|23, 23|1, 2|13, 13|2, 3|12, 12|3, 1|2|3. - _Alois P. Heinz_, Apr 27 2017

Alois P. Heinz, Table of n, a(n) for n = 0..525

Cf. A000041, A032011, A049019, A096161, A096162, A196301.
Row sums of A179233, A285824.
Main diagonal of A327244.

b:= proc(n, i, p) option remember; `if`(n=0 or i=1,
      (p+n)!/n!, add(b(n-i*j, i-1, p+j)*combinat
      [multinomial](n, n-i*j, i$j)/j!^2, j=0..n/i))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Apr 27 2017

f[{x_,y_}]:= x!^y y!;   Table[Total[Table[n!,{PartitionsP[n]}]/Apply[Times,Map[f,Map[Tally,Partitions[n]],{2}],2] * Apply[Multinomial,Map[Last,Map[Tally,Partitions[n]],{2}],2]],{n,0,20}]  (* Geoffrey Critzer, Sep 29 2011 *)

Leading 1 inserted, definition simplified by R. J. Mathar, Sep 28 2011

a(15) corrected, more terms, and new name (using Geoffrey Critzer's comment) from Alois P. Heinz, Apr 27 2017

A098546 Table read by rows: row n has a term T(n,k) for each of the partition(n) partitions of n. T(n,k) = binomial(n,m) where m is the number of parts.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 6, 6, 4, 1, 5, 10, 10, 10, 10, 5, 1, 6, 15, 15, 15, 20, 20, 20, 15, 15, 6, 1, 7, 21, 21, 21, 35, 35, 35, 35, 35, 35, 35, 21, 21, 7, 1, 8, 28, 28, 28, 28, 56, 56, 56, 56, 56, 70, 70, 70, 70, 70, 56, 56, 56, 28, 28, 8, 1, 9, 36, 36, 36, 36, 84, 84, 84, 84, 84, 84, 84

Offset: 1

Alford Arnold, Sep 14 2004

A035206 and A036038 were used to generate A049009 (Words over signatures). A098346 and A049019 provide another approach to the same end since A098346 times A049019 also yields A049009. (cf. A000312 and A000670).

Partitions are in Abramowitz and Stegun order. - Franklin T. Adams-Watters, Nov 20 2006

			A036042 begins 1 2 2 3 3 3 4 4 4 4 4 ...
A036043 begins 1 1 2 1 2 3 1 2 2 3 4 ...
so a(n) begins 1 2 1 3 3 1 4 6 6 4 1 ...
Table begins
.
1
2 1
3 3  1
4 6  6  4  1
5 10 10 10 10 5  1
6 15 15 20 15 20 15 20 15 6 1
.

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

Cf. A090657, A000041 (row lengths), A098545 (row sums), A036036, A036042, A036043.

Table[Sequence @@
  Map[Function[p, Binomial[n, Length[p]]], IntegerPartitions[n]], {n,
  1, 10}] (* Olivier Gérard, May 07 2024 *)

a(n) = Combin( A036042(n), A036043(n) )

A248927 Triangle read by rows: T(n,k) are the coefficients of the Lagrange (compositional) inversion of a function in terms of the Taylor series expansion of its reciprocal, n >= 1, k = 1..A000041(n-1).

Original entry on oeis.org

1, 1, 2, 1, 6, 9, 1, 24, 72, 12, 16, 1, 120, 600, 300, 200, 50, 25, 1, 720, 5400, 5400, 2400, 450, 1800, 450, 60, 90, 36, 1, 5040, 52920, 88200, 29400, 22050, 44100, 7350, 4410, 2940, 4410, 882, 245, 147, 49, 1, 40320, 564480, 1411200, 376320, 705600, 940800

Offset: 1

Tom Copeland, Oct 16 2014

Coefficients are listed in reverse graded colexicographic order (A228100). This is the reverse of Abramowitz and Stegun order (A036036).
Coefficients for Lagrange (compositional) inversion of a function in terms of the Taylor series expansion of its shifted reciprocal. Complementary to A134264 for formal power series. A refinement of A141618 with row sums A000272.
Given an invertible function f(t) analytic about t=0 with f(0)=0 and df(0)/dt not 0, form h(t) = t / f(t) and denote h_n = (n') as the coefficient of t^n/n! in h(t). Then the compositional inverse of f(t), g(t), as a formal Taylor series, or e.g.f., is given up to the first few orders by
g(t)/t = [ 1 (0') ]
       + [ 1 (0') (1') ] * t
       + [ 2 (0') (1')^2 + 1 (0')^2 (2') ] * t^2/2!
       + [ 6 (0') (1')^3 + 9 (0')^2 (1') (2') + 1 (0')^3 (3') ] * t^3/3!
       + [24 (0') (1')^4 + 72 (0')^2 (1')^2 (2') + (0')^3 [12 (2')^2
           + 16 (1') (3')] + (0')^4 (4')] * t^4/4!
       + [120 (0')(1')^5 + 600 (0')^2 (1')^3(2') + (0')^3 [300 (1')(2')^2 + 200 ( 1')^2(3')] + (0')^4 [50 (2')(3') + 25 (1')(4')] + (0')^5 (5')] * t^5/5! + [720 (0')(1')^6 + (0')^2 (1')^4(2')+(0')^3 [5400 (1')^2(2')^2 + 2400 (1')^3(3')] + (0')^4 [450 (2')^3+ 1800 (1')(2')(3') + 450( 1')^2(4')]+ (0')^5 [60 (3')^2 + 90 (2')(4') + 36 (1')(5')] + (0')^6 (6')] * t^6/6! + ...
..........
From Tom Copeland, Oct 28 2014: (Start)
Expressing g(t) as a Taylor series or formal e.g.f. in the indeterminates h_n generates a refinement of A055302, which enumerates the number of labeled root trees with n nodes and k leaves, with row sum A000169.
Operating with (1/n^2) d/d(1') = (1/n^2) d/d(h_1) on the n-th partition polynomial in square brackets above associated with t^n/n! generates the (n-1)-th partition polynomial.
Multiplying the n-th partition polynomial here by (n + 1) gives the (n + 1)-th partition polynomial of A248120.  (End)
These are also the coefficients in the expansion of a series related to the Lagrange reversion theorem presented in Wikipedia of which the Lagrange inversion formula about the origin is a special case. Cf. Copeland link. - Tom Copeland, Nov 01 2016

			Triangle T(n,k) begins:
    1;
    1;
    2,    1;
    6,    9,    1;
   24,   72,   12,   16,   1;
  120,  600,  300,  200,  50,   25,   1;
  720, 5400, 5400, 2400, 450, 1800, 450, 60, 90, 36, 1;
  ...
For f(t) = e^t-1, h(t) = t/f(t) = t/(e^t-1), the e.g.f. for the Bernoulli numbers, and plugging the Bernoulli numbers into the Lagrange inversion formula gives g(t) = t - t^2/2 + t^3/3 + ... = log(1+t).

Andrew Howroyd, Table of n, a(n) for n = 1..2087 (rows 1..20)
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].
Tom Copeland, The Lagrange Reversion Theorem and the Lagrange Inversion Formula

Cf. A145271
Cf. A134264 and A248120, "scaled" versions of this Lagrange inversion.
Cf. A036038.

C(v)={my(n=vecsum(v), S=Set(v)); n!^2/((n-#v+1)!*prod(i=1, #S, my(x=S[i], c=#select(y->y==x, v)); x!^c*c!))}
row(n)=[C(Vec(p)) | p<-Vecrev(partitions(n-1))]
{ for(n=1, 7, print(row(n))) } \\ Andrew Howroyd, Feb 02 2022

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 [(j-1)!/j]* P(j,m;a...) / [(2!)^a_2 (3!)^a_3 ... ((j-1)!)^a_(j-1) ] for the k-th partition of j-1. The partitions are in reverse order--from bottom to top--from the order in Abramowitz and Stegun (page 831).
For example, from g(t) above, T(6,3) = [5!/6][6!/(3!*2!)]/(2!)^2 = 300 for the 3rd partition from the bottom under n=6-1=5 with m=3 parts, and T(6,5) = [5!/6][6!/4!]/(2!*3!) = 50.
If the initial factorial and final denominator are removed and the partitions reversed in order, A134264 is obtained, a refinement of the Narayana numbers.
For f(t) = t*e^(-t), g(t) = T(t), the Tree function, which is the e.g.f. of A000169, and h(t) = t/f(t) = e^t, so h_n = 1 for all n in this case; therefore, the row sums of A248927 are A000169(n)/n = n^(n-2) = A000272(n).
Let W(x) = 1/(df(x)/dx)= 1/{d[x/h(x)]/dx}=1/{d[x/[h_0+h_1*x+ ...]]/dx}. Then the partition polynomials above are given by (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)). See A145271.
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) and L =(d/dt)/h(d/dt)=(d/dt) 1/[(h_0)+(h_1)*d/dt+(h_2)*(d/dt)^2/2!+...], which will give a lowering operator associated to the refined f-vectors of permutohedra (cf. A133314 and A049019).
Then  [dPS(n,z)/dz]/n  eval. at z=0 are the row partition polynomials of this entry. (Cf. A139605, A145271, and link therein to Mathemagical Forests for relation to planted trees on p. 13.)
As noted in A248120 and A134264, this entry is given by the Hadamard product by partition of A134264 and A036038. For example, (1,4,2,6,1)*(1,4,6,12,24) = (1,16,12,72,24). - Tom Copeland, Nov 25 2016
T(n,k) = ((n-1)!)^2/((n-j)!*Product_{i>=1} s_i!*(i!)^s_i), where (1*s_1 + 2*s_2 + ... = n-1) is the k-th partition of n-1 and j = s_1 + s_2 ... is the number of parts. - Andrew Howroyd, Feb 02 2022

Name edited and terms a(31) and beyond from Andrew Howroyd, Feb 02 2022

A249548 Coefficients of reduced partition polynomials of A134264 for computing Lagrange compositional inversion.

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 1, 5, 1, 6, 3, 5, 1, 7, 7, 21, 1, 8, 8, 4, 28, 28, 14, 1, 9, 9, 9, 36, 72, 12, 84, 1, 10, 10, 10, 5, 45, 90, 45, 45, 120, 180, 42, 1, 11, 11, 11, 11, 55, 110, 110, 55, 55, 165, 495, 165, 330, 1, 12, 12, 12, 12, 6, 66, 132, 132, 66, 66, 132, 22, 220, 660, 330, 660, 55, 495, 990, 132

Offset: 0

Tom Copeland, Oct 31 2014

Coefficients of reduced partition polynomials of A134264 for computing the complete partition polynomials for the Lagrange compositional inversion of A134264 (see Oct 2014 comment by Copeland there). Umbrally,
e^(x*t) * exp[Prt(.;1,0,h_2,..) * t] = exp[Prt(.;1,x,h_2,..) * t], where Prt(n;1,0,h_2,..,h_n) are the reduced (h_0 = 1 and h_1 = 0) partition polynomials of the complete polynomials Prt(n;h_0,h_1,h_2,..,h_n) of A134264.
Partitions are given in the order of those on page 831 of Abramowitz and Stegun. Formulas for the coefficients of the partitions are given in A134264.
Row sums are the Motzkin sums or Riordan numbers A005043. - Tom Copeland, Nov 09 2014
From Tom Copeland, Jul 03 2018: (Start)
The matrix and operator formalism for Sheffer Appell sequences leads to the following relations with D = d/dh_1.
Exp[Prt(.;1,0,h_2,..) * D] (h_1)^n = [h_1 + Prt(.;1,0,h_2,...)]^n = Prt(n;1,h_1,h_2,...), the partition polynomials of A134264 for g(t)/t with h_0 = 1.
For the umbral compositional inverses described below,
Exp[UPrt(.;1,0,h_2,..) * D] (h_1)^n = [h_1 + UPrt(.;1,0,h_2,...)]^n = UPrt(n;1,h_1,h_2,...).
The respective e.g.f.s are multiplicative inverses; that is, exp[Prt(.;1,0,h_2,..) * t] = 1/exp[UPrt(.;1,0,h_2,..) * t], so the formalism of A133314 applies.
The raising operator R such that R Prt(n;1,h_1,h_2,...) = Prt(n+1;1,h_1,h_2,...) is R = exp[Prt(.;1,0,h_2,...)*D] h_1 exp[UPrt(.;1,0,h_2,..)*D] since R Prt(n+1;1,h_1,h_2,...) = exp[Prt(.;1,0,h_2,...)*D] h_1 (h_1)^n = Prt(n+1;h_1,h_2,...) from the definition of the umbral compositional inverse. This may also be expressed as R = h_1 + d/dD log[exp[Prt(.;1,0,h_2,...) * D]], so, using A127671, R = h_1 + h_2 D + h_3 D^2/2! + (h_4 - h_2^2) D^3/3! + (h_5 - 5 h_2 h_3) D^4/4! + (h_6 - 9 h_2 h_4 + 5 h_2^3 - 7 h_3^2) D^5/5! + (h_7 - 28 h_3 h_4 - 14 h_2 h_5 + 56 h_2^2 h_3) D^6/6! + ... . (End)

			Prt(0) = 1
Prt(1;1,0) = 0
Prt(2;1,0,h_2) = 1 h_2
Prt(3;1,0,h_2,h_3) = 1 h_3
Prt(4;1,0,h_2,..,h_4) = 1 h_4 + 2 (h_2)^2
Prt(5;1,0,h_2,..,h_5) = 1 h_5 + 5 h_2 h_3
Prt(6;1,0,h_2,..,h_6) = 1 h_6 + 6 h_2 h_4 + 3 (h_3)^2 + 5 (h_2)^3
Prt(7;1,0,h_2,..,h_7) = 1 h_7 + 7 h_3 h_4 + 7 h_2 h_5 + 21 h_3 (h_2)^2
...
------------
With h_n denoted by (n'), the first seven partition polynomials of A134264 with h_0=1 are given by the first seven coefficients of the truncated Taylor series expansion of the Euler binomial transform
e^[(1') * t] * {1 + 1 (2') *  t^2/2! + 1 (3') *  t^3/3! + [1 (4') + 2 (2')^2] *  t^4/4! + [1 (5') + 5 (2')(3')] *  t^5/5! + [1 (6') + 6 (2')(4') + 3 (3')^2 + 5 (2')^3] *  t^6/6!}, giving the truncated expansion
1 + 1 (1') * t + [1 (2') + 1 (1')^2] * t^2/2! + ... + [1 (6') + 6 (1')(5') + 6 (2')(4') + 3 (3')^2 + 15 (1')^2(4') + 30 (1')(2')(3') + 5 (2')^3 + 20 (1')^3(3') + 30 (1')^2(2')^2 + 15 (1')^4(2') + 1 (1')^6] * t^6/6!.
Extending the number of reduced partition polynomials of the transform allows for further complete polynomials of A134264 to be computed.

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

Cf. A134264, A005043, A133314, A049019, A074909, A135278.
Cf. A127671.
Rows lengths are given by A002865 (except for row 1).

rows[n_] := {{1}, {0}}~Join~Module[
    {g = 1 / D[t / (1 + Sum[h[k] t^k, {k, 2, n}] + O[t]^(n+1)), t], p = t, r},
    r = Reap[Do[p = g D[p, t]/k; Sow[Expand[Normal@p /. {t -> 0}]], {k, n+1}]][[2, 1, 2 ;;]];
    Table[Coefficient[r[[k]], Product[h[t], {t, p}]], {k, 2, n}, {p, Sort[Sort /@ IntegerPartitions[k, k, Range[2, k]]]}]];
rows[12] // Flatten (* Andrey Zabolotskiy, Feb 18 2024 *)

From Tom Copeland, Nov 10 2014: (Start)
Terms may be computed symbolically up to order n by using an iterated derivative evaluated at t=0:
with g(t) = 1/{d/dt [t/(1 + 0 t + h_2 t^2 + h_3 t^3 + ... + h_n t^n)]},
evaluate 1/n! * [g(t) d/dt]^n t at t=0, i.e., ask a symbolic math app for the first term in a series expansion of this iterated derivative, to obtain Prt(n-1).
Alternatively, the explicit formula in A134264 for the numerical coefficients of each partition can be used. (End)
From Tom Copeland, Nov 12 2014: (Start)
The first few partitions polynomials formed by taking the reciprocal of the e.g.f. of this entry's e.g.f. (cf. A133314) are
UPrt(0) = 1
UPrt(1;1,0) = 0
UPrt(2;1,0,h_2) = -1 h_2
UPrt(3;1,0,h_2,h_3) = -1 h_3
UPrt(4;1,0,h_2,..,h_4) = -1 h_4 + 4 (h_2)^2
UPrt(5;1,0,h_2,..,h_5) = -1 h_5 + 15 h_2 h_3
UPrt(6;1,0,h_2,..,h_6) = -1 h_6 + 24 h_2 h_4 + 17 (h_3)^2 + -35 (h_2)^3
...
Therefore, umbrally, [Prt(.;1,0,h_2,...) + UPrt(.;1,0,h_2,...)]^n = 0 for n>0 and unity for n=0.
Example of the umbral operation:
(a. +  b.)^2 = a.^2 + 2 a.* b. + b.^2 = a_2 + 2 a_1 * b_1 + b_2.
This implies that the umbral compositional inverses (see below) of the partition polynomials of the Lagrange inversion formula (LIF) of A134264 with h_0=1 are given by UPrt(n;1,h_1,h_2,...,h_n) = [UPrt(.;1,0,h_2,...,h_n) + h_1]^n, so that the sequence of polynomials UPrt(n;1,h_1,h_2,...,h_n) is an Appell sequence in the indeterminate h_1. So, if one calculates UPrt(n;1,h_1,...,h_n), the lower order UPrt(n-1;1,h_1,...,h_(n-1)) can be found by taking the derivative w.r.t. h_1 and dividing by n. Same applies for Prt(n;1,h_1,h_2,...,h_n).
This connects the combinatorics of the permutohedra through A133314 and A049019, or their duals, to the noncrossing partitions, Dyck lattice paths, etc. that are isomorphic with the LIF of A134264.
An Appell sequence P(.,x) with the e.g.f. e^(x*t)/w(t) possesses an umbral inverse sequence UP(.,x) with the e.g.f. w(t)e^(x*t), i.e., polynomials such that P(n,UP(.,x))= x^n = UP(n,P(.,x)) through umbral substitution, as in the binomial example. The Bernoulli polynomials with w(t) = t/(e^t - 1) are a good example with the umbral compositional inverse sequence UP(n,x) = [(x+1)^(n+1)-x^(n+1)] / (n+1) (cf. A074909 and A135278). (End)

Formula for Prt(7,..) and a(12)-a(15) added by Tom Copeland, Jul 22 2016

Rows 8-12 added by Andrey Zabolotskiy, Feb 18 2024

cp's OEIS Frontend

A120774 Number of ordered set partitions of [n] where equal-sized blocks are ordered with increasing least elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A098546 Table read by rows: row n has a term T(n,k) for each of the partition(n) partitions of n. T(n,k) = binomial(n,m) where m is the number of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A248927 Triangle read by rows: T(n,k) are the coefficients of the Lagrange (compositional) inversion of a function in terms of the Taylor series expansion of its reciprocal, n >= 1, k = 1..A000041(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A249548 Coefficients of reduced partition polynomials of A134264 for computing Lagrange compositional inversion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A098545 Row sums of A098546.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A181415 Irregular triangle a(n,k) = A049009(n,k)/n, read by rows 1<=k<=A000041(n).

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions