|
|
A099947
|
|
Number of topologically connected set partitions of {1,...,n}.
|
|
37
|
|
|
1, 1, 1, 1, 2, 6, 21, 85, 385, 1907, 10205, 58455, 355884, 2290536, 15518391, 110283179, 819675482, 6355429550, 51293023347, 430062712439, 3739408304962, 33665192703946, 313354708842791, 3011545611755271, 29847401178719637, 304713973031878687, 3201007359886598431
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
A set partition of {1,...,n} is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...}, {...z...t...}} for some x < z < y < t or z < x < t < y. - Gus Wiseman, Feb 19 2019
|
|
LINKS
|
|
|
FORMULA
|
O.g.f. A(x) satisfies
(1) A(x) = Sum_{n>=0} A000110(n)*x^n/A(x)^n, where A000110 are the Bell numbers.
(2) A(x) = Sum_{n>=0} x^n / Product_{k=1..n} (A(x) - k*x).
(3) A(x) = 1/(1 - x/(A(x) - 1*x/(1 - x/(A(x) - 2*x/(1 - x/(A(x) - 3*x/(1 - x/(A(x) - 4*x/(1 - x/(A(x) - ... )))))))), a continued fraction. (End)
B(n) = Sum_p Product_{s in p} a(|s|) where p is a non-crossing set partition of {1,...,n} and B = A000110. In words, every set partition of {1,...,n} can be uniquely decomposed as a non-crossing set partition together with a topologically connected set partition of each block. - Gus Wiseman, Feb 19 2019
|
|
EXAMPLE
|
O.g.f.: A(x) = 1 + x + x^2 + x^3 + 2*x^4 + 6*x^5 + 21*x^6 + 85*x^7 +...
The o.g.f. satisfies
(1) A(x) = 1 + x/A(x) + 2*x^2/A(x)^2 + 5*x^3/A(x)^3 + 15*x^4/A(x)^4 + 52*x^5/A(x)^5 + 203*x^6/A(x)^6 + ... + A000110(n)*x^n/A(x)^n + ...
(2) A(x) = 1 + x/(A(x)-x) + x^2/((A(x)-x)*(A(x)-2*x)) + x^3/((A(x)-x)*(A(x)-2*x)*(A(x)-3*x)) + x^4/((A(x)-x)*(A(x)-2*x)*(A(x)-3*x)*(A(x)-4*x)) + ... (End)
The a(1) = 1 through a(6) = 21 topologically connected set partitions:
{{1}} {{12}} {{123}} {{1234}} {{12345}} {{123456}}
{{13}{24}} {{124}{35}} {{1235}{46}}
{{13}{245}} {{124}{356}}
{{134}{25}} {{1245}{36}}
{{135}{24}} {{1246}{35}}
{{14}{235}} {{125}{346}}
{{13}{2456}}
{{134}{256}}
{{1345}{26}}
{{1346}{25}}
{{135}{246}}
{{1356}{24}}
{{136}{245}}
{{14}{2356}}
{{145}{236}}
{{146}{235}}
{{15}{2346}}
{{13}{25}{46}}
{{14}{25}{36}}
{{14}{26}{35}}
{{15}{24}{36}}
(End)
|
|
MATHEMATICA
|
a[0] = 1; a[n_] := Module[{A = 1 + x}, For[i = 1, i <= n, i++, A = Sum[x^m/Product[A - k*x + x*O[x]^n, {k, 1, m}], {m, 0, n}]]; Coefficient[A, x^n]]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Sep 13 2013, after Paul D. Hanna *)
nn=8;
nonXQ[stn_]:=!MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<t||z<x<t<y];
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
Solve[Table[BellB[n]==Sum[Product[a[Length[s]], {s, stn}], {stn, Select[sps[Range[n]], nonXQ]}], {n, nn}], Array[a, nn]] (* Gus Wiseman, Feb 19 2019 *)
|
|
PROG
|
(PARI) {a(n)=if(n<0, 0, polcoeff( x/serreverse(x*serlaplace(exp(exp(x+x*O(x^n))-1))), n))} /* Michael Somos, Sep 22 2005 */
(PARI) {a(n)=local(A=1+x); for(i=1, n, A=sum(m=0, n, x^m/prod(k=1, m, A - k*x +x*O(x^n)) )); polcoeff(A, n)} // Paul D. Hanna, Apr 16 2013
|
|
CROSSREFS
|
Cf. A000108, A000110, A001187, A007297, A016098, A092918, A268814, A268815, A305078, A306438, A323818, A324166, A324172, A324173.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|