cp's OEIS Frontend

A131407 Repeated set partitions or nested set partitions. Possible coalitions among n persons.

%I A131407 #64 Dec 16 2024 08:20:28
%S A131407 1,1,2,11,95,1307,27035,788279,30812087,1554832679,98387784047,
%T A131407 7628836816295,711320467520855,78520062277781087,10127079289703949695,
%U A131407 1508987827451079129599,257250406707409951420079,49750955749787132205813743,10833471589449269308161546191
%N A131407 Repeated set partitions or nested set partitions. Possible coalitions among n persons.
%C A131407 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.
%C A131407 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 recursion 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.
%C A131407 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 cannot 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(3)=11.
%C A131407 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}}}.
%C A131407 However, in my opinion, the usual definition of a coalition as a partition of a set falls too short.
%C A131407 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.
%D A131407 Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 319 and 556.
%H A131407 Alois P. Heinz, <a href="/A131407/b131407.txt">Table of n, a(n) for n = 0..261</a>
%H A131407 Thomas Prellberg, <a href="http://algo.inria.fr/seminars/summary/Prellberg2002a.pdf">On the Asymptotic Analysis of a Class of Linear Recurrences</a>, Algorithms Seminar 2002-2004, F. Chyzak (ed.), INRIA, (2005), pp. 47-50.
%H A131407 Thomas Wieder, <a href="/A131407/a131407.txt">Visual Basic Program</a>.
%F A131407 Recurrence: 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).
%F A131407 a(n) ~ 3 * L * (n!)^2 / (n^(1+log(2)/3) * (2*log(2))^n), where L = Lengyel's constant A086053 = 1.0986858055... . - _Vaclav Kotesovec_, Sep 04 2014
%e A131407 a(3)=11 because we have
%e A131407   {{1,2,3}},
%e A131407   {{1,2},{3}},
%e A131407   {{1,3},{2}},
%e A131407   {{2,3},{1}},
%e A131407   {{{1,2},{3}}},
%e A131407   {{{1,2}},{{3}}},
%e A131407   {{{1,3},{2}}},
%e A131407   {{{1,3}},{{2}}},
%e A131407   {{{2,3},{1}}},
%e A131407   {{{2,3}},{{1}}},
%e A131407   {{1},{2},{3}}.
%p A131407 rctlnn := proc(n::nonnegint) # Thanks to Joe Riel, who suggested the use of # "procname" instead of "rctlnn" within the program.
%p A131407 local j; option remember; if n = 0 then 1; else bell(n)+add(stirling2(n,j)*procname(j), j=2..n-1); end if; end proc:
%p A131407 # second Maple program:
%p A131407 a:= proc(n) option remember; uses combinat;
%p A131407       bell(n) + add(stirling2(n, i)*a(i), i=2..n-1)
%p A131407     end:
%p A131407 seq(a(n), n=0..20);  # _Alois P. Heinz_, Apr 05 2012
%t A131407 a[n_] := a[n] = If[n<2, 1, BellB[n] + Sum[StirlingS2[n, i]*a[i], {i, 2, n-1}]]; Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jul 15 2015, after _Alois P. Heinz_ *)
%o A131407 (Visual Basic) ' See Wieder link.
%Y A131407 Cf. A000110, A131408, A086053.
%K A131407 nonn
%O A131407 0,3
%A A131407 _Thomas Wieder_, Jul 09 2007, Jul 20 2007
%E A131407 a(0)=1 prepended by _Alois P. Heinz_, Sep 02 2020