login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137732 Repeated set splitting, unlabeled elements. Repeated integer partitioning into two parts. 4
1, 1, 2, 5, 16, 55, 224, 935, 4400, 21262, 111624, 596805, 3457354, 20147882, 125455512, 792576243, 5277532388, 35519373064, 252120178596, 1800810613940, 13492153025558, 102095379031327, 804122472505530, 6395239610004277 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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(binomial(n-1,k)*a(k)*a(n-k),k=1..n-1) 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.

LINKS

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

FORMULA

a(n) = sum(p(n-1,k)*a(k)*a(n-k),k=1..n-1) with a(1)=1 and where p(n,k) denotes the number of integer partitions of n into k parts.

EXAMPLE

(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.

MAPLE

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: [From R. J. Mathar, Aug 25 2008]

PROG

Sub A137714() ' This is a VBA program.

Dim n As Long, nstart As Long, nend As Long

Dim k As Long, HSumme As Long, H(100) As Long

nstart = 2

nend = 15

H(1) = 1

For n = nstart To nend

HSumme = 0

For k = 1 To n - 1

HSumme = HSumme + ZahlPartitionen(n - 1, k) * H(k) * H(n - k)

Next k

H(n) = HSumme

Next n

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)

End Sub

Public Function ZahlPartitionen(n As Long, k As Long)

Dim imsgbox As Integer

If n > 2147483648# Or k > 2147483648# Then

imsgbox = MsgBox("n and k need to be smaller than 2147483648 !", vbOKOnly, "ZahlPartitionen")

End

End If

If (n < 0 Or k < 0) Then

imsgbox = MsgBox("n and k need to be greater than 0 !", vbOKOnly, "ZahlPartitionen")

End

End If

If k = 1 Then

ZahlPartitionen = 1

Exit Function

ElseIf k = n Then

ZahlPartitionen = 1

Exit Function

ElseIf k > n Then

ZahlPartitionen = 0

Exit Function

End If

ZahlPartitionen = ZahlPartitionen(n - 1, k - 1) + ZahlPartitionen(n - k, k)

End Function

CROSSREFS

Cf. A000108, A000142, A137591, A137731.

Sequence in context: A026106 A066642 A019988 * A057973 A102461 A176332

Adjacent sequences:  A137729 A137730 A137731 * A137733 A137734 A137735

KEYWORD

nonn

AUTHOR

Thomas Wieder, Feb 09 2008

EXTENSIONS

Extended by R. J. Mathar, Aug 25 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 23 22:11 EDT 2014. Contains 240947 sequences.