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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Alois P. Heinz, Table of n, a(n) for n = 0..222

Janet Simpson Beissinger, The enumeration of irreducible combinatorial objects, J. Comb. Theory, Ser. A, 38 (1985), pp. 143-169. (Example 6.2)

Daniel Birmajer, Juan B. Gil, Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.

Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016. See column NIS in Table 2 p. 8.

FindStat, The number of topologically connected components of a set partition.

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

M. Klazar, Bell numbers, their relatives and algebraic differential equations

M. Klazar, Bell numbers, their relatives and algebraic differential equations, J. Combin. Theory, A 102 (2003), 63-87.

FORMULA

From Paul D. Hanna, Apr 16 2013: (Start)

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

From Paul D. Hanna, Apr 16 2013]: (Start)

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)

From Gus Wiseman, Feb 19 2019: (Start)

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.

Sequence in context: A150225 A123922 A326276 * A121726 A090805 A150226

Adjacent sequences:  A099944 A099945 A099946 * A099948 A099949 A099950

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Nov 12 2004

EXTENSIONS

Name edited by Gus Wiseman, Feb 19 2019

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 21:03 EST 2019. Contains 329348 sequences. (Running on oeis4.)