A263771 -id:A263771 - cp's OEIS frontend

A002054 Binomial coefficient C(2n+1, n-1).

1, 5, 21, 84, 330, 1287, 5005, 19448, 75582, 293930, 1144066, 4457400, 17383860, 67863915, 265182525, 1037158320, 4059928950, 15905368710, 62359143990, 244662670200, 960566918220, 3773655750150, 14833897694226, 58343356817424, 229591913401900

Offset: 1

N. J. A. Sloane

a(n) = number of permutations in S_{n+2} containing exactly one 312 pattern. E.g., S_3 has a_1 = 1 permutations containing exactly one 312 pattern, and S_4 has a_2 = 5 permutations containing exactly one 312 pattern, namely 1423, 2413, 3124, 3142, and 4231. This comment is also true if 312 is replaced by any of 132, 213, or 231 (but not 123 or 321, for which see A003517). [Comment revised by N. J. A. Sloane, Nov 26 2022]
Number of valleys in all Dyck paths of semilength n+1. Example: a(2)=5 because UD*UD*UD, UD*UUDD, UUDD*UD, UUD*UDD, UUUDDD, where U=(1,1), D=(1,-1) and the valleys are shown by *. - Emeric Deutsch, Dec 05 2003
Number of UU's (double rises) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDU*UDD, U*UDDUD, U*UDUDD, U*U*UDDD, the double rises being shown by *. - Emeric Deutsch, Dec 05 2003
Number of peaks at level higher than one (high peaks) in all Dyck paths of semilength n+1. Example: a(2)=5 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUU*DDD, the high peaks being shown by *. - Emeric Deutsch, Dec 05 2003
Number of diagonal dissections of a convex (n+3)-gon into n regions. Number of standard tableaux of shape (n,n,1) (see Stanley reference). - Emeric Deutsch, May 20 2004
Number of dissections of a convex (n+3)-gon by noncrossing diagonals into several regions, exactly n-1 of which are triangular. Example: a(2)=5 because the convex pentagon ABCDE is dissected by any of the diagonals AC, BD, CE, DA, EB into regions containing exactly 1 triangle. - Emeric Deutsch, May 31 2004
Number of jumps in all full binary trees with n+1 internal nodes. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007
a(n) is the total number of nonempty Dyck subpaths in all Dyck paths (A000108) of semilength n. For example, the Dyck path UUDUUDDD has Dyck subpaths stretching over positions 1-8 (the entire path), 2-3, 2-7, 4-7, 5-6 and so contributes 5 to a(4). - David Callan, Jul 25 2008
a(n+1) is the total number of ascents in the set of all n-permutations avoiding the pattern 132. For example, a(2) = 5 because there are 5 ascents in the set 123, 213, 231, 312, 321. - Cheyne Homberger, Oct 25 2013
Number of increasing tableaux of shape (n+1,n+1) with largest entry 2n+1. An increasing tableau is a semistandard tableau with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 5 counts the five tableaux (124)(235), (123)(245), (124)(345), (134)(245), (123)(245). - Oliver Pechenik, May 02 2014
a(n) is the number of noncrossing partitions of 2n+1 into n-1 blocks of size 2 and 1 block of size 3. - Oliver Pechenik, May 02 2014
Number of paths in the half-plane x>=0, from (0,0) to (2n+1,3), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 5 paths: UUUUD, UUUDU, UUDUU, UDUUU, DUUUU. - José Luis Ramírez Ramírez, Apr 19 2015
From Gus Wiseman, Aug 20 2021: (Start)
Also the number of binary numbers with 2n+2 digits and with two more 0's than 1's. For example, the a(2) = 5 binary numbers are: 100001, 100010, 100100, 101000, 110000, with decimal values 33, 34, 36, 40, 48. Allowing first digit 0 gives A001791, ranked by A345910/A345912.
Also the number of integer compositions of 2n+2 with alternating sum -2, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(3) = 21 compositions are:
  (35)  (152)  (1124)  (11141)  (111113)
        (251)  (1223)  (12131)  (111212)
               (1322)  (13121)  (111311)
               (1421)  (14111)  (121112)
               (2114)           (121211)
               (2213)           (131111)
               (2312)
               (2411)
The following pertain to these compositions:
- The unordered version is A344741.
- Ranked by A345924 (reverse: A345923).
- A345197 counts compositions by length and alternating sum.
- A345925 ranks compositions with alternating sum 2 (reverse: A345922).
(End)

			G.f. = x + 5*x^2 + 21*x^3 + 84*x^4 + 330*x^5 + 1287*x^6 + 5005*x^7 + ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
George Grätzer, General Lattice Theory. Birkhauser, Basel, 1998, 2nd edition, p. 474, line -3.
A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..100 computed by T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
F. R. Bernhart and N. J. A. Sloane, Emails, April-May 1994.
Jean-Luc Baril and Sergey Kirgizov, The pure descent statistic on permutations, Discrete Mathematics, Vol. 340, No. 10 (2017), pp. 2550-2558; preprint, 2017.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck Paths with catastrophes modulo the positions of a given pattern, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.
David Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.
Arthur Cayley, On the partitions of a polygon, Proc. London Math. Soc., Vol. 22 (1891), pp. 237-262 = Collected Mathematical Papers, Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff.
Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.
Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.
Emeric Deutsch, Dyck path enumeration, Discrete Math., Vol. 204, No. 1-3 (1999), pp. 167-202.
Gennady Eremin, Dyck Numbers, IV. Nested patterns in OEIS A036991, arXiv:2306.10318 [math.CO], 2023. See (5) p. 7.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, J. Int. Seq., Vol. 17 (2014), Article 14.1.5; arXiv preprint, arXiv:1203.6792 [math.CO], 2012.
Xiaoyu He, Emily Huang, Ihyun Nam and Rishubh Thaper, Shuffle Squares and Reverse Shuffle Squares, arXiv:2109.12455 [math.CO], 2021.
Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k, arXiv:2204.14023 [math.CO], 2022.
Milan Janjic, Two Enumerative Functions.
Werner Krandick, Trees and jumps and real roots, J. Computational and Applied Math., Vol. 162, No. 1 (2004), pp. 51-55.
Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
Toufik Mansour and Alek Vainshtein, Counting occurrences of 123 in a permutation, arXiv:math/0105073 [math.CO], 2001.
Henri Mühle, Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices, arXiv:1509.06942 [math.CO], 2015.
Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Vol. 15 (2012), Article 12.3.3.
John Noonan and Doron Zeilberger, The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns, arXiv:math/9808080 [math.CO], 1998.
Oliver Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, arXiv:1209.1355 [math.CO], 2012-2014.
Oliver Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory A, Vol. 125 (2014), pp. 357-378.
Karol Penson, Hausdorff moment problems for combinatorial numbers: heuristics via Meijer G-functions, Nov. 2022.
Ronald C. Read, On general dissections of a polygon, Aequationes Mathematicae, Vol. 18, No. 1-2 (1978), pp. 370-388; Preprint, 1974.
Mark Shattuck, Enumeration of non-crossing partitions according to subwords with repeated letters, arXiv:2303.06300 [math.CO], 2023.
Richard P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, Vol. 76 , No. 1 (1996), pp. 175-177.
Daniel W. Stasiuk, An Enumeration Problem for Sequences of n-ary Trees Arising from Algebraic Operads, Master's Thesis, University of Saskatchewan-Saskatoon (2018).
A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, arXiv:1108.2993 [hep-ph], 2011.
N. J. Wildberger and Dean Rubine, A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode, Amer. Math. Monthly (2025). See section 12.

Diagonal 4 of triangle A100257. Also a diagonal of A033282.
Equals (1/2) A024483(n+2). Bisection of A037951 and A037955.
Cf. A001263.
Column k=1 of A263771.
Counts terms of A031445 with 2n+2 digits in binary.
Cf. A000097, A000346, A000984, A001622, A001700, A007318, A008549, A031444, A058622, A097805, A116406, A138364, A163493, A202736.
Cf. binomial(2*n+m, n): A000984 (m = 0), A001700 (m = 1), A001791 (m = 2), A002694 (m = 4), A003516 (m = 5), A002696 (m = 6), A030053 - A030056, A004310 - A004318.

List([1..25],n->Binomial(2*n+1,n-1)); # Muniru A Asiru, Aug 09 2018

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

with(combstruct): seq((count(Composition(2*n+2), size=n)), n=1..24); # Zerinvary Lajos, May 03 2007

CoefficientList[Series[8/(((Sqrt[1-4x] +1)^3)*Sqrt[1-4x]), {x,0,22}], x] (* Robert G. Wilson v, Aug 08 2011 *)
a[ n_]:= Binomial[2 n + 1, n - 1]; (* Michael Somos, Apr 25 2014 *)

PARI
```
{a(n) = binomial( 2*n+1, n-1)};
```

from _future_ import division
A002054_list, b = [], 1
for n in range(1,10**3):
    A002054_list.append(b)
    b = b*(2*n+2)*(2*n+3)//(n*(n+3)) # Chai Wah Wu, Jan 26 2016

[binomial(2*n+1, n-1) for n in (1..25)] # G. C. Greubel, Mar 22 2019

a(n) = Sum_{j=0..n-1} binomial(2*j, j) * binomial(2*n - 2*j, n-j-1)/(j+1). - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
G.f.: z*C^4/(2-C), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. - Emeric Deutsch, Jul 05 2003
From Wolfdieter Lang, Jan 09 2004: (Start)
a(n) = binomial(2*n+1, n-1) = n*C(n+1)/2, C(n)=A000108(n) (Catalan).
G.f.: (1 - 2*x - (1-3*x)*c(x))/(x*(1-4*x)) with g.f. c(x) of A000108. (End)
G.f.: z*C(z)^3/(1-2*z*C(z)), where C(z) is the g.f. of Catalan numbers. - José Luis Ramírez Ramírez, Apr 19 2015
G.f.: 2F1(5/2, 2; 4; 4*x). - R. J. Mathar, Aug 09 2015
D-finite with recurrence: a(n+1) = a(n)*(2*n+3)*(2*n+2)/(n*(n+3)). - Chai Wah Wu, Jan 26 2016
From Ilya Gutkovskiy, Aug 30 2016: (Start)
E.g.f.: (BesselI(0,2*x) + (1 - 1/x)*BesselI(1,2*x))*exp(2*x).
a(n) ~ 2^(2*n+1)/sqrt(Pi*n). (End)
a(n) = (1/(n+1))*Sum_{i=0..n-1} (n+1-i)*binomial(2n+2,i), n >= 1. - Taras Goy, Aug 09 2018
G.f.: (x - 1 + (1 - 3*x)/sqrt(1 - 4*x))/(2*x^2). - Michael Somos, Jul 28 2021
From Amiram Eldar, Jan 24 2022: (Start)
Sum_{n>=1} 1/a(n) = 5/3 - 2*Pi/(9*sqrt(3)).
Sum_{n>=1} (-1)^(n+1)/a(n) = 52*log(phi)/(5*sqrt(5)) - 7/5, where phi is the golden ratio (A001622). (End)
a(n) = A001405(2*n+1) - A000108(n+1), n >= 1 (from Eremin link, page 7). - Gennady Eremin, Sep 05 2023
G.f.: x/(1 - 4*x)^2 * c(-x/(1 - 4*x))^3, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Feb 03 2024
From Peter Bala, Oct 13 2024: (Start)
a(n) = Integral_{x = 0..4} x^n * w(x) dx, where the weight function w(x) = 1/(2*Pi) * sqrt(x)*(x - 3)/sqrt(4 - x) (see Penson).
G.f. x*/sqrt(1 - 4*x) * c(x)^3. (End)

A138159 Triangle read by rows: T(n,k) is the number of permutations of [n] having k occurrences of the pattern 321 (n>=1, 0<=k<=n(n-1)(n-2)/6).

Original entry on oeis.org

1, 1, 2, 5, 1, 14, 6, 3, 0, 1, 42, 27, 24, 7, 9, 6, 0, 4, 0, 0, 1, 132, 110, 133, 70, 74, 54, 37, 32, 24, 12, 16, 6, 6, 8, 0, 0, 5, 0, 0, 0, 1, 429, 429, 635, 461, 507, 395, 387, 320, 260, 232, 191, 162, 104, 130, 100, 24, 74, 62, 18, 32, 10, 30, 13, 8, 0, 10, 10, 0, 0, 0, 6, 0, 0, 0, 0, 1

Offset: 0

Emeric Deutsch, Mar 27 2008

Row n has 1 + n(n-1)(n-2)/6 terms.
Sum of row n is n! (A000142).
T(n,0) = A000108(n) (the Catalan numbers).
T(n,1) = A003517(n-1).
T(n,2) = A001089(n).
Sum_{k>=0} k * T(n,k) = A001810(n).

			T(4,2) = 3 because we have 4312, 4231 and 3421.
Triangle starts:
    1;
    1;
    2;
    5,   1;
   14,   6,   3,  0,  1;
   42,  27,  24,  7,  9,  6,  0,  4,  0,  0,  1;
  132, 110, 133, 70, 74, 54, 37, 32, 24, 12, 16, 6, 6, 8, 0, 0, 5, 0, 0, 0, 1;
  ...

Alois P. Heinz, Rows n = 0..15, flattened
D. Callan, A recursive bijective approach to counting permutations containing 3-letter patterns, arXiv:math/0211380 [math.CO], 2002.
FindStat - Combinatorial Statistic Finder, The number of occurrences of the pattern [1,2,3] inside a permutation of length at least 3
M. Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. Appl. Math., 30, 2003, 607-632. also Arxiv CO/0112092.
Toufik Mansour, Sherry H. F. Yan and Laura L. M. Yang, Counting occurrences of 231 in an involution, Discrete Mathematics 306 (2006), pages 564-572.
J. Noonan, The number of permutations containing exactly one increasing subsequence of length three, Discrete Math. 152 (1996), no. 1-3, 307-313.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns, arXiv:math/9808080 [math.CO], 1998.
J. Noonan and D. Zeilberger, The enumeration of permutations with a prescribed number of "forbidden" patterns, Adv. Appl. Math., 17, 1996, 381-407.

Cf. A000108, A000142, A000292, A003517, A001089, A001810, A056986, A263771.

# The following Maple program yields row 9 of the triangle; change the value of n to obtain other rows.
n:=9: with(combinat): P:=permute(n): f:=proc(k) local L: L:=proc(j) local ct, i: ct:=0: for i to j-1 do if P[k][j] < P[k][i] then ct:=ct+1 else end if end do: ct end proc: add(L(j)*(L(j)+P[k][j]-j),j=1..n) end proc: a:=sort([seq(f(k),k=1..factorial(n))]): for h from 0 to (1/6)*n*(n-1)*(n-2) do c[h]:=0: for m to factorial(n) do if a[m]=h then c[h]:=c[h]+1 else end if end do end do: seq(c[h],h=0..(1/6)*n*(n-1)*(n-2));
# second Maple program:
b:= proc(s, c) option remember; (n-> `if`(n=0, x^c, add(b(s minus {j},
      (t-> (j-n+t)*t+c)(nops(select(x-> x>j, s)))), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n}, 0)):
seq(T(n), n=0..9);  # Alois P. Heinz, Dec 01 2021

ro[n_] := With[{}, P = Permutations[Range[n]]; f[k_] := With[{}, L[j_] := With[{}, ct = 0; Do[If[P[[k, j]] < P[[k, i]], ct = ct + 1], {i, 1, j - 1}]; ct]; Sum[L[j]*(L[j] + P[[k, j]] - j), {j, 1, n}]]; a = Sort[Table[f[k], {k, 1, n!}]]; Do[c[h] = 0; Do[If[a[[m]] == h, c[h] = c[h] + 1], {m, 1, n!}], {h, 0, (1/6)*n*(n - 1)*(n - 2)}]; Table[c[h], {h, 0, (1/6)*n*(n - 1)*(n - 2)}]]; Flatten[Table[ro[n], {n, 1, 7}]] (* Jean-François Alcover, Sep 01 2011, after Maple *)

The number of 321-patterns of a given permutation p of [n] is given by Sum(L[i]R[i],i=1..n), where L (R) is the left (right) inversion vector of p. L and R are related by R[i]+i=p[i]+L[i] (the given Maple program makes use of this approach). References contain formulas and generating functions for the first few columns (some are only conjectured).

A342840 Irregular triangle: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 4213. 0 <= k <= A342646(n).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 10, 6, 1, 512, 77, 69, 30, 21, 5, 6, 2740, 548, 598, 330, 335, 123, 174, 58, 58, 37, 26, 3, 9, 1, 15485, 3799, 4686, 2970, 3411, 1676, 2338, 1040, 1317, 878, 777, 363, 608, 230, 252, 165, 133, 30, 93, 26, 31, 4, 1, 3, 4, 91245, 26165, 35148, 24550, 30182, 17185, 24685, 12976, 16867, 12248, 12360, 7203, 11086, 5692, 6391, 5194, 5006, 2751, 3917, 2019, 2482, 1622, 1371, 812, 1233, 490, 495, 416, 360, 157, 282, 54, 78, 41, 29, 22, 49, 7, 4, 0, 6

Offset: 0

Peter Kagey, Mar 24 2021

The sequence is the same for the patterns 1342, 2431, and 3124.
The sequence appears to be the same for the patterns 1423, 2314, 3241, and 4132.
First column is given by A022558. Row sums given by n!.

			Triangle begins:
n\k |    0    1    2    3    4    5    6   7   8   9  10 11 12 13
----+-------------------------------------------------------------
  0 |    1;
  1 |    1;
  2 |    2;
  3 |    6;
  4 |   23,   1;
  5 |  103,  10,   6,   1;
  6 |  512,  77,  69,  30,  21,   5,   6;
  7 | 2740, 548, 598, 330, 335, 123, 174, 58, 58, 37, 26, 3, 9, 1;

Peter Kagey, Rows n = 0..13, flattened, based on Anders Kaseorg's Rust program at the Code Golf Stack Exchange link.
FindStat, St000750: The number of occurrences of the pattern 4213 in a permutation.
Anders Kaseorg, Answer: Patterns in Permutations, Code Golf Stack Exchange.
Rob Pratt, Greatest number of occurrences of the pattern 4213 in a permutation, Mathematics Stack Exchange.
Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A022558, A342646.

Cf. A263771 (analogous for 312).

Join@@Array[Table[Length@Select[Permutations@Range@#,Length@Select[Subsets[#,{4}],Ordering@Ordering@#=={4,2,1,3}&]==k&],{k,0,Binomial[n+1,4]}]//.{a__,0}:>{a}&,8,0] (* Giorgos Kalogeropoulos, Mar 25 2021 *)

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

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 9, 8, 512, 62, 82, 34, 28, 2, 2740, 402, 612, 384, 466, 94, 232, 42, 60, 8, 15485, 2593, 4187, 3036, 4356, 1746, 3132, 1064, 1918, 909, 654, 333, 612, 144, 104, 22, 24, 1, 91245, 16921, 28065, 21638, 33274, 17598, 31180, 12942, 24000, 14290, 15434, 7770, 15692, 5965, 6896, 3947, 5660, 2226, 3674, 1314, 1512, 516, 508, 204, 332, 37, 40

Offset: 0

Peter Kagey, Mar 26 2021

Equivalently the table for the pattern 3142.

First column is A022558.

			Triangle begins:
  n\k|       0       1        2        3        4        5        6
  ---+------------------------------------------------------------------
   0 |       1;
   1 |       1;
   2 |       2;
   3 |       6;
   4 |      23,      1;
   5 |     103,      9,       8;
   6 |     512,     62,      82,      34,      28,       2;
   7 |    2740,    402,     612,     384,     466,      94,     232, ...
   8 |   15485,   2593,    4187,    3036,    4356,    1746,    3132, ...
   9 |   91245,  16921,   28065,   21638,   33274,   17598,   31180, ...
  10 |  555662, 112196,  188514,  149946,  237128,  140954,  257686, ...
  11 | 3475090, 755920, 1278590, 1036826, 1658064, 1041598, 1933438, ...

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. A022558, A342854.

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

A001810 a(n) = n!n(n-1)*(n-2)/36.

Original entry on oeis.org

0, 0, 0, 1, 16, 200, 2400, 29400, 376320, 5080320, 72576000, 1097712000, 17563392000, 296821324800, 5288816332800, 99165306240000, 1952793722880000, 40311241850880000, 870722823979008000, 19645683716026368000, 462251381553561600000, 11325158848062259200000

Offset: 0

N. J. A. Sloane

nonn

a(n) is the total number of 3-2-1 patterns in all permutations on [n]. This is because there are n! permutations, binomial(n,3) triples in each one and the probability that a given triple of entries in a random permutation form a 3-2-1 pattern (or any other specified pattern of length 3) is 1/6. - David Callan, Oct 26 2006

Old name was "Coefficients of Laguerre polynomials".

			G.f. = x^3 + 16*x^4 + 200*x^5 + 2400*x^6 + 29400*x^7 + 376320*x^8 + ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 799.
Cornelius Lanczos, Applied Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 519.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..100
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Cornelius Lanczos, Applied Analysis. (Annotated scans of selected pages)
Index entries for sequences related to Laguerre polynomials.

Cf. A053495, A263771.

Cf. A001113, A001620, A091725, A099285.

[Factorial(n)*n*(n-1)*(n-2)/36: n in [0..20]]; // G. C. Greubel, May 16 2018

[seq(n!*n*(n-1)*(n-2)/36,n=0..30)];
with(combstruct):ZL:=[st, {st=Prod(left, right), left=Set(U, card=r+1), right=Set(U, card=1)}, labeled]: subs(r=2, stack): seq(count(subs(r=2, ZL), size=m), m=0..20) ; # Zerinvary Lajos, Feb 07 2008

Table[n! n*(n-1)*(n-2)/36, {n, 0, 20}] (* T. D. Noe, Aug 10 2012 *)

for(n=0,20, print1(n!*n*(n-1)*(n-2)/36, ", ")) \\ G. C. Greubel, May 16 2018

[factorial(m) * binomial(m, 3) / 6 for m in range(22)]  # Zerinvary Lajos, Jul 05 2008

a(n) = -A021009(n, 3), n >= 0. a(n) = ((n!/3!)^2)/(n-3)!, n >= 3.
E.g.f.: x^3/(3!*(1-x)^4).
If we define f(n,i,x) = Sum_{k=i..n} Sum_{j=i..k} binomial(k,j) * Stirling1(n,k) * Stirling2(j,i) * x^(k-j) then a(n) = (-1)^(n-1) * f(n,3,-4), (n >= 3). - Milan Janjic, Mar 01 2009
a(n) = Sum_{k>0} k * A263771(n,k). - Alois P. Heinz, Oct 27 2015
From Amiram Eldar, May 02 2022: (Start)
Sum_{n>=3} 1/a(n) = 9*(2*e + gamma - Ei(1) - 4), where e = A001113, gamma = A001620, and Ei(1) = A091725.
Sum_{n>=3} (-1)^(n+1)/a(n) = 63*(gamma - Ei(-1)) - 36*(1/e + 1), where Ei(-1) = -A099285. (End)

Edited by N. J. A. Sloane, Apr 12 2014

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

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 10, 6, 1, 513, 75, 74, 26, 17, 9, 6, 2762, 522, 645, 321, 290, 130, 166, 47, 54, 48, 41, 4, 8, 2, 15793, 3579, 5023, 3058, 3232, 1527, 2228, 874, 1159, 893, 875, 340, 503, 281, 269, 207, 156, 112, 123, 21, 54, 2, 0, 6, 5

Offset: 0

Peter Kagey, Mar 26 2021

Equivalently the table for the pattern 4231.

First column is A061552.

			Triangle begins:
  n\k|       0        1        2        3        4        5        6
  ---+-------------------------------------------------------------------
   0 |       1;
   1 |       1;
   2 |       2;
   3 |       6;
   4 |      23,       1;
   5 |     103,      10,       6,       1;
   6 |     513,      75,      74,      26,      17,       9,       6;
   7 |    2762,     522,     645,     321,     290,     130,     166, ...
   8 |   15793,    3579,    5023,    3058,    3232,    1527,    2228, ...
   9 |   94776,   24670,   37549,   26174,   30409,   15966,   23762, ...
  10 |  591950,  172198,  277089,  213122,  264667,  154452,  228665, ...
  11 | 3824112, 1219974, 2043416, 1693787, 2213548, 1420513, 2086877, ...

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

Cf. A061552, A342853.

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

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).

cp's OEIS Frontend

A002054 Binomial coefficient C(2n+1, n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A138159 Triangle read by rows: T(n,k) is the number of permutations of [n] having k occurrences of the pattern 321 (n>=1, 0<=k<=n(n-1)(n-2)/6).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A342840 Irregular triangle: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 4213. 0 <= k <= A342646(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A001810 a(n) = n!*n*(n-1)*(n-2)/36.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A001810 a(n) = n!n(n-1)*(n-2)/36.