A054391 -id:A054391 - cp's OEIS frontend

A326245 Number of crossing, non-capturing set partitions of {1..n}.

0, 0, 0, 0, 1, 7, 34, 141, 537, 1941, 6777, 23096, 77340

Offset: 0

Gus Wiseman, Jun 20 2019

A set 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, and capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The a(4) = 1 and a(5) = 7 set partitions:
  {{1,3},{2,4}}  {{1,2,4},{3,5}}
                 {{1,3},{2,4,5}}
                 {{1},{2,4},{3,5}}
                 {{1,3},{2,4},{5}}
                 {{1,3},{2,5},{4}}
                 {{1,4},{2},{3,5}}
                 {{1,4},{2,5},{3}}

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

Crossing set partitions are A016098.
Non-capturing set partitions are A054391.
Crossing, capturing set partitions are A326246.
Cf. A000108, A000110, A001519, A054391, A058681, A095661, A324170.
Cf. A326212, A326237, A326243, A326248, A326249.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

A054392 Number of permutations with certain forbidden subsequences.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 131, 418, 1352, 4410, 14463, 47605, 157084, 519255, 1718653, 5693903, 18877509, 62620857, 207816230, 689899944, 2290913666, 7608939443, 25276349558, 83977959853, 279039638062, 927272169336, 3081641953082

Offset: 0

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

nonn

Apparently the Motzkin transform of A005251, after A005251(0) is set to 1. - R. J. Mathar, Dec 11 2008

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 131*x^6 + 418*x^7 + 1352*x^8 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000
E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108).

Cf. A005773, A054391-A054394.

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (2 -10*x +13*x^2 -5*x^3 +x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2-14*x^3) )); // G. C. Greubel, Feb 14 2020

m:=30; S:=series((2-10*x+13*x^2-5*x^3+x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2 -14*x^3), x, m+1): seq(coeff(S, x, j), j=0..m); # G. C. Greubel, Feb 14 2020

a[0] = 1; a[n_]:= Module[{M}, M = Table[If[jJean-François Alcover, Aug 16 2018, after A054391 *)
a[n_]:= a[n]= If[n<2, 1, If[n==2, 2, If[3<=n<=4, 9*n-22, ((8*n-19)*a[n-1] - (20*n-49)*a[n-2] +(11*n-1)*a[n-3] +(19*n-116)*a[n-4] -21*(n-5)*a[n-5])/(n-2) ]]]; Table[a[n], {n,0,30}] (* G. C. Greubel, Feb 14 2020 *)

PARI

{a(n) = if( n<1, n==0, polcoeff( subst( x * (1 - x) / (1 - 2*x + x^2 - x^3), x, serreverse( x / (1 + x + x^2) + x * O(x^n))), n))}; /* Michael Somos, Aug 06 2014 */

Sage

def A054392_list(prec): P. = PowerSeriesRing(ZZ, prec) return P( (2-10*x+13*x^2-5*x^3+x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2-14*x^3) ).list() A054392_list(30) # G. C. Greubel, Feb 14 2020

Formula

(n-2)*a(n) = (8*n-19)*a(n-1) - (20*n-49)*a(n-2) + (11*n-1)*a(n-3) + (19*n-116) * a(n-4) - 21*(n-5)*a(n-5). - R. J. Mathar, Aug 09 2015

G.f.: (2 -10*x +13*x^2 -5*x^3 +x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2-14*x^3). - Michael D. Weiner, Feb 07 2020

A054393 Number of permutations with certain forbidden subsequences.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 428, 1417, 4757, 16119, 54963, 188219, 646460, 2224944, 7668915, 26461005, 91371594, 315689675, 1091166442, 3772747245, 13047503222, 45131078409, 156129312025, 540181837728, 1869097588540, 6467740095295

Offset: 0

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

nonn

E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108).

Cf. A005773, A054391, A054392, A054394.

a[0] = 1; a[n_] := Module[{M}, M = Table[If[j < i || i == j && i <= 5 || j == i+1, 1, 0], {i, 1, n}, {j, 1, n}]; MatrixPower[M, n][[1, 1]]];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Aug 16 2018, after A054391 *)

Conjecture: (-n+3)*a(n) + (10*n-33)*a(n-1) + 5*(-7*n+24)*a(n-2) + 2*(22*n-63)*a(n-3) + 2*(5*n-78)*a(n-4) + (-55*n+357)*a(n-5) + (22*n-135)*a(n-6) + 3*(-n+6)*a(n-7) = 0. - R. J. Mathar, Aug 09 2015

A326260 MM-numbers of capturing, non-nesting multiset partitions (with empty parts allowed).

Original entry on oeis.org

2599, 4163, 5198, 6463, 6893, 7291, 7797, 8326, 8507, 9131, 9959, 10396, 10649, 11041, 11639, 12489, 12811, 12926, 12995, 13786, 14237, 14582, 14899, 15157, 15594, 16123, 16403, 16652, 17014, 17063, 17089, 17141, 18101, 18193, 18262, 18643, 18659, 19337, 19389

Offset: 1

Gus Wiseman, Jun 22 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n.

A set partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and y < t. It is nesting if it has two blocks of the form {...x,y...} and {...z,t...} where x < z and y > t or x > z and y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The sequence of terms together with their multiset multisystems begins:
   2599: {{2,2},{1,2,3}}
   4163: {{2,2},{1,2,4}}
   5198: {{},{2,2},{1,2,3}}
   6463: {{2,2},{1,1,2,3}}
   6893: {{1,2,2},{1,2,3}}
   7291: {{2,2},{1,2,5}}
   7797: {{1},{2,2},{1,2,3}}
   8326: {{},{2,2},{1,2,4}}
   8507: {{2,3},{1,2,4}}
   9131: {{2,2},{1,2,6}}
   9959: {{2,2},{1,1,2,4}}
  10396: {{},{},{2,2},{1,2,3}}
  10649: {{2,2},{1,2,2,3}}
  11041: {{1,2,2},{1,2,4}}
  11639: {{2,2,2},{1,2,3}}
  12489: {{1},{2,2},{1,2,4}}
  12811: {{2,2},{1,2,7}}
  12926: {{},{2,2},{1,1,2,3}}
  12995: {{2},{2,2},{1,2,3}}
  13786: {{},{1,2,2},{1,2,3}}

Non-nesting set partitions are A000108.
Capturing set partitions are A326243.
Capturing, non-nesting set partitions are A326249.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of capturing multiset partitions are A326255.
Cf. A001055, A034827, A056239, A058681, A112798, A117662, A302242, A324170.
Cf. A326212, A326246, A054391, A326257, A326258, A326259.

capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;xTable[PrimePi[p],{k}]]]];
Select[Range[10000],!nesXQ[primeMS/@primeMS[#]]&&capXQ[primeMS/@primeMS[#]]&]

A054394 Number of permutations with certain forbidden subsequences.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1429, 4847, 16660, 57820, 202086, 709928, 2503266, 8850681, 31355020, 111242127, 395091069, 1404332528, 4994581900, 17771328588, 63253477326, 225194224134, 801884971816, 2855809269782, 10171707099565

Offset: 0

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

nonn

E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A005773, A054391-A054393.

a[0] = 1; a[n_] := Module[{M}, M = Table[If[j < i || i == j && i <= 6 || j == i+1, 1, 0], {i, 1, n}, {j, 1, n}]; MatrixPower[M, n][[1, 1]]];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Aug 16 2018, after A054391 *)

Conjecture: g.f.(x)=1+z*(1-2z+z^2-z^3)/(1-3z+3z^2-3z^3+2z^4-z^5) where z=x*A001006(x) and A001006(x) is the g.f. of A001006. [R. J. Mathar, Jul 07 2009]

A369436 Number of 2-Motzkin meanders with catastrophes of length n.

Original entry on oeis.org

1, 3, 10, 36, 136, 529, 2095, 8393, 33885, 137547, 560544, 2291181, 9386584, 38525224, 158350133, 651645511, 2684323326, 11066714500, 45656997415, 188475894929, 778444106703, 3216562337420, 13296099775859, 54979806370840, 227410731720624, 940875886301665

Offset: 0

Florian Schager, Jan 23 2024

A 2-Motzkin meander is a lattice path that does not go below the x-axis. with steps U = (1,1), D = (1,-1) and two copies R = (1,0) and B = (1,0), i.e. red and blue level steps.

A catastrophe is a step C = (1,-k) from altitude k to altitude 0 for k > 1.

			For n = 2 the a(2) = 10 solutions are UU, UR, UB, UD, RU, RR, RB, BU, BR, BB.
For n = 3 the a(3) = 36 solutions are UUU, UUR, UUB, UUD, UUC, URU, URR, URB, URD, UBU, UBR, UBB, UBD, UDU, UDR, UDB, RUU, RUR, RUB, RUD, RRU, RRR, RRB, RBU, RBR, RBB, BUU, BUR, BUB, BUD, BRU, BRR, BRB, BBU, BBR, BBB.

Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.

Cf. A274115 (Dyck meanders).

Cf. A054391 (Motzkin meanders).

K := 1 - z*(1/u + 2 + u);
u1 := solve(K, u)[2];
M := (1 - u1)/(1 - 4*z);
E := u1/z;
M1 := z*E^2;Q := z*(M - E - M1);
series(M/(1 - Q), z, 30);

my(N=44,z='z+O('z^N),S=sqrt(1-4*z)); Vec((1 - 4*z - S)*z/(5*S*z^2 + 12*z^3 - 5*z*S - 15*z^2 + S + 7*z - 1))

G.f.: (1 - 4*z - sqrt(1 - 4*z))*z/(5*sqrt(1 - 4*z)*z^2 + 12*z^3 - 5*z*sqrt(-4*z + 1) - 15*z^2 + sqrt(-4*z + 1) + 7*z - 1).

D-finite with recurrence n*a(n) +4*(-3*n+2)*a(n-1) +(53*n-70)*a(n-2) +(-107*n+210)*a(n-3) +(101*n-268)*a(n-4) +18*(-2*n+7)*a(n-5)=0. - R. J. Mathar, Jan 28 2024

cp's OEIS Frontend

A326245 Number of crossing, non-capturing set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A054392 Number of permutations with certain forbidden subsequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A054393 Number of permutations with certain forbidden subsequences.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A326260 MM-numbers of capturing, non-nesting multiset partitions (with empty parts allowed).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A054394 Number of permutations with certain forbidden subsequences.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A369436 Number of 2-Motzkin meanders with catastrophes of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula