A324172 -id:A324172 - cp's OEIS frontend

A232580 Number of binary sequences of length n that contain at least one contiguous subsequence 011.

0, 0, 0, 1, 4, 12, 31, 74, 168, 369, 792, 1672, 3487, 7206, 14788, 30185, 61356, 124308, 251199, 506578, 1019920, 2050785, 4119280, 8267216, 16580799, 33236622, 66594636, 133385689, 267089188, 534692604, 1070217247, 2141780762, 4285739832, 8575004241

Offset: 0

Geoffrey Critzer, Nov 26 2013

From Gus Wiseman, Jun 26 2022: (Start)
Also the number of integer compositions of n + 1 with an even part other than the first or last. For example, the a(3) = 1 through a(5) = 12 compositions are:
  (121)  (122)   (123)
         (221)   (141)
         (1121)  (222)
         (1211)  (321)
                 (1122)
                 (1212)
                 (1221)
                 (2121)
                 (2211)
                 (11121)
                 (11211)
                 (12111)
The odd version is A274230.
(End)

			a(4) = 4 because we have: 0011, 0110, 0111, 1011.

Colin Barker, Table of n, a(n) for n = 0..1000
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 34.
Index entries for linear recurrences with constant coefficients, signature (4,-4,-1,2).

The complement is counted by A000071(n) = A001911(n) + 1.
For the contiguous pattern (1,1) or (0,0) we have A000225.
For the contiguous pattern (1,0,1) or (0,1,0) we have A000253.
For the contiguous pattern (1,0) or (0,1) we have A000295.
Numbers whose binary expansion is of this type are A004750.
For the contiguous pattern (1,1,1) or (0,0,0) we have A050231.
The not necessarily contiguous version is A324172.
Cf. A034691, A261983, A274230, A335455, A335457, A335458, A335516.

nn=40;a=x/(1-x);CoefficientList[Series[a^2 x/(1-a x)/(1-2x),{x,0,nn}],x]
(* second program *)
Table[Length[Select[Tuples[{0,1},n],MatchQ[#,{_,0,1,1,_}]&]],{n,0,10}] (* Gus Wiseman, Jun 26 2022 *)

concat(vector(3), Vec(x^3/(-2*x^4+x^3+4*x^2-4*x+1) + O(x^40))) \\ Colin Barker, Nov 03 2016

O.g.f.: x^3/( (1-x)^2*(1-x^2/(1-x))*(1-2x) ).
a(n) ~ 2^n.
From Colin Barker, Nov 03 2016: (Start)
a(n) = (1 + 2^n - (2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5)).
a(n) = 4*a(n-1) - 4*a(n-2) - a(n-3) + 2*a(n-4) for n > 3. (End)
a(n) = 2^n - Fibonacci(n+3) + 1. - Ehren Metcalfe, Dec 27 2018
E.g.f.: 2*exp(x/2)*(5*exp(x)*cosh(x/2) - 5*cosh(sqrt(5)*x/2) - 2*sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, Apr 06 2022

A268814 Number of purely crossing partitions of [n].

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 5, 14, 62, 298, 1494, 8140, 47146, 289250, 1873304, 12756416, 91062073, 679616480, 5290206513, 42858740990, 360686972473, 3147670023632, 28439719809159, 265647698228954, 2561823514680235, 25475177517626196, 260922963832247729, 2749617210928715246

Offset: 0

Michel Marcus, Feb 14 2016

nonn

For the definition of a purely crossing partition refer to Dykema link (see PC(n) Definition 1.2 and Table 2).
From Gus Wiseman, Feb 23 2019: (Start)
For n >= 1, a set partition of {1,...,n} is purely crossing if it is topologically connected (A099947), has no successive elements in the same block (A000110(n - 1)), and the first and last vertices belong to different blocks (A005493(n - 2)). For example, the a(4) = 1, a(6) = 5, and a(7) = 14 purely crossing set partitions are:
  {{13}{24}}  {{135}{246}}    {{13}{246}{57}}
              {{13}{25}{46}}  {{13}{257}{46}}
              {{14}{25}{36}}  {{135}{26}{47}}
              {{14}{26}{35}}  {{135}{27}{46}}
              {{15}{24}{36}}  {{136}{24}{57}}
                              {{136}{25}{47}}
                              {{14}{257}{36}}
                              {{14}{26}{357}}
                              {{146}{25}{37}}
                              {{146}{27}{35}}
                              {{15}{246}{37}}
                              {{15}{247}{36}}
                              {{16}{24}{357}}
                              {{16}{247}{35}}
(End)

			G.f.: A(x) = 1 + x^4 + 5*x^6 + 14*x^7 + 62*x^8 + 298*x^9 + 1494*x^10 + 8140*x^11 + 47146*x^12 +...

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

Cf. A000108 (non-crossing partitions), A000110, A000699, A001263, A002662, A005493, A016098, A054726, A099947, A268815, A306417, A324011, A324166, A324172, A324173, A324324.

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]; A = (B-x)/(1+x); Join[{1}, CoefficientList[A, x] // Rest] (* Jean-François Alcover, Feb 23 2016, adapted from K. J. Dykema's code *)
intvQ[set_]:=Or[set=={},Sort[set]==Range[Min@@set,Max@@set]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],And[!MatchQ[#,{_,{_,x_,y_,_},_}/;x+1==y],#=={}||And@@Not/@intvQ/@Union@@@Subsets[#,{1,Length[#]-1}],#=={}||Position[#,1][[1,1]]!=Position[#,n][[1,1]]]&]],{n,0,10}] (* Gus Wiseman, Feb 23 2019 *)

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)); vb = Vec(b-1); va = vector(#vb); va[1] = 0; va[2] = 0; for (k=3, #va, va[k] = vb[k] - va[k-1]; ); concat(1, va); }

{a(n) = my(A=1+x^3); for(i=1, n, A = sum(m=0, n, x^m/prod(k=1, m, (1+x)^2*A - k*x +x*O(x^n)) )/(1+x) ); polcoeff( A, n)}
for(n=0,35,print1(a(n),", ")) \\ Paul D. Hanna, Mar 07 2016

{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 +x*O(x^n))^(2*m+1)*A^m)) ); polcoeff(A, n)}
for(n=0,25,print1(a(n),", ")) \\ Paul D. Hanna, Mar 07 2016

G.f.: G(x) satisfies B(x) = x + (1 + x)*G(x) where B(x) is the g.f. of A268815 (see A(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)^(2*n+1) * A(x)^n), where A000110 are the Bell numbers.
(2) A(x) = 1/(1+x) * Sum_{n>=0} x^n / Product_{k=1..n} ((1+x)^2*A(x) - k*x).
(3) A(x) = 1/(1+x - x/((1+x)*A(x) - 1*x/(1+x - x/((1+x)*A(x) - 2*x/(1+x - x/((1+x)*A(x) - 3*x/(1+x - x/((1+x)*A(x) - 4*x/(1+x - x/((1+x)*A(x) -...)))))))))), a continued fraction. (End)

A324323 Regular triangle read by rows where T(n,k) is the number of topologically connected set partitions of {1,...,n} with k blocks, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 5, 0, 0, 0, 0, 1, 16, 4, 0, 0, 0, 0, 1, 42, 42, 0, 0, 0, 0, 0, 1, 99, 258, 27, 0, 0, 0, 0, 0, 1, 219, 1222, 465, 0, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Feb 22 2019

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.

			Triangle begins:
    1
    0    1
    0    1    0
    0    1    0    0
    0    1    1    0    0
    0    1    5    0    0    0
    0    1   16    4    0    0    0
    0    1   42   42    0    0    0    0
    0    1   99  258   27    0    0    0    0
    0    1  219 1222  465    0    0    0    0    0
Row n = 6 counts the following set partitions:
  {{123456}}  {{1235}{46}}  {{13}{25}{46}}
              {{124}{356}}  {{14}{25}{36}}
              {{1245}{36}}  {{14}{26}{35}}
              {{1246}{35}}  {{15}{24}{36}}
              {{125}{346}}
              {{13}{2456}}
              {{134}{256}}
              {{1345}{26}}
              {{1346}{25}}
              {{135}{246}}
              {{1356}{24}}
              {{136}{245}}
              {{14}{2356}}
              {{145}{236}}
              {{146}{235}}
              {{15}{2346}}

Row sums are A099947. Row k = 2 is A002662.
Cf. A000108, A000110, A001263, A016098, A136653, A268814, A268815, A306438, A324011.
Cf. A324166, A324172, A324173, A324327, A324328.

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]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],Length[crosscmpts[#]]<=1&&Length[#]==k&]],{n,0,6},{k,0,n}]

A326290 Number of non-crossing n-vertex graphs with loops.

Original entry on oeis.org

1, 2, 8, 64, 768, 11264, 184320, 3227648, 59179008, 1121714176, 21803040768, 432218832896, 8705009516544, 177618573852672, 3663840373899264, 76277945940836352, 1600706475536154624, 33823752545680490496, 719051629204296695808, 15368152475218787434496

Offset: 0

Gus Wiseman, Sep 12 2019

nonn

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.

			The a(0) = 1 through a(2) = 8 non-crossing edge sets with loops:
  {}  {}    {}
      {11}  {11}
            {12}
            {22}
            {11,12}
            {11,22}
            {12,22}
            {11,12,22}

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

Crossing and nesting simple graphs are (both) A326210, while non-crossing, non-nesting simple graphs are A326244.

Cf. A000108, A002061, A002662, A054726, A324172, A326252.

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

seq(n)=Vec(1+3*x-4*x^2 -x*sqrt(1-24*x+16*x^2 + O(x^n))) \\ Andrew Howroyd, Sep 14 2019

From Andrew Howroyd, Sep 14 2019: (Start)
a(n) = 2^n * A054726(n).
G.f.: 1 + 3*x - 4*x^2 - x*sqrt(1 - 24*x + 16*x^2). (End)

Terms a(6) and beyond from Andrew Howroyd, Sep 14 2019

A306551 Number of non-double-crossing set partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 202, 863, 3999, 19880, 105134, 587479, 3449505

Offset: 0

Gus Wiseman, Feb 23 2019

Two blocks of a set partitions double-cross each other if they are of the form {{...a...b...c...},{...x...y...z...}} for some a < x < b < y < c < z or x < a < y < b < z < c.

			Most small set partitions are not double-crossing. The smallest that is double-crossing is {{1,3,5},{2,4,6}}.

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

Cf. A000108, A000110, A001263, A002061, A005493, A007297, A016098, A054726, A099947, A324166, A324167, A324172, A324324.

nonXXQ[stn_]:=!MatchQ[stn,{_,{_,a_,_,b_,_,c_,_},_,{_,x_,_,y_,_,z_,_},_}/;a_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],nonXXQ]],{n,0,8}]

A306558 Number of double-crossing set partitions of {1,...,n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 14, 141, 1267, 10841, 91091, 764092

Offset: 0

Gus Wiseman, Feb 23 2019

Two blocks of a set partitions double-cross each other if they are of the form {{...a...b...c...},{...x...y...z...}} for some a < x < b < y < c < z or x < a < y < b < z < c.

			The a(7) = 14 double-crossing set partitions:
  {{1,3,5},{2,4,6,7}}
  {{1,3,6},{2,4,5,7}}
  {{1,4,6},{2,3,5,7}}
  {{1,2,4,6},{3,5,7}}
  {{1,3,4,6},{2,5,7}}
  {{1,3,5,6},{2,4,7}}
  {{1,3,5,7},{2,4,6}}
  {{1},{2,4,6},{3,5,7}}
  {{1,3,5},{2,4,6},{7}}
  {{1,3,5},{2,4,7},{6}}
  {{1,3,6},{2,4,7},{5}}
  {{1,3,6},{2,5,7},{4}}
  {{1,4,6},{2},{3,5,7}}
  {{1,4,6},{2,5,7},{3}}

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

Cf. A000108, A000110, A001263, A002061, A005493, A007297, A016098 (crossing set partitions), A054726, A099947, A324166, A324172, A324324.

croXXQ[stn_]:=MatchQ[stn,{_,{_,a_,_,b_,_,c_,_},_,{_,x_,_,y_,_,z_,_},_}/;a_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],croXXQ]],{n,0,8}]

A326292 Number of crossing integer partitions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 43, 57, 80, 105, 142, 186, 248, 320, 421, 539, 698, 889, 1140, 1438, 1827, 2291, 2882, 3593, 4489, 5559, 6902, 8503, 10484, 12853, 15763

Offset: 0

Gus Wiseman, Oct 03 2019

nonn

A multiset partition is crossing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < y < t or z < x < t < y. An integer partition is crossing if, by replacing each part with its multiset of prime indices, we obtain a crossing multiset partition.

			The a(31) = 1 through a(36) = 7 partitions:
  21,10  21,10,1  21,10,2    21,10,3      21,10,4        21,10,5
                  21,10,1,1  21,10,2,1    21,10,2,2      21,10,3,2
                             21,10,1,1,1  21,10,3,1      21,10,4,1
                                          21,10,2,1,1    21,10,2,2,1
                                          21,10,1,1,1,1  21,10,3,1,1
                                                         21,10,2,1,1,1
                                                         21,10,1,1,1,1,1

The Heinz numbers of these partitions are given by A324170.

Cf. A000108, A002662, A016098, A056239, A112798, A324172, A324326, A326210, A326252, A326332.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

More terms from Jinyuan Wang, Jun 28 2020

cp's OEIS Frontend

A232580 Number of binary sequences of length n that contain at least one contiguous subsequence 011.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A268814 Number of purely crossing partitions of [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A324323 Regular triangle read by rows where T(n,k) is the number of topologically connected set partitions of {1,...,n} with k blocks, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326290 Number of non-crossing n-vertex graphs with loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A306551 Number of non-double-crossing set partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A306558 Number of double-crossing set partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A326292 Number of crossing integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions