A137732 -id:A137732 - 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

A141799 Number of repeated integer partitions of n.

Original entry on oeis.org

1, 3, 8, 25, 66, 192, 511, 1418, 3812, 10383, 27958, 75758, 204215, 551821, 1488561, 4018722, 10842422, 29262357, 78955472, 213063551, 574905487, 1551325859, 4185959285, 11295211039, 30478118079, 82240300045, 221911189754, 598790247900, 1615732588962

Offset: 1

Thomas Wieder, Jul 05 2008

nonn

An integer n can be partitioned into P(n) partitions P([n],i) where i=1,...,P(n) counts the partitions. The partition P([n],i) consists of T(n,i) integer parts t(i,j) with j=1,...,T(n,i). Now we perform on each t(i,j) an integer partition again and arrive at new partitions. Their parts can be partitioned again and so forth. We count such repeated partitions of n. One convention is necessary to avoid an infinite loop: The trivial partition P([n],1)=[n] will not be partitioned again but just counted once (and therefore we also have a(1)=1).

			For the integers 1, 2, 3 and 4 we have
[1] -> 1,
thus a(1)=1.
[2] -> 1,
[1,1] => [1] ->, [1] -> 1.
thus a(2)=3.
[3] -> 1,
[1,2] => [1] -> 1, [2] -> 3,
[1,1,1] => [1] -> 1, [1] -> 1, [1] -> 1,
thus a(3)=8.
[4] -> 1,
[1,3] => [1] -> 1, [3] -> 8,
[2,2] => [2] -> 3, [2] -> 3,
[1,1,2] => [1] -> 1, [1] -> 1, [2] -> 3,
[1,1,1,1] => [1] -> 1, [1] -> 1, [1] -> 1, [1] -> 1,
thus a(4)=25.

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

Cf. A000041, A131407, A131408, A137732, A246828.

A141799 := proc(n) option remember ; local a,P,i,p ; if n =1 then 1; else a := 0 ; for P in combinat[partition](n) do if nops(P) > 1 then for i in P do a := a+procname(i) ; od: else a := a+1 ; fi; od: RETURN(a) ; fi ; end: for n from 1 to 40 do printf("%d,",A141799(n)) ; od: # R. J. Mathar, Aug 25 2008
# second Maple program
a:= proc(n) option remember;
      1+ `if`(n>1, b(n, n-1)[2], 0)
    end:
b:= proc(n, i) option remember; local f, g;
      if n=0 or i=1 then [1, n]
    else f:= b(n, i-1); g:= `if`(i>n, [0, 0], b(n-i, i));
         [f[1]+g[1], f[2]+g[2] +g[1]*a(i)]
      fi
    end:
seq(a(n), n=1..40); # Alois P. Heinz, Apr 05 2012

a[n_] := a[n] = 1 + If[n>1, b[n, n-1][[2]], 0]; b[n_, i_] := b[n, i] = Module[{f, g}, If[n == 0 || i == 1, {1, n}, f = b[n, i-1]; g = If[i>n, {0, 0}, b[n-i, i]]; {f[[1]] + g[[1]], f[[2]] + g[[2]] + g[[1]]*a[i]}]]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *)

Let sum_{i=1}^P(n) denote the sum over all integer partitions P([n],i) of n. Let sum_{j=1}^T(i,j) denote the sum over all parts of the i-th integer partition. Then we have the recursive formula 1 if t(i,j)=n a(n) = sum_{i=1}^P(n) sum_{j=1}^T(i,j) { a(t(i,j)) else. E.g. a(4)=25 because [4] contributes 1, [1,3] contributes a(1)+a(3)=1+8=9, [2,2] contributes a(2)+a(2)=3+3=6, [1,1,2] contributes a(1)+a(1)+a(2)=1+1+3=5, [1,1,1,1] contributes a(1)+a(1)+a(1)+a(1)=1+1+1+1=4 which gives in total 25.

a(n) ~ c * d^n, where d = 2.69832910647421123126399866... (see A246828), c = 0.5088820425072641934222229579416714164592334575899644931509447692360546... . - Vaclav Kotesovec, Sep 04 2014

Extended by R. J. Mathar, Aug 25 2008

A143141 Total number of all repeated partitions of the integer n and its parts down to parts equal to 1. Essentially first differences of A055887.

Original entry on oeis.org

1, 2, 5, 14, 37, 101, 271, 733, 1976, 5334, 14390, 38833, 104779, 282734, 762903, 2058571, 5554692, 14988400, 40443620, 109130216, 294469216, 794574883, 2144024501, 5785283758, 15610599502, 42122535067, 113660462337, 306693333868, 827559549428, 2233028019698

Offset: 1

Thomas Wieder, Jul 27 2008

nonn

Start from the A000041(n) integer partitions P(n,i,s) of the integer n at stage s=1.
The index i=1,...,A000041(n) denotes the different partitions.
We call the index s the partition stage and increase it by one as we sub-partition the partitions of a previous stage.
Each P(n,i,s) is a set P(n,i,s)={t(n,1,j,s)),...,t(P,i,j,s),...,t(P,i,J,s)} of parts t(P,i,j,s) of S.
The index j is attached to the parts of a partition P(n,i,s). 1<=j<=n since there are at most n parts.
Now apply the set partition process on every P(n,i,s=1).
That is, each t(n,i,j,s=1) is subjected to a further partitioning.
We get partitions P(t'(n,i,j,1),i',j',2)={t'(t(n,i,j,1),i',1,2),...,t'(t(n,i,j,1), i',j',2),...,t'(t(n,i,j,1),i',J',2)} of the second partition stage.
We repeat this partitioning process on each part t'(i,j',2) until we arrive at parts equal to 1 which cannot be partitioned any further.
We may speak of the full decomposition F of n into parts.
The sequence counts the total number of partitions of all stages of the full decomposition of n.
Note that n is its own partition, e.g. P(n=3,i=1,s=1)={3} is an integer partition of n=3.
We do not apply the repeated partitioning on the partition P(n,i,s)={n} (otherwise an infinite loop would arise).
For n=1 and n=2 there is no second partition stage: s stays at s=1.
The corresponding labeled counterpart is sequence A143140.

			n=1:
[[1]]
n=2:
[[2], [1, 1]]
n=3:
[[3], [2, 1], [1, 1, 1]], [[2], [1, 1]]
n=4 in more detail:
[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]], <- stage s=1, partition of 4
[[3], [2, 1], [1, 1, 1]], <- stage s=2 partitioning the first 3 of the 2nd partition
[[2], [1, 1]], <- stage s=2 partitioning the first 2 of the 3rd partition
[[2], [1, 1]], <- stage s=2 partitioning the second 2 of the 3rd partition
[[2], [1, 1]] <- stage s=2 partitioning the first 2 of the 4th partition
a(4) = 14 = 5 (from s=1)+9 (from s=2).

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

Cf. A143140, A055887, A000041, A141799, A131408, A137732.

A055887 := proc(n) option remember ; if n = 0 then 1; else add(combinat[numbpart](k)*procname(n-k),k=1..n) ; fi; end: A143141 := proc(n) if n = 1 then 1; else A055887(n)-A055887(n-1) ; fi; end: seq(A143141(n),n=1..20) ;

b[n_] := b[n] = Sum[PartitionsP[k]*b[n-k], {k, 1, n}]; b[0]=1; A055887 = Table[b[n], {n, 0, 30}]; Join[{1}, Rest[Differences[A055887]]] (* Jean-François Alcover, Feb 05 2017 *)

a(n) = A055887(n) - A055887(n-1), n>1.

Edited and 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

A141799 Number of repeated integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A143141 Total number of all repeated partitions of the integer n and its parts down to parts equal to 1. Essentially first differences of A055887.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions