A054726 -id:A054726 - cp's OEIS frontend

A324171 Number of non-crossing multiset partitions of normal multisets of size n.

1, 1, 4, 16, 75, 378, 2042, 11489, 66697

Offset: 0

Gus Wiseman, Feb 17 2019

A multiset is normal if its union is an initial interval of positive integers.

A multiset partition is crossing if it has a 2-element submultiset of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The A255906(5) - a(5) = 22 crossing multiset partitions:
  {{13}{124}}  {{1}{13}{24}}
  {{13}{224}}  {{1}{24}{35}}
  {{13}{234}}  {{2}{13}{24}}
  {{13}{244}}  {{2}{14}{35}}
  {{13}{245}}  {{3}{13}{24}}
  {{14}{235}}  {{3}{14}{25}}
  {{24}{113}}  {{4}{13}{24}}
  {{24}{123}}  {{4}{13}{25}}
  {{24}{133}}  {{5}{13}{24}}
  {{24}{134}}
  {{24}{135}}
  {{25}{134}}
  {{35}{124}}

Cf. A000108 (non-crossing set partitions), A000124, A001006, A001055, A001263, A007297, A054726 (non-crossing graphs), A099947, A194560, A255906 (multiset partitions of normal multisets), A306438.

Cf. A324166, A324167, A324168, A324169, A324170, A324173.

nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Select[mps[m],nonXQ]],{m,allnorm[n]}],{n,0,8}]

A324327 Number of topologically connected chord graphs covering {1,...,n}.

Original entry on oeis.org

1, 0, 1, 0, 1, 11, 257

Offset: 0

Gus Wiseman, Feb 22 2019

A graph is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected, where two edges cross each other if they are of the form {{x,y},{z,t}} with x < z < y < t or z < x < t < y.

Covering means there are no isolated vertices.

			The a(0) = 1 through a(5) = 11 graphs:
  {}  {{12}}  {{13}{24}}  {{13}{14}{25}}
                          {{13}{24}{25}}
                          {{13}{24}{35}}
                          {{14}{24}{35}}
                          {{14}{25}{35}}
                          {{13}{14}{24}{25}}
                          {{13}{14}{24}{35}}
                          {{13}{14}{25}{35}}
                          {{13}{24}{25}{35}}
                          {{14}{24}{25}{35}}
                          {{13}{14}{24}{25}{35}}

Gus Wiseman, The a(5) = 11 topologically connected chord graphs.
Gus Wiseman, The a(6) = 257 topologically connected chord graphs.

Cf. A000108, A000699 (the case with disjoint edges), A001764, A002061, A007297, A016098, A054726, A099947, A136653 (the case with set-theoretical connectedness also), A268814.

Cf. A324167, A324169 (non-crossing covers), A324172, A324173, A324323, A324328 (non-covering case).

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[crosscmpts[#]]<=1]&]],{n,0,5}]

Inverse binomial transform of A324328.

A324328 Number of topologically connected chord graphs on a subset of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 4, 8, 27, 354

Offset: 0

Gus Wiseman, Feb 22 2019

A graph is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected, where two edges cross each other if they are of the form {{x,y},{z,t}} with x < z < y < t or z < x < t < y.

			The a(0) = 1 through a(5) = 27 graphs:
  {}  {}  {}      {}      {}          {}
          {{12}}  {{12}}  {{12}}      {{12}}
                  {{13}}  {{13}}      {{13}}
                  {{23}}  {{14}}      {{14}}
                          {{23}}      {{15}}
                          {{24}}      {{23}}
                          {{34}}      {{24}}
                          {{13}{24}}  {{25}}
                                      {{34}}
                                      {{35}}
                                      {{45}}
                                      {{13}{24}}
                                      {{13}{25}}
                                      {{14}{25}}
                                      {{14}{35}}
                                      {{24}{35}}
                                      {{13}{14}{25}}
                                      {{13}{24}{25}}
                                      {{13}{24}{35}}
                                      {{14}{24}{35}}
                                      {{14}{25}{35}}
                                      {{13}{14}{24}{25}}
                                      {{13}{14}{24}{35}}
                                      {{13}{14}{25}{35}}
                                      {{13}{24}{25}{35}}
                                      {{14}{24}{25}{35}}
                                      {{13}{14}{24}{25}{35}}

Cf. A000108, A000699, A001764, A002061, A007297, A016098, A054726 (non-crossing chord graphs), A099947, A136653, A268814.

Cf. A324168, A324169, A324172, A324173, A324323, A324327 (covering case).

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[crosscmpts[#]]<=1&]],{n,0,5}]

Binomial transform of A324327.

A326250 Number of weakly nesting simple graphs with vertices {1..n}.

Original entry on oeis.org

0, 0, 0, 3, 50, 982, 32636, 2096723

Offset: 0

Gus Wiseman, Jun 21 2019

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d.

Gus Wiseman, The a(4) = 50 weakly nesting simple graphs.

Non-nesting set partitions are A000108.
Non-crossing graphs are A054726.
Nesting digraphs are A326209.
Crossing graphs are A326210.
MM-numbers of nesting multiset partitions are A326256.
Cf. A000088, A000332, A006125, A117662.
Cf. A326211, A326243, A326244, A326248, A326257, A326279.

wnsXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x<=z

Conjecture: A006125(n) = a(n) + A000108(n).

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 19, 120, 1084, 11783, 141110, 1791156, 23646352, 321220257, 4459886776, 63000867229, 902528825332, 13080523942476, 191445447535373, 2825542818304080, 42005234042942228, 628422035415996065, 9454076958795999908, 142933849346150225253, 2170556938059142024688

Offset: 0

Gus Wiseman, Feb 17 2019

nonn

An antichain is non-crossing if no pair of distinct parts is of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The a(0) = 1 through a(3) = 19 non-crossing antichains:
  {}  {}     {}        {}
      {{1}}  {{1}}     {{1}}
             {{2}}     {{2}}
             {{12}}    {{3}}
             {{1}{2}}  {{12}}
                       {{13}}
                       {{23}}
                       {{123}}
                       {{1}{2}}
                       {{1}{3}}
                       {{2}{3}}
                       {{1}{23}}
                       {{2}{13}}
                       {{3}{12}}
                       {{12}{13}}
                       {{12}{23}}
                       {{13}{23}}
                       {{1}{2}{3}}
                       {{12}{13}{23}}

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000108 (non-crossing set partitions), A000124, A000372 (antichains), A001006, A001263, A006126 (antichain covers), A014466 (nonempty antichains), A054726 (non-crossing graphs), A099947, A261005, A306438.

Cf. A324166, A324167, A324169, A324170, A324171, A324173, A359984.

nn=6;
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

seq(n)={my(f=O(1)); for(n=2, n, f = 1 + (4*x + x^2)*f^2 - 3*x^2*(1 + x)*f^3); Vec(subst(x*(1 + x^2*f^2 - 3*x^3*f^3), x, x/(1-2*x))/x) } \\ Andrew Howroyd, Jan 20 2023

Binomial transform of A324167.

G.f.: A(x) = B(x/(1-2*x))/x where B(x)/x is the g.f. of A359984. - Andrew Howroyd, Jan 20 2023

Terms a(9) and beyond from Andrew Howroyd, Jan 20 2023

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Original entry on oeis.org

1, 0, 1, 4, 13, 44, 149, 504, 1705, 5768, 19513, 66012

Offset: 0

Gus Wiseman, Jun 27 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Is this (apart from offsets) the same as A073717? - R. J. Mathar, Jul 04 2019

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Gus Wiseman, The a(5) = 44 covering simple graphs with no crossing or nesting edges.

The case for set partitions is A001519.
Covering simple graphs are A006129.
The case with just nesting or just crossing edges forbidden is A324169.
The binomial transform is the non-covering case A326244.
Cf. A000108, A006125, A007297, A054726, A099947, A324327, A326279, A326293.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A326330 Number of simple graphs with vertices {1..n} whose nesting edges are connected.

Original entry on oeis.org

1, 1, 2, 4, 8, 30, 654

Offset: 0

Gus Wiseman, Jun 27 2019

Two edges {a,b}, {c,d} are nesting if a < c < d < b or c < a < b < d. A graph has its nesting edges connected if the graph whose vertices are the edges and whose edges are nesting pairs of edges is connected.

Gus Wiseman, The a(5) = 30 nesting-connected simple graphs.

The covering case is the inverse binomial transform A326331.
Graphs whose crossing edges are connected are A324328.
Cf. A006125, A007297, A054726, A099947, A117662, A136653, A324328.
Cf. A326210, A326293, A326335, A326336, A326337, A326338, A326339.

nesXQ[stn_]:=MatchQ[stn,{_,{x_,y_},_,{z_,t_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[nestcmpts[#]]<=1&]],{n,0,5}]

A326337 Number of simple graphs covering the vertices {1..n} whose weakly nesting edges are connected.

Original entry on oeis.org

1, 0, 1, 3, 29, 595, 23437

Offset: 0

Gus Wiseman, Jun 28 2019

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d. A graph has its weakly nesting edges connected if the graph whose vertices are the edges and whose edges are weakly nesting pairs of edges is connected.

Gus Wiseman, The a(4) = 29 covering simple graphs whose weakly nesting edges are connected.

The binomial transform is the non-covering case A326338.
The non-weak case is A326331.
Simple graphs whose nesting edges are connected are A326330.
Cf. A006125, A007297, A054726, A099947, A136653.
Cf. A324169, A324327, A326293, A326294, A326329, A326335, A326336.

wknXQ[stn_]:=MatchQ[stn,{_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;(x<=z&&y>=t)||(x>=z&&y<=t)];
wknestcmpts[stn_]:=csm[Union[List/@stn,Select[Subsets[stn,{2}],wknXQ]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[wknestcmpts[#]]<=1&]],{n,0,5}]

A059435 Number of lattice paths in plane starting at (0,0) and ending at (n,n) with steps from {(i,j): i+j > 0, i, j >= 0} that never go below the line y = x.

Original entry on oeis.org

1, 2, 12, 88, 720, 6304, 57792, 547712, 5323008, 52761088, 531311616, 5420488704, 55905767424, 581954543616, 6106210615296, 64513688174592, 685741070942208, 7328106153115648, 78684992821788672, 848487859401261056

Offset: 0

Wenjin Woan, Feb 01 2001

Series reversion of x(1-4x)/(1-2x). - Paul Barry, May 19 2005

The Hankel transform of this sequence is 8^C(n+1,2) = [1, 8, 512, 262144, ...]. - Philippe Deléham, Nov 08 2007

W.-J. Woan, A bijective proof by induction that the n-th term of this sequence is 2^(n-1) times of the n-th term of the big Schroeder number, 2001 (unpublished).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
David Callan, A uniformly distributed statistic on a class of lattice paths, Electronic J. Combinatorics, Vol. 11(1), R82, 2004.
Z. Chen and H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 (2016); see Eq. (1.13) with a=2 and b=4.
Ira M. Gessel, A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory Ser. A 28 (1980), 321-337.
Elina Robeva and Melinda Sun, Bimonotone Subdivisions of Point Configurations in the Plane, arXiv:2007.00877 [math.CO], 2020. See B(2,n) column in Table 3 (p. 10).
Robert A. Sulanke, Counting lattice paths by Narayana polynomials, Electronic J. Combinatorics 7 (2000), R40.

Cf. A001003, A006318, A054726.

gf := (1+2*x-sqrt(4*x^2-12*x+1))/(8*x): s := series(gf, x, 100): for i from 0 to 50 do printf(`%d,`,coeff(s,x,i)) od:

Table[SeriesCoefficient[(1+2*x-Sqrt[4*x^2-12*x+1])/(8*x),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 11 2012 *)

x='x+O('x^66); Vec((1+2*x-sqrt(4*x^2-12*x+1))/(8*x)) \\ Joerg Arndt, May 06 2013

a(n) = 2^n*A001003(n).
G.f.: (1 + 2*x - sqrt(4*x^2 - 12*x + 1))/(8*x).
From Paul Barry, May 19 2005: (Start)
a(n) = (1/(n + 1)) * Sum_{k=0..n} C(n+1, k) * C(2*n-k, n)(-1)^k * 4^(n-k) * 2^k;
a(n) = Sum_{k=0..n} (1/n) * C(n, k) * C(n, k+1) * 4^k * 2^(n-k);
a(n) = Sum_{k=1..n} N(n, k)*2^(n+k-1), for n >= 1, where N(n, k) are the Narayana numbers (A001263). [Corrected by Alejandro H. Morales, May 14 2015]
(End)
Recurrence: (n+1)*a(n) = 6*(2*n-1)*a(n-1) - 4*(n-2)*a(n-2). - Vaclav Kotesovec, Oct 11 2012
a(n) ~ sqrt(4+3*sqrt(2))*(6+4*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 11 2012

A306386 Number of chord diagrams with n chords all having arc length at least 3.

Original entry on oeis.org

1, 0, 0, 1, 7, 68, 837, 11863, 189503, 3377341, 66564396, 1439304777, 33902511983, 864514417843, 23735220814661, 698226455579492, 21914096529153695, 731009183350476805, 25829581529376423945, 963786767538027630275, 37871891147795243899204, 1563295398737378236910447

Offset: 0

Gus Wiseman, Feb 26 2019

nonn

A cyclical form of A190823.

Also the number of 2-uniform set partitions of {1...2n} such that, when the vertices are arranged uniformly around a circle, no block has its two vertices separated by an arc length of less than 3.

			The a(8) = 7 2-uniform set partitions with all arc lengths at least 3:
  {{1,4},{2,6},{3,7},{5,8}}
  {{1,4},{2,7},{3,6},{5,8}}
  {{1,5},{2,6},{3,7},{4,8}}
  {{1,5},{2,6},{3,8},{4,7}}
  {{1,5},{2,7},{3,6},{4,8}}
  {{1,6},{2,5},{3,7},{4,8}}
  {{1,6},{2,5},{3,8},{4,7}}

Alois P. Heinz, Table of n, a(n) for n = 0..404
Gus Wiseman, The a(5) = 68 chord diagrams with all arc lengths at least 3.

Cf. A000296, A000699, A001006, A001147, A001610, A003436, A038041, A054726, A135042, A170941, A190823, A278990, A306419, A322402, A324011, A324169.

Column k=3 of A324428.

a:= proc(n) option remember; `if`(n<8, [1, 0$2, 1, 7, 68, 837, 11863][n+1],
      ((8*n^4-64*n^3+142*n^2-66*n+109)    *a(n-1)
      -(24*n^4-248*n^3+870*n^2-1106*n+241)*a(n-2)
      +(24*n^4-264*n^3+982*n^2-1270*n+145)*a(n-3)
      -(8*n^4-96*n^3+374*n^2-486*n+33)    *a(n-4)
      -(4*n^3-24*n^2+39*n-2)              *a(n-5))/(4*n^3-36*n^2+99*n-69))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 27 2019

dtui[{},]:={{}};dtui[set:{i,___},n_]:=Join@@Function[s,Prepend[#,s]&/@dtui[Complement[set,s],n]]/@Table[{i,j},{j,Switch[i,1,Select[set,3<#i+2&]]}];
Table[Length[dtui[Range[n],n]],{n,0,12,2}]

a(n) is even <=> n in { A135042 }. - Alois P. Heinz, Feb 27 2019

a(10)-a(16) from Alois P. Heinz, Feb 26 2019

a(17)-a(21) from Alois P. Heinz, Feb 27 2019

cp's OEIS Frontend

A324171 Number of non-crossing multiset partitions of normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324327 Number of topologically connected chord graphs covering {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A324328 Number of topologically connected chord graphs on a subset of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326250 Number of weakly nesting simple graphs with vertices {1..n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326330 Number of simple graphs with vertices {1..n} whose nesting edges are connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A326337 Number of simple graphs covering the vertices {1..n} whose weakly nesting edges are connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs