cp's OEIS Frontend

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

%I A137732 #12 Feb 03 2017 04:13:11
%S A137732 1,1,2,5,16,55,224,935,4400,21262,111624,596805,3457354,20147882,
%T A137732 125455512,792576243,5277532388,35519373064,252120178596,
%U A137732 1800810613940,13492153025558,102095379031327,804122472505530,6395239610004277
%N A137732 Repeated set splitting, unlabeled elements. Repeated integer partitioning into two parts.
%C A137732 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.
%C A137732 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 (***), (**,*), (*,**), ((*,*),*), (*,(*,*)).
%C A137732 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.
%C A137732 See also A137591 = Number of parenthesizings of products formed by n factors assuming noncommutativity and nonassociativity. See also the Catalan numbers A000108.
%H A137732 Alois P. Heinz, <a href="/A137732/b137732.txt">Table of n, a(n) for n = 1..250</a>
%F A137732 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.
%e A137732 (1)
%e A137732 (2), (1,1).
%e A137732 (3), (2,1), (1,2), ((1,1),1), (1,(1,1)).
%e A137732 (4), (3,1), (1,3), ((2,1),1), (1,(2,1)), ((1,2),1), (1,(1,2)),
%e A137732 (((1,1),1),1), (1,((1,1),1)), ((1,(1,1)),1), (1,(1,(1,1))),
%e A137732 (2,2), ((1,1),2), (2,(1,1)), ((1,1),(1,1)), ((1,1),(1,1)).
%e A137732 Observe that for (4) we obtain ((1,1),(1,1)), ((1,1),(1,1)) twice.
%p A137732 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
%t A137732 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 *)
%o A137732 Sub A137714() ' This is a VBA program.
%o A137732 Dim n As Long, nstart As Long, nend As Long
%o A137732 Dim k As Long, HSumme As Long, H(100) As Long
%o A137732 nstart = 2
%o A137732 nend = 15
%o A137732 H(1) = 1
%o A137732 For n = nstart To nend
%o A137732 HSumme = 0
%o A137732 For k = 1 To n - 1
%o A137732 HSumme = HSumme + ZahlPartitionen(n - 1, k) * H(k) * H(n - k)
%o A137732 Next k
%o A137732 H(n) = HSumme
%o A137732 Next n
%o A137732 Debug.Print H(1), H(2), H(3), H(4), H(5), H(6), H(7), H(8), H(9), H(10), H(11), H(12), H(13), H(14), H(15)
%o A137732 End Sub
%o A137732 Public Function ZahlPartitionen(n As Long, k As Long)
%o A137732 Dim imsgbox As Integer
%o A137732 If n > 2147483648# Or k > 2147483648# Then
%o A137732 imsgbox = MsgBox("n and k need to be smaller than 2147483648 !", vbOKOnly, "ZahlPartitionen")
%o A137732 End
%o A137732 End If
%o A137732 If (n < 0 Or k < 0) Then
%o A137732 imsgbox = MsgBox("n and k need to be greater than 0 !", vbOKOnly, "ZahlPartitionen")
%o A137732 End
%o A137732 End If
%o A137732 If k = 1 Then
%o A137732 ZahlPartitionen = 1
%o A137732 Exit Function
%o A137732 ElseIf k = n Then
%o A137732 ZahlPartitionen = 1
%o A137732 Exit Function
%o A137732 ElseIf k > n Then
%o A137732 ZahlPartitionen = 0
%o A137732 Exit Function
%o A137732 End If
%o A137732 ZahlPartitionen = ZahlPartitionen(n - 1, k - 1) + ZahlPartitionen(n - k, k)
%o A137732 End Function
%Y A137732 Cf. A000108, A000142, A137591, A137731.
%K A137732 nonn
%O A137732 1,3
%A A137732 _Thomas Wieder_, Feb 09 2008
%E A137732 Extended by _R. J. Mathar_, Aug 25 2008