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