A094219 -id:A094219 - cp's OEIS frontend

A263776 Triangle read by rows: T(n,k) (n>=0, 0<=k<=A002620(n-1)) is the number of permutations of [n] with k nestings.

1, 1, 2, 5, 1, 14, 8, 2, 42, 45, 25, 7, 1, 132, 220, 198, 112, 44, 12, 2, 429, 1001, 1274, 1092, 700, 352, 140, 42, 9, 1, 1430, 4368, 7280, 8400, 7460, 5392, 3262, 1664, 716, 256, 74, 16, 2, 4862, 18564, 38556, 56100, 63648, 59670, 47802, 33338, 20466, 11115

Offset: 0

Christian Stump, Oct 26 2015

Row sums give A000142.
First column gives A000108.
Also the number of permutations of [n] with k crossings (see Corteel, Proposition 4).
Also the number of permutations of [n] with exactly k (possibly overlapping) occurrences of the generalized pattern 13-2 (alternatively: 2-13, 2-31, or 31-2). - Alois P. Heinz, Nov 14 2015

			Triangle begins:
0 :   1;
1 :   1;
2 :   2;
3 :   5,    1;
4 :  14,    8,    2;
5 :  42,   45,   25,    7,   1;
6 : 132,  220,  198,  112,  44,  12,   2;
7 : 429, 1001, 1274, 1092, 700, 352, 140, 42, 9, 1;
...

Alois P. Heinz, Rows n = 0..50, flattened
A. Claesson and T. Mansour, Counting occurrences of a pattern of type (1,2) or (2,1) in permutations, arXiv:math/0110036 [math.CO], 2001.
S. Corteel, Crossings and alignments of permutations, Adv. Appl. Math 38 (2007) 149-163.
FindStat - Combinatorial Statistic Finder, The number of nestings of a permutation, The number of crossings of a permutation
R. Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.
Lucas Sá and Antonio M. García-García, The Wishart-Sachdev-Ye-Kitaev model: Q-Laguerre spectral density and quantum chaos, arXiv:2104.07647 [hep-th], 2021.

Columns k=0-10 give: A000108, A002696, A094218, A094219, A120812, A120813, A120814, A120815, A120816, A264496, A264497.

Cf. A000142, A001754, A002620, A260665, A260670, A287328, A291722.

b:= proc(u, o) option remember;
      `if`(u+o=0, 1, add(b(u-j, o+j-1), j=1..u)+
       add(expand(b(u+j-1, o-j)*x^(j-1)), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);  # Alois P. Heinz, Nov 14 2015

b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[u-j, o+j-1], {j, 1, u}] + Sum[Expand[b[u+j-1, o-j]*x^(j-1)], {j, 1, o}]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[ T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 31 2016, after Alois P. Heinz *)

Sum_{k>0} k * T(n,k) = A001754(n).

T(n,n) = A287328(n). - Alois P. Heinz, Aug 31 2017

More terms from Alois P. Heinz, Oct 26 2015

A094218 Number of permutations of length n with exactly 2 occurrences of the pattern 2-13.

Original entry on oeis.org

0, 0, 0, 2, 25, 198, 1274, 7280, 38556, 193800, 937992, 4412826, 20309575, 91861770, 409704750, 1806342720, 7887861960, 34166674800, 146977222320, 628521016500, 2673950235138, 11324837666604, 47773836727540, 200828153398752

Offset: 1

Benoit Cloitre, May 27 2004

nonn

R. Lie, Permutations and Patterns, Master's Thesis, Goeteborg, Sweden: Chalmers University of Technology, 2004.

Alois P. Heinz, Table of n, a(n) for n = 1..500
Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Cf. A094219, A001622.

Column k=2 of A263776.

[n*Binomial(2*n,n-4)/2: n in [1..30]]; // Vincenzo Librandi, Aug 20 2015

Table[n Binomial[2 n, n - 4]/2, {n, 30}] (* Vincenzo Librandi, Aug 20 2015 *)

PARI
```
a(n)=n*binomial(2*n,n-4)/2
```

a(n) = n*binomial(2*n,n-4)/2.
From Amiram Eldar, May 04 2025: (Start)
Sum_{n>=4} 1/a(n) = 1147/45 - 34*Pi/(3*sqrt(3)) - 4*Pi^2/9.
Sum_{n>=4} (-1)^n/a(n) = 16*log(phi)^2 + 1588*log(phi)/(3*sqrt(5)) - 5272/45, where phi is the golden ratio (A001622). (End)

A120812 Number of permutations of length n with exactly 4 occurrences of the pattern 2-13.

Original entry on oeis.org

1, 44, 700, 7460, 63648, 470934, 3155691, 19660630, 115855025, 653392740, 3556757490, 18805317960, 97034823600, 490465092600, 2435567286708, 11910569958216, 57470522059594, 274051266477560, 1293219035408080

Offset: 5

Robert Parviainen (robertp(AT)ms.unimelb.edu.au), Jul 05 2006

nonn

R. Parviainen, Lattice path enumeration of permutations with k occurrences of the pattern 2-13, preprint, 2006.
Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Alois P. Heinz, Table of n, a(n) for n = 5..500
R. Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Cf. A002629, A094218, A094219, A120813-A120816.

Column k=4 of A263776.

a(n) = (-36 - 100 m - 13 m^2 + 4 m^3 + m^4)/(24(m + 6))Binomial[2m, m - 5]; generating function = x^5 C^11 (5 - 118C + 259C^2 - 240C^3 + 142C^4 - 62C^5 + 17C^6 - 2 C^7)/(2-C)^7, where C=(1-Sqrt[1-4x])/(2x) is the Catalan function.

A120816 Number of permutations of length n with exactly 8 occurrences of the pattern 2-13.

Original entry on oeis.org

9, 716, 20466, 365996, 4939341, 55098294, 535240680, 4680045630, 37665984798, 283492037268, 2018852205700, 13724440760376, 89682252682256, 566388685336800, 3472428372731880, 20740959695100150, 121059468257664984

Offset: 7

Robert Parviainen (robertp(AT)ms.unimelb.edu.au), Jul 06 2006

nonn

R. Parviainen, Lattice path enumeration of permutations with k occurrences of the pattern 2-13, preprint, 2006.
Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Alois P. Heinz, Table of n, a(n) for n = 7..500
R. Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Cf. A002629, A094218, A094219, A120812-A120815.

Column k=8 of A263776.

a(n) = (-7983360 - 12956832n + 10475400n^2 + 3647724n^3 - 416326n^4 - 249417n^5 - 19971n^6 + 2646n^7 + 576n^8 + 39n^9 + n^10)/(40320(n+8)(n+9)(n+10))Binomial[2n, n-7]; generating function = x^7 C^15(29 - 65536C + 499576C^2 - 1679496C^3 + 3298054C^4 - 4270444C^5 + 3911698C^6 - 2671744C^7 + 1439239C^8 - 659504C^9 + 279446C^10 - 112922C^11 + 41165C^12 - 12362C^13 + 2816C^14 - 448C^15 + 44C^16 - 2C^17)/(2-C)^15, where C=(1-Sqrt[1-4x])/(2x) is the Catalan function.

A120813 Number of permutations of length n with exactly 5 occurrences of the pattern 2-13.

Original entry on oeis.org

0, 0, 0, 0, 0, 12, 352, 5392, 59670, 541044, 4285127, 30772896, 205200710, 1291195620, 7754735430, 44827592160, 251003101440, 1368033658992, 7285815623268, 38033923266368, 195107105534280, 985573624414808, 4911044001390648

Offset: 1

Robert Parviainen (robertp(AT)ms.unimelb.edu.au), Jul 06 2006, entries corrected Feb 08 2008

nonn

R. Parviainen, Lattice path enumeration of permutations with k occurrences of the pattern 2-13, preprint, 2006.
Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Alois P. Heinz, Table of n, a(n) for n = 1..500
R. Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Cf. A002629, A094218, A094219, A120812, A120814-A120816.

Column k=5 of A263776.

a(n) = ((n+4)(-108 - 192 n +3 n^2 + 8 n^3 + n^4))/(120(n + 7))binomial[2n, n - 6]; generating function = x^6 C^13 (-14 - 540C + 1519C^2 - 1517C^3 + 616C^4 + 70C^5 - 199C^6 + 97C^7 - 22C^8 + 2C^9)/(2-C)^9, where C=(1-Sqrt[1-4x])/(2x) is the Catalan function.

A120814 Number of permutations of length n with exactly 6 occurrences of the pattern 2-13.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 140, 3262, 47802, 535990, 5038418, 41781432, 315447990, 2214289350, 14664659100, 92612930280, 562220244768, 3301016862024, 18836205435208, 104862661271840, 571336322754792, 3054404571541092, 16056744308319000

Offset: 1

Robert Parviainen (robertp(AT)ms.unimelb.edu.au), Jul 06 2006

nonn

R. Parviainen, Lattice path enumeration of permutations with k occurrences of the pattern 2-13, preprint, 2006.
Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Alois P. Heinz, Table of n, a(n) for n = 1..500
R. Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Cf. A002629, A094218, A094219, A120812-A120813, A120815-A120816.

Column k=6 of A263776.

a(n) = (20160 + 44448n + 548n^2 - 4196n^3 - 565n^4 + 67n^5 + 17n^6 + n^7)/(720(n+7)(n+6))binomial[2n, n-6]; generating function = x^6 C^13 (-42 + 4054C - 18354C^2 + 36038C^3 - 40660C^4 + 30080C^5 - 16090C^6 + 6914C^7 - 2604C^8 + 840C^9 - 202C^10 + 30C^11 - 2C^12)/(2-C)^11, where C=(1-Sqrt[1-4x])/(2x) is the Catalan function.

A120815 Number of permutations of length n with exactly 7 occurrences of the pattern 2-13.

Original entry on oeis.org

42, 1664, 33338, 468200, 5253864, 50442128, 431645370, 3380738400, 24682378500, 170201240352, 1119398566704, 7074531999584, 43215257135312, 256343213520000, 1482127305153560, 8378542979807616, 46428426576857886

Offset: 7

Robert Parviainen (robertp(AT)ms.unimelb.edu.au), Jul 06 2006; definition corrected Feb 08 2008

R. Parviainen, Lattice path enumeration of permutations with k occurrences of the pattern 2-13, preprint, 2006.
Robert Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Alois P. Heinz, Table of n, a(n) for n = 7..500
R. Parviainen, Lattice Path Enumeration of Permutations with k Occurrences of the Pattern 2-13, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.2.

Cf. A002629, A094218, A094219, A120812-A120814, A120816.

Column k=7 of A263776.

a(n) = (n+5)*(40320 + 67824*n - 20180*n^2 - 7556*n^3 - 5*n^4 + 211*n^5 + 25*n^6 + n^7)*binomial(2*n, n-7)/(5040*(n+8)*(n+9)).

G.f.: x^7*C^15*(132 + 16516*C - 92666*C^2 + 215944*C^3 - 281094*C^4 + 225628*C^5 - 110922*C^6 + 25360*C^7 + 7066*C^8 - 9364*C^9 + 4622*C^10 - 1440*C^11 + 294*C^12 - 36*C^13 + 2*C^14)/(2-C)^13, where C=(1-sqrt(1-4*x))/(2*x) is the Catalan function.

cp's OEIS Frontend

A263776 Triangle read by rows: T(n,k) (n>=0, 0<=k<=A002620(n-1)) is the number of permutations of [n] with k nestings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A094218 Number of permutations of length n with exactly 2 occurrences of the pattern 2-13.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A120812 Number of permutations of length n with exactly 4 occurrences of the pattern 2-13.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A120816 Number of permutations of length n with exactly 8 occurrences of the pattern 2-13.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A120813 Number of permutations of length n with exactly 5 occurrences of the pattern 2-13.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A120814 Number of permutations of length n with exactly 6 occurrences of the pattern 2-13.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A120815 Number of permutations of length n with exactly 7 occurrences of the pattern 2-13.

Views

Author

Keywords

References

Links

Crossrefs

Formula