A002629 -id:A002629 - cp's OEIS frontend

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

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.

A047921 Triangle of numbers a(n,k) = number of permutations on n letters containing k 3-sequences (n >= 0, 0<=k<=max(0,n-2)).

Original entry on oeis.org

1, 1, 2, 5, 1, 21, 2, 1, 106, 11, 2, 1, 643, 62, 12, 2, 1, 4547, 406, 71, 13, 2, 1, 36696, 3046, 481, 80, 14, 2, 1, 332769, 25737, 3708, 559, 89, 15, 2, 1, 3349507, 242094, 32028, 4414, 640, 98, 16, 2, 1, 37054436, 2510733, 306723, 38893, 5164, 724, 107, 17, 2, 1

Offset: 0

N. J. A. Sloane

			Triangle begins:
       1;
       1;
       2;
       5,     1;
      21,     2,    1;
     106,    11,    2,   1;
     643,    62,   12,   2,  1;
    4547,   406,   71,  13,  2,  1;
   36696,  3046,  481,  80, 14,  2, 1;
  332769, 25737, 3708, 559, 89, 15, 2, 1;
  ...

J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.

Columns give A002628, A002629, A002630.

Row sums give A000142.

Riordan gives a recurrence.

Edited and extended by Max Alekseyev, Sep 05 2010

a(0,0) = a(1,0) = 1 prepended by Alois P. Heinz, Apr 20 2021

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.

A180185 Triangle read by rows: T(n,k) is the number of permutations of [n] having no 3-sequences and having k successions (0 <= k <= floor(n/2)); a succession of a permutation p is a position i such that p(i +1) - p(i) = 1.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 11, 9, 1, 53, 44, 9, 309, 265, 66, 3, 2119, 1854, 530, 44, 16687, 14833, 4635, 530, 11, 148329, 133496, 44499, 6180, 265, 1468457, 1334961, 467236, 74165, 4635, 53, 16019531, 14684570, 5339844, 934472, 74165, 1854, 190899411

Offset: 0

Emeric Deutsch, Sep 06 2010

Row n has 1+floor(n/2) entries.

Sum of entries in row n is A002628(n).

			T(6,3)=3 because we have 125634, 341256, and 563412.
Triangle starts:
     1;
     1;
     1,    1;
     3,    2;
    11,    9,    1;
    53,   44,    9;
   309,  265,   66,    3;
  2119, 1854,  530,   44;

Cf. A000166, A002628, A002629, A000255.

d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n, k) if n = 0 and k = 0 then 1 elif k <= (1/2)*n then binomial(n-k, k)*d[n+1-k]/(n-k) else 0 end if end proc: for n from 0 to 12 do seq(a(n, k), k = 0 .. (1/2)*n) end do; # yields sequence in triangular form

d[0] = 1; d[n_] := d[n] = n d[n - 1] + (-1)^n;
T[n_, k_] := If[n == 0 && k == 0, 1, If[k <= n/2, Binomial[n - k, k] d[n + 1 - k]/(n - k), 0]];
Table[T[n, k], {n, 0, 20}, {k, 0, Quotient[n, 2]}] // Flatten (* Jean-François Alcover, May 23 2020 *)

d(n) = if(n<2, !n , round(n!/exp(1)));
for(n=0, 20, for(k=0, (n\2), print1(binomial(n - k, k)*(d(n - k) + d(n - k - 1)),", ");); print();) \\ Indranil Ghosh, Apr 12 2017

T(n,k) = binomial(n-k,k)*(d(n-k) + d(n-k-1)), where d(j) = A000166(j) are the derangement numbers.
T(n,0) = d(n) + d(n-1) = A000255(n-1).
T(n,1) = d(n).
Sum_{k>=0} k*T(n,k) = A002629(n+1).

cp's OEIS Frontend

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

A047921 Triangle of numbers a(n,k) = number of permutations on n letters containing k 3-sequences (n >= 0, 0<=k<=max(0,n-2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

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

A180185 Triangle read by rows: T(n,k) is the number of permutations of [n] having no 3-sequences and having k successions (0 <= k <= floor(n/2)); a succession of a permutation p is a position i such that p(i +1) - p(i) = 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula