A137591 -id:A137591 - cp's OEIS frontend

A137731 Repeated set splitting, labeled elements.

1, 1, 2, 7, 40, 355, 4720, 91690, 2559980, 101724390, 5724370860, 455400049575, 51225573119870, 8155535394029685, 1840116104410154380, 589128078915179209630, 267942956094193363173030, 173296035183231212307098790, 159532934947213401229226873410

Offset: 1

Thomas Wieder, Feb 09 2008

nonn

Consider a set of n labeled elements. Form all splittings into two subsets. Consider the resulting sets and perform the splittings on all their subsets and so on. a(n+1) = number of splittings of the n-set {1,2,3,...,n}.
E.g., a(4) = 7 because we have {abc}, {ab}{c}, {ac}{b}, {bc}{a}, {{a}{b}}{c}, {{a}{c}}{b}, {{b}{c}}{a}. The case for unlabeled elements is described by A137732. This structure is related to the Double Factorials A000142 for which the recurrence is a(n) = Sum_{k=1..n-1} C(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.

			{a}.
{ab}, {a}{b}.
{abc}, {ab}{c}, {ac}{b}, {bc}{a}, {{a}{b}}{c}, {{a}{c}}{b}, {{b}{c}}{a}.
{abcd}, {abc}{d}, {abd}{c}, {acd}{b}, {bcd}{a},
{{ab}{c}}{d}, {{ab}{d}}{c}, {{ac}{d}}{b}, {{bc}{d}}{a},
{{ac}{b}}{d}, {{ad}{b}}{c}, {{ad}{c}}{b}, {{bd}{c}}{a},
{{bc}{a}}{d}, {{bd}{a}}{c}, {{cd}{a}}{b}, {{cd}{b}}{a},
{{{a}{b}}{c}}{d}, {{{a}{b}}{d}}{c}, {{{a}{c}}{d}}{b}, {{{b}{c}}{d}}{a},
{{{a}{c}}{b}}{d}, {{{a}{d}}{b}}{c}, {{{a}{d}}{c}}{b}, {{{b}{d}}{c}}{a},
{{{b}{c}}{a}}{d}, {{{b}{d}}{a}}{c}, {{{c}{d}}{a}}{b}, {{{c}{d}}{b}}{a},
{{ab}{cd}}, {{ac}{bd}}, {{ad}{bc}},
{{{a}{b}}{cd}}, {{{a}{c}}{bd}}, {{{a}{d}}{bc}},
{{ab}{{c}{d}}}, {{ac}{{b}{d}}}, {{ad}{{b}{c}}},
{{{a}{b}}{{c}{d}}}, {{{a}{c}}{{b}{d}}}, {{{a}{d}}{{b}{c}}}.

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

Cf. A000108, A000142, A137591, A137732.

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

a[1] = 1; a[n_] := a[n] = Sum[StirlingS2[n-1, k]*a[k]*a[n-k], {k, 1, n-1}]; Array[a, 20] (* Jean-François Alcover, May 18 2018 *)

from functools import cache
from sympy.functions.combinatorial.numbers import stirling as S2
@cache
def a(n): return sum(S2(n-1,k)*a(k)*a(n-k) for k in range(1, n)) if n > 1 else 1
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, May 05 2023

a(n) = Sum_{k=1..n-1} S2(n-1,k)*a(k)*a(n-k) with a(1)=1, where S2(n,k) denotes the Stirling numbers of the second kind.

Extended by R. J. Mathar, Aug 25 2008

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

Original entry on oeis.org

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

cp's OEIS Frontend

A137731 Repeated set splitting, labeled elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions