A073525 -id:A073525 - cp's OEIS frontend

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

1, 1, 2, 5, 15, 51, 191, 772, 3320, 15032, 71084, 348889, 1768483, 9220655, 49286863, 269346822, 1501400222, 8519796094, 49133373040, 287544553912, 1705548000296, 10241669069576, 62201517142632, 381749896129920, 2365758616886432, 14793705539872672

Offset: 0

Mireille Bousquet-Mélou, Jun 29 2005

Also the number of 2-regular 3-noncrossing partitions. There is a bijection from 2-regular 3-noncrossing partitions of n to enhanced partition of n-1. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 30 2007
It appears that this is the number of sequences of length n, starting with a(1) = 1 and 1 <= a(2) <= 2, with 1 <= a(n) <= max(a(n-1),a(n-2)) + 1 for n > 2. - Franklin T. Adams-Watters, May 27 2008
From Eric M. Schmidt, Jul 17 2017: (Start)
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) <= e(k) and e(i) >= e(k). [Martinez and Savage, 2.16]
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) >= e(k). [Martinez and Savage, 2.16]
(End)
The second of the above-mentioned conjectures is proved in Zhicong Lin's paper. - Eric M. Schmidt, Nov 25 2017

			There are 52 partitions of 5 elements, but a(5)=51 because the partition (1,5)(2,4)(3) has an enhanced 3-nesting.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, On sequences associated to the invariant theory of rank two simple Lie algebras, arXiv:1911.10288 [math.CO], 2019.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, On some combinatorial sequences associated to invariant theory, arXiv:2110.13753 [math.CO], 2021.
M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.
W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.
Emma Y. Jin, Jing Qin and Christian M. Reidys, On 2-regular k-noncrossing partitions, arXiv:0710.5014 [math.CO], 2007.
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018.
Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, arXiv:1706.07213 [math.CO], 2017.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Sherry H. F. Yan, Ascent sequences and 3-nonnesting set partitions, Eur. J. Comb. 39, 80-94 (2014), remark 3.6.

Cf. A124303, A073525, A007317.

Cf. A000110, A000108.

a:= proc(n) option remember; if n<=1 then 1 elif n=2 then 2 else (8*(n+1) *(n-1) *a(n-2)+ (7*(n-2)^2 +53*(n-2) +88) *a(n-1))/(n+6)/(n+5) fi end: seq(a(n), n=0..20);  # Alois P. Heinz, Sep 05 2008

a[n_] := a[n] = If[n <= 1, 1, If[n==2, 2, (8*(n+1)*(n-1)*a[n-2]+(7*(n-2)^2+53*(n-2)+88)*a[n-1])/(n+6)/(n+5)]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

D-finite with recurrence: 8*(n+3)*(n+1)*a(n)+(7*n^2+53*n+88)*a(n+1)-(n+8)*(n+7)*a(n+2)=0. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 26 2007
G.f.: -(6*x^4-15*x^3-7*x^2-11*x-1)/(6*x^5)+(224*x^3-60*x^2+45*x+5) * hypergeom([1/3, 2/3],[2],27*x^2/(1-2*x)^3) / (30*x^5*(2*x-1))+(32*x^2+64*x+5) * hypergeom([2/3, 4/3],[3],27*x^2/(1-2*x)^3)/(5*x^3*(2*x-1)^2). - Mark van Hoeij, Oct 24 2011
a(n) ~ 5*sqrt(3)*2^(3*n+16)/(27*Pi*n^7). - Vaclav Kotesovec, Aug 16 2013
G.f.: (-6*x^4+15*x^3+7*x^2+11*x+1)/(6*x^5)-(1-8*x)^(4/3)*(1+x)^(2/3)*hypergeom([-2/3, 7/3],[2],-27*x/((1+x)*(-1+8*x)^2))/(6*x^5). - Mark van Hoeij, Jul 26 2021

Edited by N. J. A. Sloane at the suggestion of Franklin T. Adams-Watters, Apr 27 2008

A129775 Number of maximally clustered permutations in S_n; the maximally clustered permutations are those that avoid 3421, 4312 and 4321.

Original entry on oeis.org

1, 1, 2, 6, 21, 78, 298, 1157, 4539, 17936, 71251, 284188, 1137076, 4561093, 18333337, 73816489, 297635750, 1201551286, 4855672249, 19640147061, 79501958895, 322037615290, 1305256267511, 5293166568270, 21475362822956, 87166344495561, 353933533606927

Offset: 0

Brant Jones (brant(AT)math.washington.edu), May 17 2007

nonn

Equals INVERT transform of A001700 prefaced with a "1": (1, 1, 3, 10, 35, 126, 462, ...). - Gary W. Adamson, Dec 26 2008
Row sums of A155083. - Paul Barry, Jan 19 2009
Hankel transform is n+1. - Paul Barry, Jul 31 2010
INVERT transform of A088218. - Michael Somos, Jan 01 2014
INVERT transform is A073525. - Michael Somos, Jan 09 2014

			a(5)=78 because there are 78 permutations of size 5 that avoid 3421, 4312 and 4321.
G.f. = 1 + x + 2*x^2 + 6*x^3 + 21*x^4 + 78*x^5 + 298*x^6 + 1157*x^7 + 4539*x^8 + ...

Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
David Callan, Toufik Mansour, and Mark Shattuck, Twelve subsets of permutations enumerated as maximally clustered permutations, Annales Mathematicae et Informaticae, 47 (2017) pp. 41-74.
H. Denoncourt and B. Jones, The enumeration of maximally clustered permutations, arXiv:0704.3469 [math.CO], 2007-2008.
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)
Jozsef Losonczy, Maximally clustered elements and Schubert varieties, Annals of Combinatorics 11 (2) (2007) 195-212.

Cf. A108600.

Cf. A001700. - Gary W. Adamson, Dec 26 2008

a[ n_] := SeriesCoefficient[ 1 + 2 x^2 / (-1 + 4 x - 2 x^2 + Sqrt[1 - 4 x]), {x, 0, n}]; (* Michael Somos, Jan 01 2014 *)
a[n_] := 1+Sum[(m Binomial[2(n-m), n-m-1] Hypergeometric2F1[m+1, m-n+1, n-m+2, -1])/(n-m), {m, 1, n-1}]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Dec 14 2018, after Vladimir Kruchinin *)

a(n):=if n=0 then 1 else sum(sum(k*binomial(m+k-1,m-1)*binomial(2*(n-m),n-m-k),k,1,n-m)/(n-m),m,1,n-1)+1; /* Vladimir Kruchinin, Oct 11 2011 */

G.f.: 1+(2x^2) / (-1+4x-2x^2+sqrt(1-4x)).
G.f.: 1 + x * (1 - 4*x + 2*x^2 + sqrt(1 - 4*x)) / (2 * (1 - 5*x + 4*x^2 - x^3)). - Michael Somos, Jan 01 2014
G.f.: 1+x/(1-x-x/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction). [From Paul Barry, Jan 19 2009]
G.f.: 1+x/(1-x-x/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-... (continued fraction). - Paul Barry, Jul 31 2010
a(n) = sum(m=1..n-1, sum(k=1..n-m, k*binomial(m+k-1,m-1)*binomial(2*(n-m),n-m-k))/(n-m))+1, a(0)=1. - Vladimir Kruchinin, Oct 11 2011
a(n) is the upper left term in M^n, M = an infinite square production matrix with (1, 1, 2, 4, 8, 16, ... powers of 2) as the left border, as follows:
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  2, 1, 1, 1, 0, ...
  4, 1, 1, 1, 1, ...
  ... - Gary W. Adamson, Nov 14 2011
D-finite with recurrence (n-1)*a(n) + 3*(5-3*n)*a(n-1) + 6*(4*n-9)*a(n-2) + (41-17*n)*a(n-3) + 2*(2*n-5)*a(n-4) = 0. - R. J. Mathar, Nov 15 2011
0 = a(n) * (16*a(n+1) - 74*a(n+2) + 120*a(n+3) - 66*a(n+4) + 10*a(n+5))+ a(n+1) * (-62*a(n+1) + 361*a(n+2) - 480*a(n+3) + 265*a(n+4) - 41*a(n+5)) + a(n+2) * (-342*a(n+2) + 615*a(n+3) - 335*a(n+4) + 54*a(n+5)) + a(n+3) * (-90*a(n+3) + 75*a(n+4) - 15*a(n+5)) + a(n+4) * (-3*a(n+4) + a(n+5)) if n>0. - Michael Somos, Jan 01 2014
G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (2 - 3*x / (1 - 2*x / (3 - 4*x / ... ))))))). - Michael Somos, Jan 09 2014
G.f.: 2/(2-x-x/sqrt(1-4*x)). - Michael Somos, Jan 09 2014
a(n) ~ 1/(r^(n-1) * (2*r - 2 + (16*r^2 - 60*r + 65)*sqrt(1-4*r))), where r = 1/3*(4 - (2/(25-3*sqrt(69)))^(1/3) - (1/2*(25-3*sqrt(69)))^(1/3)) = 0.2451223337533... is the root of the equation 5*r-4*r^2+r^3 = 1. - Vaclav Kotesovec, Jan 12 2014
G.f.: x/(2-x-C(x)) where C(x)=(1-sqrt(1-4*x))/(2*x) is the g.f. for Catalan numbers A000108. - David Callan, Dec 03 2015

a(0)=1 prepended by Alois P. Heinz, Dec 04 2015

A235391 Duplicate of A129775.

Original entry on oeis.org

Offset: 0

Michael Somos, Jan 09 2014

dead

			G.f. = 1 + x + 2*x^2 + 6*x^3 + 21*x^4 + 78*x^5 + 298*x^6 + 1157*x^7 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A000012, A073525, A129775.

m:=25; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!(2/( 2-x - x/Sqrt(1-4*x)))); // G. C. Greubel, Aug 07 2018

a[ n_] := SeriesCoefficient[ 2 / (2 - x - x / Sqrt[1 - 4 x]), {x, 0, n}]

{a(n) = if( n<0, 0, polcoeff( 2 / (2 - x - x / sqrt(1 - 4*x + x * O(x^n))), n))}

G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (2 - 3*x / (1 - 2*x / (3 - 4*x / ... ))))))).
D-finite with recurrence: 0 = (4*n + 6) * a(n) - (17*n + 27) * a(n+1) + (24*n + 42) * a(n+2) - (9*n + 21) * a(n+3) + (n + 3) * a(n+4). - Sign flipped by R. J. Mathar, Feb 16 2020
0 = a(n) * (16*a(n+1) - 74*a(n+2) + 120*a(n+3) - 66*a(n+4) + 10*a(n+5))+ a(n+1) * (-62*a(n+1) + 361*a(n+2) - 480*a(n+3) + 265*a(n+4) - 41*a(n+5)) + a(n+2) * (-342*a(n+2) + 615*a(n+3) - 335*a(n+4) + 54*a(n+5)) + a(n+3) * (-90*a(n+3) + 75*a(n+4) - 15*a(n+5)) + a(n+4) * (-3*a(n+4) + a(n+5)).
a(n) = A129775(n) if n>0.
HANKEL transform is A000012.
INVERT transform is A073525.

cp's OEIS Frontend

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A129775 Number of maximally clustered permutations in S_n; the maximally clustered permutations are those that avoid 3421, 4312 and 4321.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

Extensions

A235391 Duplicate of A129775.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula