A137731 -id:A137731 - cp's OEIS frontend

A137732 Repeated set splitting, unlabeled elements. Repeated integer partitioning into two parts.

1, 1, 2, 5, 16, 55, 224, 935, 4400, 21262, 111624, 596805, 3457354, 20147882, 125455512, 792576243, 5277532388, 35519373064, 252120178596, 1800810613940, 13492153025558, 102095379031327, 804122472505530, 6395239610004277

Offset: 1

Thomas Wieder, Feb 09 2008

nonn

Consider a set of n unlabeled elements. Form all splittings into two subsets. Consider the resulting sets and perform the splittings on all their subsets and so on. In order to understand this structure, imagine that each of the two parts can be put either 'to the left or to the right.
E.g., (4) gives (3,1) and (1,3). That is, the order of parts counts. H(n+1) = number of splittings of the n-set {*,*,...,*} composed of n elements '*'. E.g., H(4)=5 because we have (***), (**,*), (*,**), ((*,*),*), (*,(*,*)).
Equivalently, we have (3), (2,1), (1,2), ((1,1),1), (1,(1,1)). The case for labeled elements is described by A137731. This structure is related to the Double Factorials A000142 for which the recurrence is a(n) = Sum_{k=1..n-1} binomial(n-1,k)*a(k)*a(n-k), with a(1)=1, a(2)=1.
See also A137591 = Number of parenthesizings of products formed by n factors assuming noncommutativity and nonassociativity. See also the Catalan numbers A000108.

			(1)
(2), (1,1).
(3), (2,1), (1,2), ((1,1),1), (1,(1,1)).
(4), (3,1), (1,3), ((2,1),1), (1,(2,1)), ((1,2),1), (1,(1,2)),
(((1,1),1),1), (1,((1,1),1)), ((1,(1,1)),1), (1,(1,(1,1))),
(2,2), ((1,1),2), (2,(1,1)), ((1,1),(1,1)), ((1,1),(1,1)).
Observe that for (4) we obtain ((1,1),(1,1)), ((1,1),(1,1)) twice.

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

Cf. A000108, A000142, A137591, A137731.

A008284 := proc(n,k) combinat[numbpart](n,k)-combinat[numbpart](n,k-1) ; end: A137732 := proc(n) option remember ; local i ; if n =1 then 1; else add(A008284(n-1,k)*procname(k)*procname(n-k),k=1..n-1) ; fi ; end: for n from 1 to 40 do printf("%d,",A137732(n)) ; od: # R. J. Mathar, Aug 25 2008

p[, 1] = 1; p[n, k_] /; 1 <= k <= n := p[n, k] = Sum[p[n-i, k-1], {i, 1, n-1}] - Sum[p[n-i, k], {i, 1, k-1}]; p[, ] = 0; a[1] = 1; a[n_] := a[n] = Sum[p[n-1, k]*a[k]*a[n-k], {k, 1, n-1}]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 03 2017 *)

a(n) = Sum_{k=1..n-1} p(n-1,k)*a(k)*a(n-k), with a(1)=1 and where p(n,k) denotes the number of integer partitions of n into k parts.

Extended by R. J. Mathar, Aug 25 2008

A143140 Total number of all repeated partitions of the n-set {1,2,3,...,n}.

Original entry on oeis.org

1, 1, 2, 11, 83, 787, 8965, 119170, 1810450, 30942699, 587606593, 12274606775, 279715819531, 6905395692990, 183588212652382, 5229549060414223, 158895798308201987, 5129671140284343035, 175343720698891809337, 6326623756471457351814, 240286954202031694593966

Offset: 0

Thomas Wieder, Jul 27 2008

nonn

The corresponding unlabeled counterpart is sequence A143141.
See also A131407 = Repeated set partitions or nested set partitions. Possible coalitions among n persons.
See also A137731 = Repeated set splitting, labeled elements.
a(n) is the number of set partitions of the n-set plus sum of a(k) for all the k-sets (1 < k < n) that are contained (with multiplicity) in these set partitions. - Alois P. Heinz, Jul 27 2012

			a(1) = |{{{1}}}| = 1.
a(2) = |{{{1,2}}, {{1},{2}}}| = 2.
a(3) = |{{{1,2,3}}, {{1,2},{3}}, {{2},{1,3}}, {{1},{2,3}}, {{1},{2},{3}}}| + 3*a(2) = 5 + 3*2 = 11.

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

Cf. A000110, A131407, A137731, A143141.

with(combinat):
a:= proc(n) option remember;
      bell(n)+ add(a(k)*binomial(n, k)*bell(n-k), k=2..n-1)
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jul 26 2012

a[n_] := a[n] = BellB[n]+Sum[a[k]*Binomial[n, k]*BellB[n-k], {k, 2, n-1}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 05 2017, after Alois P. Heinz *)

a(n) = Bell(n) + Sum_{k=2..n-1} C(n,k)*Bell(n-k)*a(k) with Bell = A000110. - Alois P. Heinz, Jul 26 2012

Edited by Thomas Wieder, Jul 26 2012
More terms from Alois P. Heinz, Jul 26 2012
a(0)=1 prepended by Alois P. Heinz, Sep 22 2016

A317275 a(1) = 1; a(n) = Sum_{k=1..n-1} |Stirling1(n-1,k)|a(k)a(n-k).

Original entry on oeis.org

1, 1, 2, 9, 97, 3105, 409318, 301069244, 1523141657289, 61447697339843710, 22299766257043761657829, 80922067241038150103930448880, 3230152742688615187688660954252643194, 1547248455508510864175770056662224501358437847

Offset: 1

Ilya Gutkovskiy, Jul 25 2018

nonn

Cf. A008275, A137731, A143805.

a[n_] := a[n] = Sum[Abs[StirlingS1[n - 1, k]] a[k] a[n - k], {k, n - 1}]; a[1] = 1; Table[a[n], {n, 14}]

cp's OEIS Frontend

A137732 Repeated set splitting, unlabeled elements. Repeated integer partitioning into two parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A143140 Total number of all repeated partitions of the n-set {1,2,3,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A317275 a(1) = 1; a(n) = Sum_{k=1..n-1} |Stirling1(n-1,k)|a(k)a(n-k).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

cp's OEIS Frontend

A137732 Repeated set splitting, unlabeled elements. Repeated integer partitioning into two parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A143140 Total number of all repeated partitions of the n-set {1,2,3,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A317275 a(1) = 1; a(n) = Sum_{k=1..n-1} |Stirling1(n-1,k)|*a(k)*a(n-k).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A317275 a(1) = 1; a(n) = Sum_{k=1..n-1} |Stirling1(n-1,k)|a(k)a(n-k).