1,2

Consider a set N={1,2,3,...n}. We can apply the operation S~(N) on N which gives us the set partitions S~(N)=SP(N) of N. Let denote

SP_i(N) such a set partition, then SP(N)={SP_1(N), SP_2(N)...,SP_B(n)} (There are B(n) set partitions of N with B(n) as the Bell

number). Observe that in each SP(N) we have SP(1)={{1,2,3,...,n}} and SP(B(n))={{1},{2},{3},...,{n}} and their magnitudes are |SP(1)|=1

and |SP(B(n)|=n.

Now we perform an iteration on the set partitions SP_i(N). We set partition each SP_i(N), thus we perform S~(SP_i(N), but we exclude

SP(1)={{1,2,3,...,n}} and SP(B(n))={{1},{2},{3},...,{n}} from this repetition. Otherwise an infinite recurrsion arises. Thus if 1 <

|SP_i(N)|=m < n, then we apply S~ on SP_i(N) again and get S~(SP_i(N))= SP(SP_i(N))={SP_1(SP_i(N)),...,SP_B(m)(SP_i(N))}. We repeat this

partition operation S~ on every set partition we encounter. Let denote U_k a subset of SP_i(X) were X is a set. X may be any of the

subsequent set partitions. Since |U_k| < X (under the condition above on m) the repeated application of S~ will end in set partitions

SP(X) with |SP(X)| = 1.

Let us consider the example N={1,2,3}. The S~(N) gives us {{1,2,3}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{13}}, and {{1},{2},{1}}. We

exclude {{1,2,3}} and {{1},{2},{1}} from further partitioning. From {{1,2},{3}} we get {{{1,2},{3}}} and {{{1,2}},{{3}}}. Consider the

last two partitions. They correspond to N'={1',2'} and are thus {{1',2'}} and {{1'},{2'}}. Since |{{1',2'}}|=1 and |{{1'},{2'}}|=2 these

last two set partitions can not be partitioned any further according to our condition above. In total we get {{1,2,3}}, {{1,2},{3}},

{{1,3},{2}}, {{2,3},{1}}, {{{1,2},{3}}}, {{{1,2}},{{3}}}, {{{1,3},{2}}}, {{{1,3}},{{2}}}, {{{2,3},{1}}}, {{{2,3}},{{1}}}, {{1},{2},{3}}

and we have a(n=3)=11.

A possible application are the number of coalitions among the set N={1,2,...,n} of n persons. These persons will split into parties =

subsets U_k of N. Then coalitions will form among these parties, thus we encounter sets of subsets. It is even possible that coalitions

form coalitions in turn. We thus define a coalition structure as a set of repeated set partitions. For example if n=6 we could have

{{1,2},{3}},{{4,5,6}}, the parties {1,2} and {3} form the coalition {{1,2},{3}}. Since {{456}}={4,5,6} one might not want to consider a

single set as a coalition, but formally it is possible to do so. However, if in the example all three parties are patriotic, they may

stand together in questions of national interest and the coalition structure would be {{{1,2},{3}},{{4,5,6}}}.

However, in my opinion, the usual definition of a coalition as a partition of a set falls too short.

See also A005121 = Ultradissimilarity relations on an n-set. The paper "On the Asymptotic Analysis of a Class of Linear Recurrences" (by Thomas Prellberg) outlines how to find an asymptotic formula for A005121. Perhaps this method is applicable to the present sequence as well, but one needs to have the generating function as starting point.

Thomas Wieder, Homepage.

Thomas Wieder, (Old) Homepage.

Thomas Prellberg, On the Asymptotic Analysis of a Class of Linear Recurrences, Algorithms Seminar 2002-2004, F. Chyzak (ed.), INRIA, (2005), pp. 47-50.

Recurrence: a(1)=1, a(2)=2, a(n) = Bell(n) + sum_{i=2}^{n-1} S2(n,i) a(i) E.g.: a(n=4) = Bell(4) + S2(4,2) a(2) + S2(4,3) a(3) = 15+2+7*2+6*11 = 95. "closed" formula: a(n=4) = Bell(n=4) + sum_{i1=2}^{(n=4)-1} Bell(i1)+S2(n,i1)*sum_{i2=2}^{i1-1} Bell(i2)+S2(i1,i2)*sum_{i3=2}^{i2-1} Bell(i3)+S2(i2,i3)*sum_{i4=2}^{i3-1} Stirling2(i3,i4)

a(n=3)=11 because we have {{1,2,3}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}, {{{1,2},{3}}}, {{{1,2}},{{3}}}, {{{1,3},{2}}}, {{{1,3}},{{2}}}, {{{2,3},{1}}}, {{{2,3}},{{1}}}, {{1},{2},{3}}.

Sub test_A131407_rec()

Dim n As Long, Result As Long

For n = 1 To 9

Result = A131407_rec(n)

Debug.Print n, Result

Next n

End Sub

Public Function A131407_rec(n As Long)

' Recursive formula.

Dim imsgbox As Integer

Dim i As Long, j As Long, Summe As Long

If n = 0 Then

A131407_rec = 0

Exit Function

ElseIf n = 1 Then

A131407_rec = 1

Exit Function

ElseIf n = 2 Then

A131407_rec = 2

Exit Function

ElseIf n > 2 And n < 13 Then

Summe = Bell(n)

For j = 2 To n - 1

Summe = Summe + Stirling2(n, j) * A131407_rec(j)

Next j

Else

imsgbox = MsgBox("Illegal input for argument *** n *** !", vbOKOnly, "A131407_rec")

End

End If

A131407_rec = Summe

End Function

Sub test_A131407_expl()

Dim n As Long, Result As Long

For n = 1 To 4

Result = A131407_expl(n)

Debug.Print n, Result

Next n

End Sub

Public Function A131407_expl(n As Long)

' Explicit formula. For n =1, 2, 3, 4 only!

Dim imsgbox As Integer

Dim e As Long, f As Long, g As Long, h As Long, Summe As Long, Summe2 As Long, Summe3 As Long, Summe4 As Long

Dim zeile As Integer, spalte As Integer

If n = 0 Then

A131407_expl = 0

Exit Function

ElseIf n = 1 Then

A131407_expl = 1

Exit Function

ElseIf n = 2 Then

A131407_expl = 2

Exit Function

ElseIf n > 2 And n < 5 Then

Summe = Bell(n)

For e = 2 To n - 1

Summe2 = Bell(e)

For f = 2 To e - 1

Summe3 = Bell(f)

For g = 2 To f - 1

Summe4 = Bell(g)

For h = 2 To g - 1

Summe4 = Summe4 + Stirling2(g, h)

spalte = spalte + 4

Next h

Summe3 = Summe3 + Stirling2(f, g) * Summe4

Next g

Summe2 = Summe2 + Stirling2(e, f) * Summe3

Next f

zeile = zeile + 1

Summe = Summe + Stirling2(n, e) * Summe2

Next e

Else

imsgbox = MsgBox("Illegal input for argument *** n *** !", vbOKOnly, "A131407_expl")

End

End If

A131407_expl = Summe

End Function

Function Bell(n As Long)

' Berechne die Bellschen Zahlen.

Dim imsgbox As Integer

Dim i As Long

If n > 2147483648# Then

imsgbox = MsgBox("n needs to be smaller than 2147483648 !", vbOKOnly, "Bell")

End

End If

If (n < 0) Then

imsgbox = MsgBox("n needs to be greater than 0 !", vbOKOnly, "Bell")

End

End If

Bell = 0

For i = 1 To n

Bell = Bell + Stirling2(n, i)

Next i

End Function

Sub Test_Stirling2()

Dim n As Long, k As Long, dummy As Long, dummy2 As Long

k = 3

For n = 1 To 10

dummy = Stirling2(n, k)

Debug.Print n, k, dummy

Next n

End Sub

Function Stirling2(n As Long, k As Long)

' Berechne die Stirlingschen Zahlen der zweiten Art.

Dim i As Long, Summe As Long

Summe = 0

For i = 0 To k

Summe = Summe + ((-1) ^ i) * binomial(k, i) * (k - i) ^ n

Next i

Stirling2 = (1 / faculty(k)) * Summe

End Function

Sub Test_binomial()

Dim n As Long, dummy As Long

n = 6

dummy = binomial(n, 4)

Debug.Print n, dummy

End Sub

Function binomial(m As Long, n As Long)

' Berechne die Binomialzahlen.

Dim Result As Long

Result = faculty(m) / (faculty(m - n) * faculty(n))

binomial = Result

End Function

Function faculty(n As Long)

' Berechne die Fakultat (ohne Rekursion).

Dim Result As Long, i As Long

Result = 1

For i = 2 To n

Result = Result * i

Next i

faculty = Result

End Function

rctlnn := proc(n::nonnegint) # Thanks to Joe Riel who suggested to use # "procname" instead of "rctlnn" within the program. local j; option remember; if n = 0 then 0; else bell(n)+add(stirling2(n, j)*procname(j), j=2..n-1); end if; end proc:

Cf. A000110, A131408.

Sequence in context: A099697 A083069 A098621 this_sequence A138210 A136344 A055680

Adjacent sequences: A131404 A131405 A131406 this_sequence A131408 A131409 A131410

nonn

Thomas Wieder (thomas.wieder(AT)t-online.de), Jul 09 2007, Jul 20 2007