login
Repeated set splitting, labeled elements.
4

%I #26 May 05 2023 12:38:44

%S 1,1,2,7,40,355,4720,91690,2559980,101724390,5724370860,455400049575,

%T 51225573119870,8155535394029685,1840116104410154380,

%U 589128078915179209630,267942956094193363173030,173296035183231212307098790,159532934947213401229226873410

%N Repeated set splitting, labeled elements.

%C 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}.

%C 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.

%C See also A137591 = Number of parenthesizings of products formed by n factors assuming noncommutativity and nonassociativity. See also the Catalan numbers A000108.

%H Alois P. Heinz, <a href="/A137731/b137731.txt">Table of n, a(n) for n = 1..70</a>

%F 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.

%e {a}.

%e {ab}, {a}{b}.

%e {abc}, {ab}{c}, {ac}{b}, {bc}{a}, {{a}{b}}{c}, {{a}{c}}{b}, {{b}{c}}{a}.

%e {abcd}, {abc}{d}, {abd}{c}, {acd}{b}, {bcd}{a},

%e {{ab}{c}}{d}, {{ab}{d}}{c}, {{ac}{d}}{b}, {{bc}{d}}{a},

%e {{ac}{b}}{d}, {{ad}{b}}{c}, {{ad}{c}}{b}, {{bd}{c}}{a},

%e {{bc}{a}}{d}, {{bd}{a}}{c}, {{cd}{a}}{b}, {{cd}{b}}{a},

%e {{{a}{b}}{c}}{d}, {{{a}{b}}{d}}{c}, {{{a}{c}}{d}}{b}, {{{b}{c}}{d}}{a},

%e {{{a}{c}}{b}}{d}, {{{a}{d}}{b}}{c}, {{{a}{d}}{c}}{b}, {{{b}{d}}{c}}{a},

%e {{{b}{c}}{a}}{d}, {{{b}{d}}{a}}{c}, {{{c}{d}}{a}}{b}, {{{c}{d}}{b}}{a},

%e {{ab}{cd}}, {{ac}{bd}}, {{ad}{bc}},

%e {{{a}{b}}{cd}}, {{{a}{c}}{bd}}, {{{a}{d}}{bc}},

%e {{ab}{{c}{d}}}, {{ac}{{b}{d}}}, {{ad}{{b}{c}}},

%e {{{a}{b}}{{c}{d}}}, {{{a}{c}}{{b}{d}}}, {{{a}{d}}{{b}{c}}}.

%p 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

%t 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 *)

%o (Python)

%o from functools import cache

%o from sympy.functions.combinatorial.numbers import stirling as S2

%o @cache

%o 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

%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, May 05 2023

%Y Cf. A000108, A000142, A137591, A137732.

%K nonn

%O 1,3

%A _Thomas Wieder_, Feb 09 2008

%E Extended by _R. J. Mathar_, Aug 25 2008