A005802 -id:A005802 - cp's OEIS frontend

A246065 a(n) = Sum_{k=0..n}C(n,k)^2C(2k,k)/(2k-1), where C(n,k) denotes the binomial coefficient n!/(k!(n-k)!).

-1, 1, 9, 39, 177, 927, 5463, 34857, 234657, 1641471, 11820135, 87080265, 653499135, 4979882385, 38441107305, 300027646647, 2364113123073, 18784242756927, 150351698420247, 1211310469545081, 9816017765368671, 79963826730913809, 654504197331971961, 5380270242617370951

Offset: 0

Zhi-Wei Sun, Aug 24 2014

sign

a(n) is always an integer since (2k-1)|C(2k,k) for any nonnegative integer k.
Conjecture: (i) The sequence a(n+1)/a(n) (n = 2,3,...) is strictly increasing to the limit 9, and the sequence a(n+1)^(1/(n+1))/a(n)^(1/n) (n = 1,2,3,...) is strictly decreasing to the limit 1.
(ii) sum_{k=0}^{n-1}a(k) == 0 (mod n^2) for all n > 0. Moreover, for any prime p we have sum_{k=0}^{p-1}a(k) == -p^2*(1+9*(p/3))/2 (mod p^3), where (p/3) is the Legendre symbol.
We are able to prove n | sum_{k=0}^{n-1}a(k). Note also that sum_{k=0}^{n-1}a(k)*9^(n-1-k) = -n^2*A086618(n-1) for all n > 0 since both sides satisfy the same recurrence via the Zeilberger algorithm.
The congruence (0 mod n^2) in (ii) is true, see the formula for A246138 in terms of A005802. - Mark van Hoeij, Nov 07 2023

			a(2) = 9 since Sum_{k=0,1,2}C(2,k)^2*C(2k,k)/(2k-1) = -1 + 8 + 6/3 = 9.

Zhi-Wei Sun, Table of n, a(n) for n = 0..150
Zhi-Wei Sun, A new kind of numbers and their arithmetic properties, preprint, arXiv:1408.5381 [math.NT], 2014-2018.

Cf. A086618, A245769.

a := n -> -hypergeom([-1/2, -n, -n], [1, 1], 4):
seq(simplify(a(n)), n=0..23); # Peter Luschny, Nov 07 2023
ogf := -(1-9*x)^(1/4)*hypergeom([-1/4, 3/4],[1],64*x^3/((1-9*x)*(x-1)^3))/(1-x)^(5/4);
series(ogf, x=0, 25); # Mark van Hoeij, Nov 12 2023

a[n_]:=Sum[Binomial[n,k]^2*Binomial[2k,k]/(2k-1),{k,0,n}]
Table[a[n],{n,0,20}]

Recurrence (obtained via the Zeilberger algorithm):
9*(n+1)^2*a(n) -(19n^2+58n+63)*a(n+1) + (11n^2+46n+47)*a(n+2)-(n+3)^2*a(n+3) = 0.
a(n) ~ A086618(n)/2 ~ 3^(2*n + 5/2)/(16*Pi*n^2) as n tends to the infinity.
a(n) = (9*(2*n+1)^2*A002893(n) - 4*(n+1)^2*A002893(n+1))/3. - Mark van Hoeij, Nov 07 2023
a(n) = -hypergeom([-1/2, -n, -n], [1, 1], 4). - Peter Luschny, Nov 07 2023

A246138 a(n) = (Sum_{k=0..n-1} A246065(k)) / n^2.

Original entry on oeis.org

-1, 0, 1, 3, 9, 32, 135, 648, 3409, 19176, 113535, 700125, 4463415, 29256120, 196334697, 1344542787, 9371335905, 66335058128, 476022873279, 3457886816997, 25394948961831, 188353304179920, 1409578821465129, 10635308054118792, 80845157085234975

Offset: 1

Zhi-Wei Sun, Aug 25 2014

sign

Part (ii) of the conjecture in A246065 implies that all the terms in the current sequence are integers.

Conjecture: The sequence a(n+1)/a(n) (n = 4,5,...) is strictly increasing to the limit 9, and the sequence a(n+1)^(1/(n+1))/a(n)^(1/n) (n = 3,4,...) is strictly decreasing to the limit 1.

			a(5) = 9 since sum_{k=0}^{5-1}A246065(k) = -1 + 1 + 9 + 39 + 177 = 225 = 5^2*9.

Zhi-Wei Sun, Table of n, a(n) for n = 1..170

Cf. A005802, A246065.

ogf := (1-((9*x-1)/(x-1))^(3/4)*hypergeom([-1/4, 3/4],[1],-64*x/(9*x-1)^3/(x-1)))/6;
series(ogf, x=0, 25); # Mark van Hoeij, Nov 12 2023

s[n_]:=Sum[Binomial[n,k]^2*Binomial[2k,k]/(2k-1),{k,0,n}]
a[n_]:=Sum[s[k],{k,0,n-1}]/n^2
Table[a[n],{n,1,25}]

Recurrence: n^2*a(n) = 2*(n-2)*(5*n-8)*a(n-1) - 9*(n-2)^2*a(n-2). - Vaclav Kotesovec, Aug 27 2014
a(n) ~ 3^(2*n+5/2) / (128*Pi*n^4). - Vaclav Kotesovec, Aug 27 2014
a(n) = ((3*n+2)*(3*n-2)*A005802(n-1) - (n+2)^2*A005802(n))/4. - Mark van Hoeij, Nov 06 2023

A342862 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 2143. 0 <= k <= A028723(n + 1).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 11, 4, 2, 513, 88, 53, 33, 18, 8, 6, 0, 0, 1, 2761, 642, 495, 340, 262, 160, 172, 65, 58, 39, 14, 6, 18, 0, 0, 6, 0, 0, 2, 15767, 4567, 4099, 3007, 2692, 1832, 2171, 1152, 1291, 968, 728, 457, 566, 174, 176, 221, 129, 14, 122, 29, 38, 52, 8, 0, 32, 9, 0, 10, 0, 0, 8, 0, 0, 0, 0, 0, 1

Offset: 0

Peter Kagey, Mar 26 2021

Equivalently the table for the pattern 3412.

First column is A005802.

			Triangle begins:
  n\k|       0        1        2        3        4        5        6
  ---+-------------------------------------------------------------------
   0 |       1;
   1 |       1;
   2 |       2;
   3 |       6;
   4 |      23,       1;
   5 |     103,      11,       4,       2;
   6 |     513,      88,      53,      33,      18,       8,       6, ...
   7 |    2761,     642,     495,     340,     262,     160,     172, ...
   8 |   15767,    4567,    4099,    3007,    2692,    1832,    2171, ...
   9 |   94359,   32443,   32345,   25049,   24492,   17732,   21841, ...
  10 |  586590,  232189,  250371,  203452,  211291,  160561,  201524, ...
  11 | 3763290, 1679295, 1926145, 1635315, 1776655, 1409304, 1787218, ...

Peter Kagey, Rows n = 0..13, flattened, based on Anders Kaseorg's Rust program in the Code Golf Stack Exchange link.
FindStat, St000407: The number of occurrences of the pattern 2143 in a permutation.
Anders Kaseorg, Answer: Patterns in Permutations, Code Golf Stack Exchange.

Cf. A005802, A028723.

Analogous for other patterns: A008302 (12), A138159 (321), A263771 (312), A342840 (1342), A342860 (2413), A342861 (1324), A342863 (1243), A342864 (1432), A342865 (1234).

A342863 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 1243. 0 <= k <= A028723(n + 1).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 11, 4, 2, 513, 88, 56, 32, 14, 7, 9, 0, 0, 1, 2761, 638, 543, 341, 235, 138, 173, 51, 42, 47, 34, 6, 17, 4, 0, 7, 1, 0, 2, 15767, 4478, 4600, 3119, 2658, 1710, 2180, 972, 975, 877, 771, 356, 542, 233, 184, 266, 157, 81, 130, 41, 60, 49, 16, 16, 37, 8, 9, 13, 3, 0, 10, 1, 0, 0, 0, 0, 1

Offset: 0

Peter Kagey, Mar 26 2021

Equivalently the table for the patterns 2134, 3421, and 4312.

First column is A005802.

			Table begins:
  n\k|       0        1        2        3        4        5        6
  ---+-------------------------------------------------------------------
   0 |       1;
   1 |       1;
   2 |       2;
   3 |       6;
   4 |      23,       1;
   5 |     103,      11,       4,       2;
   6 |     513,      88,      56,      32,      14,       7,       9, ...
   7 |    2761,     638,     543,     341,     235,     138,     173, ...
   8 |   15767,    4478,    4600,    3119,    2658,    1710,    2180, ...
   9 |   94359,   31199,   36691,   26602,   25756,   17628,   22984, ...
  10 |  586590,  218033,  284370,  218957,  231390,  166338,  221429, ...
  11 | 3763290, 1535207, 2174352, 1767837, 1994176, 1496134, 2028316, ...

Peter Kagey, Rows n = 0..13, flattened, based on Anders Kaseorg's Rust program in the Code Golf Stack Exchange link.
Anders Kaseorg, Answer: Patterns in Permutations, Code Golf Stack Exchange.

Cf. A005802, A028723.

Analogous for other patterns: A008302 (12), A138159 (321), A263771 (312), A342840 (1342), A342860 (2413), A342861 (1324), A342862 (2143), A342864 (1432), A342865 (1234).

A342864 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 1432. 0 <= k <= A100354(n).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 11, 5, 0, 1, 513, 87, 68, 17, 18, 10, 0, 4, 2, 0, 1, 2761, 625, 626, 268, 274, 138, 112, 58, 51, 44, 31, 9, 15, 8, 12, 0, 5, 0, 0, 0, 3, 15767, 4378, 5038, 2781, 3060, 1697, 1817, 1036, 964, 773, 656, 450, 379, 320, 285, 148, 237, 97, 98, 55, 68, 61, 23, 30, 30, 13, 30, 0, 0, 0, 16, 0, 10, 0, 0, 1, 0, 0, 0, 0, 2

Offset: 0

Peter Kagey, Mar 26 2021

Equivalently the table for the patterns 2341, 3214, and 4123.

First column is A005802.

			Table begins:
  n\k|       0        1        2        3        4        5        6
  ---+-------------------------------------------------------------------
   0 |       1;
   1 |       1;
   2 |       2;
   3 |       6;
   4 |      23,       1;
   5 |     103,      11,       5,       0,       1;
   6 |     513,      87,      68,      17,      18,      10,       0, ...
   7 |    2761,     625,     626,     268,     274,     138,     112, ...
   8 |   15767,    4378,    5038,    2781,    3060,    1697,    1817, ...
   9 |   94359,   30671,   38541,   24731,   28881,   17943,   21193, ...
  10 |  586590,  216883,  289785,  205853,  251051,  170941,  211942, ...
  11 | 3763290, 1552588, 2172387, 1663964, 2096207, 1535129, 1954751, ...

Peter Kagey, Rows n = 0..13, flattened, based on Anders Kaseorg's Rust program in the Code Golf Stack Exchange link.
Anders Kaseorg, Answer: Patterns in Permutations, Code Golf Stack Exchange.

Cf. A005802, A100354.

Analogous for other patterns: A008302 (12), A138159 (321), A263771 (312), A342840 (1342), A342860 (2413), A342861 (1324), A342862 (2143), A342863 (1243), A342865 (1234).

A342865 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 1234. 0 <= k <= A000332(n).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 12, 4, 0, 0, 1, 513, 102, 63, 10, 6, 12, 8, 0, 0, 5, 0, 0, 0, 0, 0, 1, 2761, 770, 665, 196, 146, 116, 142, 46, 10, 72, 32, 24, 0, 13, 0, 12, 18, 0, 0, 10, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Peter Kagey, Mar 26 2021

Equivalently the table for the pattern 4321.

First column is A005802.

			Table begins:
  n\k|       0        1        2        3        4        5        6
  ---+-------------------------------------------------------------------
   0 |       1;
   1 |       1;
   2 |       2;
   3 |       6;
   4 |      23,       1;
   5 |     103,      12,       4,       0,       0,       1;
   6 |     513,     102,      63,      10,       6,      12,       8, ...
   7 |    2761,     770,     665,     196,     146,     116,     142, ...
   8 |   15767,    5545,    5982,    2477,    2148,    1204,    1782, ...
   9 |   94359,   39220,   49748,   25886,   25190,   13188,   19936, ...
  10 |  586590,  276144,  396642,  244233,  260505,  142550,  210663, ...
  11 | 3763290, 1948212, 3089010, 2167834, 2493489, 1476655, 2136586, ...

Peter Kagey, Rows n = 0..13, flattened, based on Anders Kaseorg's Rust program in the Code Golf Stack Exchange link.
Anders Kaseorg, Answer: Patterns in Permutations, Code Golf Stack Exchange.

Cf. A000332, A005802.

Analogous for other patterns: A008302 (12), A138159 (321), A263771 (312), A342840 (1342), A342860 (2413), A342861 (1324), A342862 (2143), A342863 (1243), A342864 (1432).

A217057 Number of permutations in S_n containing exactly one increasing subsequence of length 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 12, 102, 770, 5545, 39220, 276144, 1948212, 13817680, 98679990, 710108396, 5150076076, 37641647410, 277202062666, 2056218941678, 15358296210724, 115469557503753, 873561194459596, 6647760790457218, 50871527629923754, 391345137795371013

Offset: 0

Alois P. Heinz, Sep 25 2012

nonn

			a(4) = 1: 1234.
a(5) = 12: 12453, 12534, 13425, 13452, 14235, 15234, 23145, 23415, 23451, 31245, 41235, 51234.

Brian Nakamura and Doron Zeilberger, Table of n, a(n) for n = 0..70
Andrew R. Conway and Anthony J. Guttmann, Counting occurrences of patterns in permutations, arXiv:2306.12682 [math.CO], 2023. See p. 16.
Brian Nakamura and Doron Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes; Local copy, pdf file only, no active links
Brian Nakamura and Doron Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes, arXiv preprint arXiv:1209.2353, 2012.
Wikipedia, Enumerations of specific permutation classes
Wikipedia, Subsequence

Cf. A005802, A117158, A158005, A214015, A214152.

# programs can be obtained from the Nakamura & Zeilberger link.

A367022 Triangle read by rows, T(n, k) = [x^k] p(n), where p(n) = 4^n * hypergeom([1/2, -n - 1, -n], [2, 2], x).

Original entry on oeis.org

1, 4, 1, 16, 12, 2, 64, 96, 48, 5, 256, 640, 640, 200, 14, 1024, 3840, 6400, 4000, 840, 42, 4096, 21504, 53760, 56000, 23520, 3528, 132, 16384, 114688, 401408, 627200, 439040, 131712, 14784, 429, 65536, 589824, 2752512, 6021120, 6322176, 3161088, 709632, 61776, 1430

Offset: 0

Peter Luschny, Nov 06 2023

			Triangle T(n, k) starts:
  [0]     1;
  [1]     4,      1;
  [2]    16,     12,       2;
  [3]    64,     96,      48,       5;
  [4]   256,    640,     640,     200,      14;
  [5]  1024,   3840,    6400,    4000,     840,      42;
  [6]  4096,  21504,   53760,   56000,   23520,    3528,    132;
  [7] 16384, 114688,  401408,  627200,  439040,  131712,  14784,   429;
  [8] 65536, 589824, 2752512, 6021120, 6322176, 3161088, 709632, 61776, 1430;

Cf. A038845 (column 1), A128088, A005802, A246513, A001263.

p := n -> 4^n*hypergeom([1/2, -n - 1, -n], [2, 2], x):
T := (n, k) -> coeff(simplify(p(n)), x, k):
seq(seq(T(n, k), k = 0..n), n = 0..8);

T[n_,k_]:=4^(n-k)*Binomial[n,k]*Binomial[n+1,k]*Binomial[2*k,k]/(k+1)^2;Flatten[Table[T[n,k],{n,0,8},{k,0,n}]] (* Detlef Meya, Nov 20 2023 *)

From Detlef Meya, Nov 20 2023: (Start)
T(n, k) = 4^(n - k)*binomial(n, k)*binomial(n+1, k)*binomial(2*k, k)/(k + 1)^2.
T(n, k) = A001263(n+1, k+1)*4^(n - k)*binomial(2*k, k)/(k + 1). (End)

A128088 a(n) = Sum_{k=0..n} A000108(k)*A001263(n+1,k+1), where A000108 is the Catalan numbers and A001263 is the Narayana triangle.

Original entry on oeis.org

1, 2, 6, 24, 115, 618, 3591, 22088, 141903, 943590, 6452490, 45159480, 322305165, 2339100078, 17223121350, 128428689888, 968383277791, 7374380672718, 56655414930642, 438741242896680, 3422125459579869, 26866961380274598, 212191772351034249, 1685036376746788392

Offset: 0

Paul D. Hanna, Feb 23 2007

nonn

a(n) is the number of permutations of length n+1 avoiding the partially ordered pattern (POP) {1>2>3>4} of length 5. That is, the number of length n+1 permutations having no subsequences of length 5 in which the element in position 1 is larger than the element in position 2, which in turn is larger than the element in position 3, and that element is larger than the element in position 4. - Sergey Kitaev, Dec 13 2020

			Illustrate a(n) = Sum_{k=0..n} A000108(k)*A001263(n+1,k+1) by:
a(2) = 1*(1) + 1*(3) + 2*(1) = 6;
a(3) = 1*(1) + 1*(6) + 2*(6) + 5*(1) = 24;
a(4) = 1*(1) + 1*(10)+ 2*(20)+ 5*(10)+ 14*(1) = 115.
The Narayana triangle A001263(n+1,k+1) = C(n,k)*C(n+1,k)/(k+1) begins:
1;
1, 1;
1, 3, 1;
1, 6, 6, 1;
1, 10, 20, 10, 1;
1, 15, 50, 50, 15, 1; ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

Cf. A005802, A000108, A001263, A259833.

a := n -> hypergeom([1/2, -n - 1, -n], [2, 2], 4):
seq(simplify(a(n)), n = 0..23);  # Peter Luschny, Nov 06 2023

Table[Sum[Binomial[2*k,k]*Binomial[n,k]*Binomial[n+1,k]/(k+1)^2,{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 20 2012 *)
Table[HypergeometricPFQ[{1/2, -1 - n, -n}, {2, 2}, 4], {n, 0, 20}] (* Vaclav Kotesovec, May 14 2016 *)

{a(n)=sum(k=0,n,binomial(2*k,k)*binomial(n,k)*binomial(n+1,k)/(k+1)^2)}

a(n) = (n+1)*A005802(n), where A005802(n) = number of permutations in S_n with longest increasing subsequence of length <= 3.
a(n) = Sum_{k=0..n} C(2k,k)*C(n,k)*C(n+1,k)/(k+1)^2.
Recurrence: (n+2)^2*a(n) = (n+1)*(7*n+2)*a(n-1) + 3*(n-2)*(7*n-4)*a(n-2) - 27*(n-2)*(n-1)*a(n-3) . - Vaclav Kotesovec, Oct 20 2012
a(n) ~ 3^(2*n+9/2)/(16*Pi*n^3). - Vaclav Kotesovec, Oct 20 2012
a(n) = hypergeom([1/2, -n - 1, -n], [2, 2], 4). - Vaclav Kotesovec, May 14 2016

A223905 Number of 4-vexillary permutations in S_n, that is, permutations whose Stanley symmetric function has at most 4 terms or at most 4 Edelman-Greene tableaux.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 717, 4824, 34629, 256689, 1935301

Offset: 0

Sara Billey, Apr 04 2013

This family is characterized by a finite set of patterns.

S. Billey and B. Pawlowski, Permutation Patterns, Stanley symmetric functions and generalized Specht modules, arXiv:1304.7870 [math.CO], 2013.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.

Cf. A005802, A224318.

a(0)=1 prepended by Alois P. Heinz, Jul 31 2019

cp's OEIS Frontend

A246065 a(n) = Sum_{k=0..n}C(n,k)^2*C(2k,k)/(2k-1), where C(n,k) denotes the binomial coefficient n!/(k!*(n-k)!).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246138 a(n) = (Sum_{k=0..n-1} A246065(k)) / n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A342862 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 2143. 0 <= k <= A028723(n + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A342863 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 1243. 0 <= k <= A028723(n + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A342864 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 1432. 0 <= k <= A100354(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A342865 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 1234. 0 <= k <= A000332(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A217057 Number of permutations in S_n containing exactly one increasing subsequence of length 4.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A367022 Triangle read by rows, T(n, k) = [x^k] p(n), where p(n) = 4^n * hypergeom([1/2, -n - 1, -n], [2, 2], x).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A128088 a(n) = Sum_{k=0..n} A000108(k)*A001263(n+1,k+1), where A000108 is the Catalan numbers and A001263 is the Narayana triangle.

Views

Author

Keywords

A246065 a(n) = Sum_{k=0..n}C(n,k)^2C(2k,k)/(2k-1), where C(n,k) denotes the binomial coefficient n!/(k!(n-k)!).