login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A268815 Number of purely crossing + partitions of [n]. 4
1, 1, 0, 0, 1, 1, 5, 19, 76, 360, 1792, 9634, 55286, 336396, 2162554, 14629720, 103818489, 770678553, 5969822993, 48148947503, 403545713463, 3508356996105, 31587389832791, 294087418038113, 2827471212909189, 28037001032306431, 286398141349873925, 3010540174760962975 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

For the definition of these special purely crossing partitions refer to Dykema link (see PC+(n) Definition 2.1 and Table 2).

From Gus Wiseman, Feb 23 2019: (Start)

a(n) is the number of topologically connected (A099947) set partitions of {1,...,n} with no successive elements in the same block. For example, the a(4) = 1 through a(7) = 19 set partitions are:

  {{13}{24}}  {{135}{24}}  {{135}{246}}    {{1357}{246}}

                           {{13}{25}{46}}  {{13}{246}{57}}

                           {{14}{25}{36}}  {{13}{257}{46}}

                           {{14}{26}{35}}  {{135}{26}{47}}

                           {{15}{24}{36}}  {{135}{27}{46}}

                                           {{136}{24}{57}}

                                           {{136}{25}{47}}

                                           {{137}{25}{46}}

                                           {{14}{257}{36}}

                                           {{14}{26}{357}}

                                           {{146}{25}{37}}

                                           {{146}{27}{35}}

                                           {{147}{25}{36}}

                                           {{147}{26}{35}}

                                           {{15}{246}{37}}

                                           {{15}{247}{36}}

                                           {{157}{24}{36}}

                                           {{16}{24}{357}}

                                           {{16}{247}{35}}

(End)

LINKS

Table of n, a(n) for n=0..27.

Kenneth J. Dykema, Generating functions for purely crossing partitions, arXiv:1602.03469 [math.CO], 2016.

FORMULA

G.f.: G(x) satisfies C(x) = G(x/1-x) where C(x) is the g.f. of A099947 (see B(x) in Dykema link p. 7).

From Paul D. Hanna, Mar 07 2016: (Start)

O.g.f. A(x) satisfies

(1) A(x) = Sum_{n>=0} A000110(n)*x^n/((1+x)^n*A(x)^n), where A000110 are the Bell numbers.

(2) A(x) = Sum_{n>=0} x^n / Product_{k=1..n} ((1+x)*A(x) - k*x).

(3) A(x) = 1/(1 - x/((1+x)*A(x) - 1*x/(1 - x/((1+x)*A(x) - 2*x/(1 - x/((1+x)*A(x) - 3*x/(1 - x/((1+x)*A(x) - 4*x/(1 - x/((1+x)*A(x) - ... )))))))), a continued fraction. (End)

EXAMPLE

G.f.: A(x) = 1 + x + x^4 + x^5 + 5*x^6 + 19*x^7 + 76*x^8 + 360*x^9 + 1792*x^10 +...

MATHEMATICA

n = 30; F = x*Sum[BellB[k] x^k, {k, 0, n}] + O[x]^n; B = ComposeSeries[1/( InverseSeries[F, w] /w)-1, x/(1+x) + O[x]^n]; CoefficientList[B, x] // Rest (* Jean-François Alcover, Feb 16 2016, adapted from K. J. Dykema's code *)

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

intvQ[set_]:=Or[set=={}, Sort[set]==Range[Min@@set, Max@@set]];

Table[Length[Select[sps[Range[n]], And[!MatchQ[#, {___, {___, x_, y_, ___}, ___}/; x+1==y], #=={}||And@@Not/@intvQ/@Union@@@Subsets[#, {1, Length[#]-1}]]&]], {n, 0, 10}] (* Gus Wiseman, Feb 23 2019 *)

PROG

(PARI) lista(nn) = {c = x/serreverse(x*serlaplace(exp(exp(x+x*O(x^nn)) -1))); b = subst(c, x, x/(1+x) + O(x^nn)); Vec(b); }

(PARI) {a(n) = my(A=1+x); for(i=1, n, A = sum(m=0, n, x^m/prod(k=1, m, (1+x)*A - k*x +x*O(x^n)) )); polcoeff(A, n)}

for(n=0, 25, print1(a(n), ", ")) \\ Paul D. Hanna, Mar 07 2016

(PARI) {Stirling2(n, k) = n!*polcoeff(((exp(x+x*O(x^n)) - 1)^k)/k!, n)}

{Bell(n) = sum(k=0, n, Stirling2(n, k) )}

{a(n) = my(A=1+x); for(i=1, n, A = sum(m=0, n, Bell(m)*x^m/((1+x)*A +x*O(x^n))^m) ); polcoeff(A, n)}

for(n=0, 25, print1(a(n), ", ")) \\ Paul D. Hanna, Mar 07 2016

CROSSREFS

Cf. A000108, A000110, A005493, A016098, A099947, A268814, A306417, A324011, A324166, A324173, A324324, A324327.

Sequence in context: A285424 A275859 A323269 * A108981 A228678 A149771

Adjacent sequences:  A268812 A268813 A268814 * A268816 A268817 A268818

KEYWORD

nonn

AUTHOR

Michel Marcus, Feb 14 2016

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 December 2 01:47 EST 2021. Contains 349435 sequences. (Running on oeis4.)