A196545 -id:A196545 - cp's OEIS frontend

A296150 Triangle whose n-th row is the integer partition with Heinz number n.

1, 2, 1, 1, 3, 2, 1, 4, 1, 1, 1, 2, 2, 3, 1, 5, 2, 1, 1, 6, 4, 1, 3, 2, 1, 1, 1, 1, 7, 2, 2, 1, 8, 3, 1, 1, 4, 2, 5, 1, 9, 2, 1, 1, 1, 3, 3, 6, 1, 2, 2, 2, 4, 1, 1, 10, 3, 2, 1, 11, 1, 1, 1, 1, 1, 5, 2, 7, 1, 4, 3, 2, 2, 1, 1, 12, 8, 1, 6, 2, 3, 1, 1, 1, 13, 4

Offset: 1

Gus Wiseman, Feb 05 2018

Same as A112798 with rows reversed. Row lengths are A001222. Rows sums are A056239.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of partitions begins: (), (1), (2), (11), (3), (21), (4), (111), (22), (31), (5), (211), (6), (41), (32), (1111), (7), (221).

Robert Israel, Table of n, a(n) for n = 1..10002 (rows 1 to 3272, flattened)

Cf. A000041, A000720, A001222, A056239, A063834, A112798, A196545, A215366, A289501, A299200, A299201, A299202, A299203.

f := n -> op(map(numtheory:-pi, sort(map(`$`@op, ifactors(n)[2]), `>`))):
map(f, [$1..100]); # Robert Israel, Feb 09 2018

Table[If[n===1,{},Join@@Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]],{n,50}]

A063834 Twice partitioned numbers: the number of ways a number can be partitioned into not necessarily different parts and each part is again so partitioned.

Original entry on oeis.org

1, 1, 3, 6, 15, 28, 66, 122, 266, 503, 1027, 1913, 3874, 7099, 13799, 25501, 48508, 88295, 165942, 299649, 554545, 997281, 1817984, 3245430, 5875438, 10410768, 18635587, 32885735, 58399350, 102381103, 180634057, 314957425, 551857780, 958031826, 1667918758

Offset: 0

Wouter Meeussen, Aug 21 2001

These are different from plane partitions.
For ordered partitions of partitions see A055887 which may be computed from A036036 and A048996. - Alford Arnold, May 19 2006
Twice partitioned numbers correspond to triangles (or compositions) in the multiorder of integer partitions. - Gus Wiseman, Oct 28 2015

			G.f. = 1 + x + 3*x^2 + 6*x^3 + 15*x^4 + 28*x^5 + 66*x^6 + 122*x^7 + 266*x^8 + ...
If n=6, a possible first partitioning is (3+3), resulting in the following second partitionings: ((3),(3)), ((3),(2+1)), ((3),(1+1+1)), ((2+1),(3)), ((2+1),(2+1)), ((2+1),(1+1+1)), ((1+1+1),(3)), ((1+1+1),(2+1)), ((1+1+1),(1+1+1)).

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (terms n=1..500 from T. D. Noe)
Vaclav Kotesovec, Screenshot - A closed form formula for the constant c
Gus Wiseman, Comcategories and Multiorders
Gus Wiseman, Sequences enumerating triangles of integer partitions
Gus Wiseman, On the Categorical Structure of Weakly Ordered Sequences of Integer Partitions

Cf. A063835, A196545.
Cf. A036036, A048996, A055887.
Cf. A006906, A270995.
Cf. A007425, A047966, A047968, A271619, A279375, A279784-A279791.
The strict case is A296122.
Row sums of A321449.
Column k=2 of A323718.
Without singletons we have A327769, A358828, A358829.
For odd lengths we have A358823, A358824.
For distinct lengths we have A358830, A358912.
For strict partitions see A358914, A382524.
A000041 counts integer partitions, strict A000009.
A001970 counts multiset partitions of integer partitions.
Cf. A075900, A358831, A358833, A358906, A358908, A358909.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      b(n, i-1)+`if`(i>n, 0, numbpart(i)*b(n-i, i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 26 2015

Table[Plus @@ Apply[Times, IntegerPartitions[i] /. i_Integer :> PartitionsP[i], 2], {i, 36}]
(* second program: *)
b[n_, i_] := b[n, i] = If[n==0 || i==1, 1, b[n, i-1] + If[i > n, 0, PartitionsP[i]*b[n-i, i]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jan 20 2016, after Alois P. Heinz *)

{a(n) = if( n<0, 0, polcoeff( 1 / prod(k=1, n, 1 - numbpart(k) * x^k, 1 + x * O(x^n)), n))}; /* Michael Somos, Dec 19 2016 */

G.f.: 1/Product_{k>0} (1-A000041(k)*x^k). n*a(n) = Sum_{k=1..n} b(k)*a(n-k), a(0) = 1, where b(k) = Sum_{d|k} d*A000041(d)^(k/d) = 1, 5, 10, 29, 36, 110, 106, ... . - Vladeta Jovovic, Jun 19 2003
From Vaclav Kotesovec, Mar 27 2016: (Start)
a(n) ~ c * 5^(n/4), where
c = 96146522937.7161898848278970039269600938032826... if n mod 4 = 0
c = 96146521894.9433858914667933636782092683849082... if n mod 4 = 1
c = 96146522937.2138934755566928890704687838407524... if n mod 4 = 2
c = 96146521894.8218716328341714149619262713426755... if n mod 4 = 3
(End)

a(0)=1 prepended by Alois P. Heinz, Nov 26 2015

A000311 Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.

Original entry on oeis.org

0, 1, 1, 4, 26, 236, 2752, 39208, 660032, 12818912, 282137824, 6939897856, 188666182784, 5617349020544, 181790703209728, 6353726042486272, 238513970965257728, 9571020586419012608, 408837905660444010496, 18522305410364986906624

Offset: 0

N. J. A. Sloane

a(n) is the number of labeled series-reduced rooted trees with n leaves (root has degree 0 or >= 2); a(n-1) = number of labeled series-reduced trees with n leaves. Also number of series-parallel networks with n labeled edges, divided by 2.
A total partition of n is essentially what is meant by the first part of the previous line: take the numbers 12...n, and partition them into at least two blocks. Partition each block with at least 2 elements into at least two blocks. Repeat until only blocks of size 1 remain. (See the reference to Stanley, Vol. 2.) - N. J. A. Sloane, Aug 03 2016
Polynomials with coefficients in triangle A008517, evaluated at 2. - Ralf Stephan, Dec 13 2004
Row sums of unsigned A134685. - Tom Copeland, Oct 11 2008
Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - Tom Copeland, Jan 24 2018
From Gus Wiseman, Dec 28 2019: (Start)
Also the number of singleton-reduced phylogenetic trees with n labels. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) nonempty sets. It is singleton-reduced if no non-leaf node covers only singleton branches. For example, the a(4) = 26 trees are:
  {1,2,3,4}  {{1},{2},{3,4}}  {{1},{2,3,4}}
             {{1},{2,3},{4}}  {{1,2},{3,4}}
             {{1,2},{3},{4}}  {{1,2,3},{4}}
             {{1},{2,4},{3}}  {{1,2,4},{3}}
             {{1,3},{2},{4}}  {{1,3},{2,4}}
             {{1,4},{2},{3}}  {{1,3,4},{2}}
                              {{1,4},{2,3}}
                              {{{1},{2,3}},{4}}
                              {{{1,2},{3}},{4}}
                              {{1},{{2},{3,4}}}
                              {{1},{{2,3},{4}}}
                              {{{1},{2,4}},{3}}
                              {{{1,2},{4}},{3}}
                              {{1},{{2,4},{3}}}
                              {{{1,3},{2}},{4}}
                              {{{1},{3,4}},{2}}
                              {{{1,3},{4}},{2}}
                              {{{1,4},{2}},{3}}
                              {{{1,4},{3}},{2}}
(End)

			E.g.f.: A(x) = x + x^2/2! + 4*x^3/3! + 26*x^4/4! + 236*x^5/5! + 2752*x^6/6! + ...
where exp(A(x)) = 1 - x + 2*A(x), and thus
Series_Reversion(A(x)) = x - x^2/2! - x^3/3! - x^4/4! - x^5/5! - x^6/6! + ...
O.g.f.: G(x) = x + x^2 + 4*x^3 + 26*x^4 + 236*x^5 + 2752*x^6 + 39208*x^7 + ...
where
G(x) = x/2 + x/(2*(2-x)) + x/(2*(2-x)*(2-2*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)*(2-5*x)) + ...
From _Gus Wiseman_, Dec 28 2019: (Start)
A rooted tree is series-reduced if it has no unary branchings, so every non-leaf node covers at least two other nodes. The a(4) = 26 series-reduced rooted trees with 4 labeled leaves are the following. Each bracket (...) corresponds to a non-leaf node.
  (1234)  ((12)34)  ((123)4)
          (1(23)4)  (1(234))
          (12(34))  ((124)3)
          (1(24)3)  ((134)2)
          ((13)24)  (((12)3)4)
          ((14)23)  ((1(23))4)
                    ((12)(34))
                    (1((23)4))
                    (1(2(34)))
                    (((12)4)3)
                    ((1(24))3)
                    (1((24)3))
                    (((13)2)4)
                    ((13)(24))
                    (((13)4)2)
                    ((1(34))2)
                    (((14)2)3)
                    ((14)(23))
                    (((14)3)2)
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 224.
J. Felsenstein, Inferring phyogenies, Sinauer Associates, 2004; see p. 25ff.
L. R. Foulds and R. W. Robinson, Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 197.
E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see "total partitions", Example 5.2.5, Equation (5.27), and also Fig. 5-3 on page 14. See also the Notes on page 66.

N. J. A. Sloane, Table of n, a(n) for n = 0..375 [Shortened file because terms grow rapidly: see Sloane link below for additional terms]
Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin Leuner, On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture, arXiv:1907.01073 [math.CO], 2019.
Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot, Random cographs: Brownian graphon limit and asymptotic degree distribution, arXiv:1907.08517 [math.CO], 2019.
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 58.
A. Blass, N. Dobrinen, and D. Raghavan, The next best thing to a P-point, arXiv preprint arXiv:1308.3790 [math.LO], 2013.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155 and 159.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
L. Carlitz and J. Riordan, The number of labeled two-terminal series-parallel networks, Duke Math. J. 23 (1956), 435-445 (the sequence called {A_n}).
Tom Copeland, Comments on A000311
Brian Drake, Ira M. Gessel, and Guoce Xin, Three Proofs and a Generalization of the Goulden-Litsyn-Shevelev Conjecture on a Sequence Arising in Algebraic Geometry, J. of Integer Sequences, Vol. 10 (2007), Article 07.3.7
John Engbers, David Galvin, and Clifford Smyth, Restricted Stirling and Lah numbers and their inverses, arXiv:1610.05803 [math.CO], 2016.
J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)
J. Felsenstein, The number of evolutionary trees, Systematic Biology, 27 (1978), pp. 27-33, 1978.
S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Philippe Flajolet, A Problem in Statistical Classification Theory
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 129
Daniel L. Geisler, Combinatorics of Iterated Functions
M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984) Table 1
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 69
D. Jackson, A. Kempf, and A. Morales, A robust generalization of the Legendre transform for QFT, arXiv:1612.0046 [hep-th], 2017.
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.
B. R. Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Vladimir V. Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
Shi-Mei Ma, Jun-Ying Liu, Jean Yeh, and Yeong-Nan Yeh, Eulerian-type polynomials over Stirling permutations and box sorting algorithm, arXiv:2506.16438 [math.CO], 2025. See p. 5.
Dragan Mašulović, Big Ramsey spectra of countable chains, arXiv:1912.03022 [math.CO], 2019.
Arnau Mir, Francesc Rossello, and Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018.
J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
F. Murtagh, Counting dendrograms: a survey, Discrete Appl. Math., 7 (1984), 191-199.
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.
P. Regner, Phylogenetic Trees: Selected Combinatorial Problems, Master's Thesis, 2012, Institute of Discrete Mathematics and Geometry, TU Vienna, pp. 50-59.
J. Riordan, Letter to N. J. A. Sloane, Jul. 1970
J. Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16.
E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]
N. J. A. Sloane, Table of n, a(n) for n = 0..500
J. Taylor, Formal group laws and hypergraph colorings, doctoral thesis, Univ. of Wash., 2016, p. 95. [_Tom Copeland_, Dec 20 2018]
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See pp. 2, 12.
Index entries for sequences related to trees
Index entries for sequences related to rooted trees
Index entries for "core" sequences
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to parenthesizing

Row sums of A064060 and A134991.
The unlabeled version is A000669.
Unlabeled phylogenetic trees are A141268.
The node-counting version is A060356, with unlabeled version A001678.
Phylogenetic trees with n labels are A005804.
Chains of set partitions are A005121, with maximal version A002846.
Inequivalent leaf-colorings of series-reduced rooted trees are A318231.
Cf. A001003, A007827, A005805, A006351, A000084.
For n >= 2, A000311(n) = A006351(n)/2 = A005640(n)/2^(n+1).
Cf. A000110, A000669 = unlabeled hierarchies, A119649.
Cf. A000670, A135494, A134685.
Cf. A048816, A196545, A213427, A316651, A316652, A330626, A330627.
Cf. A000169, A042977, A133314, A134685, A269939.

M:=499; a:=array(0..500); a[0]:=0; a[1]:=1; a[2]:=1; for n from 0 to 2 do lprint(n,a[n]); od: for n from 2 to M do a[n+1]:=(n+2)*a[n]+2*add(binomial(n,k)*a[k]*a[n-k+1],k=2..n-1); lprint(n+1,a[n+1]); od:
Order := 50; t1 := solve(series((exp(A)-2*A-1),A)=-x,A); A000311 := n-> n!*coeff(t1,x,n);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(combinat[multinomial](n, n-i*j, i$j)/j!*
      a(i)^j*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 28 2016
# faster program:
b:= proc(n, i) option remember;
    `if`(i=0 and n=0, 1, `if`(i<=0 or i>n, 0,
    i*b(n-1, i) + (n+i-1)*b(n-1, i-1))) end:
a:= n -> `if`(n<2, n, add(b(n-1, i), i=0..n-1)):
seq(a(n), n=0..40);  # Peter Luschny, Feb 15 2021

nn = 19; CoefficientList[ InverseSeries[ Series[1+2a-E^a, {a, 0, nn}], x], x]*Range[0, nn]! (* Jean-François Alcover, Jul 21 2011 *)
a[ n_] := If[ n < 1, 0, n! SeriesCoefficient[ InverseSeries[ Series[ 1 + 2 x - Exp[x], {x, 0, n}]], n]]; (* Michael Somos, Jun 04 2012 *)
a[n_] := (If[n < 2,n,(column = ConstantArray[0, n - 1]; column[[1]] = 1; For[j = 3, j <= n, j++, column = column * Flatten[{Range[j - 2], ConstantArray[0, (n - j) + 1]}] + Drop[Prepend[column, 0], -1] * Flatten[{Range[j - 1, 2*j - 3], ConstantArray[0, n - j]}];]; Sum[column[[i]], {i, n - 1}]  )]); Table[a[n], {n, 0, 20}] (* Peter Regner, Oct 05 2012, after a formula by Felsenstein (1978) *)
multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&,j]]]/j!*a[i]^j *b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := If[n<2, n, b[n, n-1]]; Table[ a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 07 2016, after Alois P. Heinz *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[sps[m],1Gus Wiseman, Dec 28 2019 *)
(* Lengthy but easy to follow *)
  lead[, n /; n < 3] := 0
  lead[h_, n_] := Module[{p, i},
        p = Position[h, {_}];
        Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
        ]
  follow[h_, n_] := Module[{r, i},
        r = Replace[Position[h, {_}], {a__} -> {a, -1}, 1];
        Sum[Insert[h, n, r[[i]]], {i, Length[r]}]
        ]
  marry[, n /; n < 3] := 0
  marry[h_, n_] := Module[{p, i},
        p = Position[h, _Integer];
        Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
        ]
  extend[a_ + b_, n_] := extend[a, n] + extend[b, n]
  extend[a_, n_] := lead[a, n] + follow[a, n] + marry[a, n]
  hierarchies[1] := hierarchies[1] = extend[hier[{}], 1]
  hierarchies[n_] := hierarchies[n] = extend[hierarchies[n - 1], n] (* Daniel Geisler, Aug 22 2022 *)

a(n):=if n=1 then 1 else sum((n+k-1)!*sum(1/(k-j)!*sum((2^i*(-1)^(i)*stirling2(n+j-i-1,j-i))/((n+j-i-1)!*i!),i,0,j),j,1,k),k,1,n-1); /* Vladimir Kruchinin, Jan 28 2012 */

{a(n) = local(A); if( n<0, 0, for( i=1, n, A = Pol(exp(A + x * O(x^i)) - A + x - 1)); n! * polcoeff(A, n))}; /* Michael Somos, Jan 15 2004 */

{a(n) = my(A); if( n<0, 0, A = O(x); for( i=1, n, A = intformal( 1 / (1 + x - 2*A))); n! * polcoeff(A, n))}; /* Michael Somos, Oct 25 2014 */

{a(n) = n! * polcoeff(serreverse(1+2*x - exp(x +x^2*O(x^n))), n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Oct 27 2014

\p100 \\ set precision
{A=Vec(sum(n=0, 600, 1.*x/prod(k=0, n, 2 - k*x + O(x^31))))}
for(n=0, 25, print1(if(n<1,0,round(A[n])),", ")) \\ Paul D. Hanna, Oct 27 2014

from functools import lru_cache
from math import comb
@lru_cache(maxsize=None)
def A000311(n): return n if n <= 1 else -(n-1)*A000311(n-1)+comb(n,m:=n+1>>1)*(0 if n&1 else A000311(m)**2) + (sum(comb(n,i)*A000311(i)*A000311(n-i) for i in range(1,m))<<1) # Chai Wah Wu, Nov 10 2022

E.g.f. A(x) satisfies exp A(x) = 2*A(x) - x + 1.
a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).
a(1)=1; for n>1, a(n) = -(n-1) * a(n-1) + Sum_{k=1..n-1} binomial(n, k) * a(k) * a(n-k). - Michael Somos, Jun 04 2012
From the umbral operator L in A135494 acting on x^n comes, umbrally, (a(.) + x)^n = (n * x^(n-1) / 2) - (x^n / 2) + Sum_{j>=1} j^(j-1) * (2^(-j) / j!) * exp(-j/2) * (x + j/2)^n giving a(n) = 2^(-n) * Sum_{j>=1} j^(n-1) * ((j/2) * exp(-1/2))^j / j! for n > 1. - Tom Copeland, Feb 11 2008
Let h(x) = 1/(2-exp(x)), an e.g.f. for A000670, then the n-th term of A000311 is given by ((h(x)*d/dx)^n)x evaluated at x=0, i.e., A(x) = exp(x*a(.)) = exp(x*h(u)*d/du) u evaluated at u=0. Also, dA(x)/dx = h(A(x)). - Tom Copeland, Sep 05 2011 (The autonomous differential eqn. here is also on p. 59 of Jones. - Tom Copeland, Dec 16 2019)
A134991 gives (b.+c.)^n = 0^n, for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - Tom Copeland, Oct 19 2011
a(n) = Sum_{k=1..n-1} (n+k-1)!*Sum_{j=1..k} (1/(k-j)!)*Sum_{i=0..j} 2^i*(-1)^i*Stirling2(n+j-i-1, j-i)/((n+j-i-1)!*i!), n>1, a(0)=0, a(1)=1. - Vladimir Kruchinin, Jan 28 2012
Using L. Comtet's identity and D. Wasserman's explicit formula for the associated Stirling numbers of second kind (A008299) one gets: a(n) = Sum_{m=1..n-1} Sum_{i=0..m} (-1)^i * binomial(n+m-1,i) * Sum_{j=0..m-i} (-1)^j * ((m-i-j)^(n+m-1-i))/(j! * (m-i-j)!). - Peter Regner, Oct 08 2012
G.f.: x/Q(0), where Q(k) = 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
G.f.: x*Q(0), where Q(k) = 1 - x*(k+1)/(x*(k+1) - (1-k*x)*(1-x-k*x)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 11 2013
a(n) ~ n^(n-1) / (sqrt(2) * exp(n) * (2*log(2)-1)^(n-1/2)). - Vaclav Kotesovec, Jan 05 2014
E.g.f. A(x) satisfies d/dx A(x) = 1 / (1 + x - 2 * A(x)). - Michael Somos, Oct 25 2014
O.g.f.: Sum_{n>=0} x / Product_{k=0..n} (2 - k*x). - Paul D. Hanna, Oct 27 2014
E.g.f.: (x - 1 - 2 LambertW(-exp((x-1)/2) / 2)) / 2. - Vladimir Reshetnikov, Oct 16 2015 (This e.g.f. is given in A135494, the entry alluded to in my 2008 formula, and in A134991 along with its compositional inverse. - Tom Copeland, Jan 24 2018)
a(0) = 0, a(1) = 1; a(n) = n! * [x^n] exp(Sum_{k=1..n-1} a(k)*x^k/k!). - Ilya Gutkovskiy, Oct 17 2017
a(n+1) = Sum_{k=0..n} A269939(n, k) for n >= 1. - Peter Luschny, Feb 15 2021

Name edited by Gus Wiseman, Dec 28 2019

A289501 Number of enriched p-trees of weight n.

Original entry on oeis.org

1, 1, 2, 4, 12, 32, 112, 352, 1296, 4448, 16640, 59968, 231168, 856960, 3334400, 12679424, 49991424, 192890880, 767229952, 2998427648, 12015527936, 47438950400, 191117033472, 760625733632, 3082675150848, 12346305839104, 50223511928832, 202359539335168

Offset: 0

Gus Wiseman, Jul 07 2017

nonn

An enriched p-tree of weight n is either (case 1) the number n itself, or (case 2) a sequence of two or more enriched p-trees, having a weakly decreasing sequence of weights summing to n.

			The a(4) = 12 enriched p-trees are:
  4,
  (31), ((21)1), (((11)1)1), ((111)1),
  (22), (2(11)), ((11)2), ((11)(11)),
  (211), ((11)11),
  (1111).

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

Cf. A052337, A063834, A093637, A196545, A273873, A281145, A300660.

b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> `if`(n=0, 1, 1+b(n, n-1)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 07 2017

a[n_]:=a[n]=1+Sum[Times@@a/@y,{y,Rest[IntegerPartitions[n]]}];
Array[a,20]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1,
     If[i<1, 0, b[n, i-1] + a[i] b[n-i, Min[n-i, i]]]];
a[n_] := If[n == 0, 1, 1 + b[n, n-1]];
a /@ Range[0, 30] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(1/prod(k=1, n-1, 1 - v[k]*x^k + O(x*x^n)), n)); concat([1], v)} \\ Andrew Howroyd, Aug 26 2018

O.g.f.: (1/(1-x) + Product_{i>0} 1/(1-a(i)*x^i))/2.

A273873 Number of strict trees of weight n.

Original entry on oeis.org

1, 1, 2, 3, 6, 12, 28, 65, 166, 412, 1076, 2806, 7524, 20020, 54744, 148417, 410078, 1126732, 3144500, 8728570, 24555900, 68713420, 194469616, 548088278, 1559301428, 4418131108, 12628267512, 35957541462, 103150588492, 294924202032, 848878072440, 2435729999665

Offset: 1

Gus Wiseman, Jun 01 2016

nonn

A strict tree t is either (case 1) a positive integer t = n, or (case 2) a set t = {t1, t2, ..., tk} of two or more strict trees (i.e. branches) with distinct weights, where the weight of a strict tree in the second case is the sum of the weights of its branches; hence the multiset of weights is a strict integer partition of n. For example, {{{{{2,1},1},2},3},{4,{2,1}},{2,1},1} is a strict tree of weight 20.

			a(6) = 12: {6, (51), (42), ((41)1), (321), ((31)2), ((32)1), (((31)1)1), ((21)21), (((21)1)2), (((21)2)1), ((((21)1)1)1)}.

Alois P. Heinz, Table of n, a(n) for n = 1..2000
H. Gingold and A. Knopfmacher, Analytic properties of power product expansions, Canad. J. Math. 47(1995), 1219-1239
Gus Wiseman, Comcategories and Multiorders, (pdf version)
Gus Wiseman, All strict trees n=1..6.

Cf. A196545 (weakly ordered plane trees); A220418, A220420 (power product expansions); A271619, A063834 (twice partitioned numbers), A289501.

b:= proc(n, i) option remember; `if`(i*(i+1)/2 1+b(n, n-1):
seq(a(n), n=1..35);  # Alois P. Heinz, Jun 02 2016

STE[n_Integer?Positive]:=STE[n]=1+Plus@@Map[Function[ptn,Times@@STE/@ptn],Select[IntegerPartitions[n],And[Length[#]>1,UnsameQ@@#]&]];
Array[STE,30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[i(i + 1)/2 < n, 0,
     If[n == 0, 1, b[n, i - 1] + b[n - i, Min[n - i, i - 1]] a[i]]];
a[n_] := If[n == 0, 1, 1 + b[n, n - 1]];
a /@ Range[35] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(prod(k=1, n-1, 1 + v[k]*x^k + O(x*x^n)), n)); v} \\ Andrew Howroyd, Aug 26 2018

Sum_{g(t)=y} (-1)^{d(t)} = mu(|y|<={y_1,...,y_k}), where mu is the Mobius function of the multiorder of integer partitions, g(t) is the multiset of leaves of a strict tree t, and d(t) is the number of branchings.

Strict trees are closely related to the coefficients appearing in a(i) = Sum_y c(y_1)*...*c(y_k) where Sum_i c(i)*x^i = Prod_i (1 + a(i)*x^i). The latter identity is the formal power product expansion (PPE) of an (ordinary) generating function.

A299202 Moebius function of the multiorder of integer partitions indexed by their Heinz numbers.

Original entry on oeis.org

0, 1, 1, -1, 1, -1, 1, 0, -1, -1, 1, 2, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, 0, 1, 1, 3, 1, 0, -1, -1, -1, -1, 1, -1, -1, -1, 1, 2, 1, 1, 1, -1, 1, 0, -1, 1, -1, 1, 1, -1, -1, -1, -1, -1, 1, -3, 1, -1, 2, 0, -1, 2, 1, 1, -1, 3, 1, 2, 1, -1, 1, 1, -1, 2, 1, 1, -1, -1, 1, -5, -1, -1, -1, -1, 1, -4

Offset: 1

Gus Wiseman, Feb 05 2018

sign

By convention, mu() = 0.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Heinz number of (2,1,1) is 12, so mu(2,1,1) = a(12) = 2.

Gus Wiseman, Comcategories and Multiorders

Cf. A000041, A063834, A112798, A196545, A273873, A281145, A289501, A290261, A296150, A299200, A299201, A299203.

nn=120;
ptns=Table[If[n===1,{},Join@@Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]],{n,nn}];
tris=Join@@Map[Tuples[IntegerPartitions/@#]&,ptns];
mu[y_]:=mu[y]=If[Length[y]===1,1,-Sum[Times@@mu/@t,{t,Select[tris,And[Length[#]>1,Sort[Join@@#,Greater]===y]&]}]];
mu/@ptns

mu(y) = Sum_{g(t)=y} (-1)^d(t), where the sum is over all enriched p-trees (A289501, A299203) whose multiset of leaves is the integer partition y, and d(t) is the number of non-leaf nodes in t.

A299200 Number of twice-partitions whose domain is the integer partition with Heinz number n.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 5, 1, 4, 3, 7, 2, 11, 5, 6, 1, 15, 4, 22, 3, 10, 7, 30, 2, 9, 11, 8, 5, 42, 6, 56, 1, 14, 15, 15, 4, 77, 22, 22, 3, 101, 10, 135, 7, 12, 30, 176, 2, 25, 9, 30, 11, 231, 8, 21, 5, 44, 42, 297, 6, 385, 56, 20, 1, 33, 14, 490, 15, 60, 15, 627, 4

Offset: 1

Gus Wiseman, Feb 05 2018

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The a(15) = 6 twice-partitions: (3)(2), (3)(11), (21)(2), (21)(11), (111)(2), (111)(11).

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A000041, A063834, A112798, A196545, A273873, A281145, A289501, A290261, A296150, A299201, A299202, A299203.

Cf. A000720, A003964.

with(numtheory): with(combinat):
a:= n-> mul(numbpart(pi(i[1]))^i[2], i=ifactors(n)[2]):
seq(a(n), n=1..82);  # Alois P. Heinz, Jan 14 2021

Table[Times@@Cases[FactorInteger[n],{p_,k_}:>PartitionsP[PrimePi[p]]^k],{n,100}]

a(n) = {my(f = factor(n)); for (k=1, #f~, f[k, 1] = numbpart(primepi(f[k, 1]));); factorback(f);} \\ Michel Marcus, Feb 26 2018

Multiplicative with a(prime(n)) = A000041(n).

A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 5, 17, 12, 5, 12, 73, 95, 44, 12, 33, 369, 721, 512, 168, 33, 90, 1795, 5487, 5480, 2556, 625, 90, 261, 9192, 41945, 58990, 36711, 12306, 2342, 261, 766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766, 2312, 249164, 2483192, 6593103, 7141755, 3965673, 1283624, 258887, 32313, 2312

Offset: 1

Andrew Howroyd, Dec 11 2020

Only the leaves are colored. Equivalence is up to permutation of the colors.

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

			Triangle begins:
    1;
    1,     1;
    2,     3,      2;
    5,    17,     12,      5;
   12,    73,     95,     44,     12;
   33,   369,    721,    512,    168,     33;
   90,  1795,   5487,   5480,   2556,    625,    90;
  261,  9192,  41945,  58990,  36711,  12306,  2342,  261;
  766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766;
  ...
From _Gus Wiseman_, Jan 02 2021: (Start)
Non-isomorphic representatives of the 39 = 5 + 17 + 12 + 5 trees with four colored leaves:
  (1111)      (1112)      (1123)      (1234)
  (1(111))    (1122)      (1(123))    (1(234))
  (11(11))    (1(112))    (11(23))    (12(34))
  ((11)(11))  (11(12))    (12(13))    ((12)(34))
  (1(1(11)))  (1(122))    (2(113))    (1(2(34)))
              (11(22))    (23(11))
              (12(11))    ((11)(23))
              (12(12))    (1(1(23)))
              (2(111))    ((12)(13))
              ((11)(12))  (1(2(13)))
              (1(1(12)))  (2(1(13)))
              ((11)(22))  (2(3(11)))
              (1(1(22)))
              (1(2(11)))
              ((12)(12))
              (1(2(12)))
              (2(1(11)))
(End)

Andrew Howroyd, PARI Functions for Combinatorial Species, v2, Dec 2020.
Wikipedia, Combinatorial species

The case with only one color is A000669.
Counting by nodes gives A318231.
A labeled version is A319376.
Row sums are A330470.
A000311 counts singleton-reduced phylogenetic trees.
A001678 counts unlabeled lone-child-avoiding rooted trees.
A005121 counts chains of set partitions, with maximal case A002846.
A005804 counts phylogenetic rooted trees with n labels.
A060356 counts labeled lone-child-avoiding rooted trees.
A141268 counts lone-child-avoiding rooted trees with leaves summing to n.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A316651 counts lone-child-avoiding rooted trees with normal leaves.
A316652 counts lone-child-avoiding rooted trees with strongly normal leaves.
A330465 counts inequivalent leaf-colorings of phylogenetic rooted trees.
Cf. A196545, A213427, A281118, A289501, A292504, A318812, A319312, A330627.

\\ See link above for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
{my(A=InequivalentColoringsTriangle(cycleIndexSeries(10))); for(n=1, #A~, print(A[n,1..n]))}

A281118 a(1)=1, a(n>1) = number of tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 2, 2, 12, 1, 6, 1, 6, 2, 2, 1, 20, 2, 2, 4, 6, 1, 8, 1, 32, 2, 2, 2, 28, 1, 2, 2, 20, 1, 8, 1, 6, 6, 2, 1, 76, 2, 6, 2, 6, 1, 20, 2, 20, 2, 2, 1, 38, 1, 2, 6, 112, 2, 8, 1, 6, 2, 8, 1, 116, 1, 2, 6, 6, 2, 8, 1, 76, 12, 2, 1

Offset: 1

Gus Wiseman, Jan 15 2017

nonn

A tree-factorization of n>=2 is either (case 1) the number n or (case 2) a sequence of two or more tree-factorizations, one of each part of a weakly increasing factorization of n. These are rooted plane trees and the ordering of branches is important. For example, {{2,2},9}, {2,{2,9}}, {{2,2},{3,3}}, {6,{2,3}}, and {{2,3},6} are distinct tree-factorizations of 36, but {9,{2,2}}, {{2,9},2}, and {{3,3},{2,2}} are not.

a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(30)=8 tree-factorizations are 30, 2*15, 2*(3*5), 3*10, 3*(2*5), 5*6, 5*(2*3), 2*3*5.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A001055, A063834, A196545, A262673, A273873, A281113, A289501.

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
treefacs[n_]:=If[n<=1,{{}},Prepend[Join@@Function[q,Tuples[treefacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];
Table[Length[treefacs[n]],{n,2,83}]

seq(n)={my(v=vector(n), w=vector(n)); w[1]=v[1]=1; for(k=2, n, w[k]=v[k]+1; forstep(j=n\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j] += w[k]^e*v[i]))); w} \\ Andrew Howroyd, Nov 18 2018

a(p^n) = A289501(n) for prime p. - Andrew Howroyd, Nov 18 2018

A281145 Number of same-trees of weight n.

Original entry on oeis.org

1, 2, 2, 6, 2, 14, 2, 54, 10, 38, 2, 494, 2, 134, 42, 4470, 2, 3422, 2, 10262, 138, 2054, 2, 490926, 34, 8198, 1514, 314294, 2, 628318, 2, 30229110, 2058, 131078, 162, 150147342, 2, 524294, 8202, 628073814, 2, 109952254, 2, 371210294, 207370, 8388614, 2

Offset: 1

Gus Wiseman, Jan 15 2017

nonn

A same-tree is either: (case 1) a positive integer, or (case 2) a finite sequence of two or more same-trees all having the same weight, where the weight in case 2 is the sum of weights.

			The a(6)=14 same-trees are:
6,
(33),
(222),
(3(111)), ((111)3),
(22(11)), (2(11)2), ((11)22),
(2(11)(11)), ((11)2(11)), ((11)(11)2),
((111)(111)), ((11)(11)(11)), (111111).
The a(9)=10 same-trees are:
9,
(333),
(33(111)), (3(111)3), ((111)33),
(3(111)(111)), ((111)3(111)), ((111)(111)3),
((111)(111)(111)), (111111111).

G. C. Greubel, Table of n, a(n) for n = 1..4000

Cf. A196545, A260685, A273873, A275870, A006241.

a[n_]:=1+DivisorSum[n,b[#]^(n/#)&]-b[n]/.b->a;
Array[a,47]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sumdiv(n, d, v[n/d]^d)); v} \\ Andrew Howroyd, Aug 20 2018

a(n) = 1 + Sum a(d)^(n/d) where the sum is over divisors less than n.

cp's OEIS Frontend

A296150 Triangle whose n-th row is the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A063834 Twice partitioned numbers: the number of ways a number can be partitioned into not necessarily different parts and each part is again so partitioned.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A000311 Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A289501 Number of enriched p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A273873 Number of strict trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A299202 Moebius function of the multiorder of integer partitions indexed by their Heinz numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs