A005118 -id:A005118 - cp's OEIS frontend

A006245 Number of primitive sorting networks on n elements; also number of rhombic tilings of a 2n-gon.

1, 1, 2, 8, 62, 908, 24698, 1232944, 112018190, 18410581880, 5449192389984, 2894710651370536, 2752596959306389652, 4675651520558571537540, 14163808995580022218786390, 76413073725772593230461936736

Offset: 1

N. J. A. Sloane

Also the number of commutation classes of reduced words for the longest element of a Weyl group of type A_{n-1} (see Armstrong reference).
Also the number of signotopes of rank 3, i.e., mappings X:{{1..n} choose 3}->{+,-} such that for any four indices a < b < c < d, the sequence X(a,b,c), X(a,b,d), X(a,c,d), X(b,c,d) changes its sign at most once (see Felsner-Weil and Balko-Fulek-Kynčl reference). - Manfred Scheucher, Oct 20 2019
There is a relation to non-degenerate oriented matroids of rank 3 on n elements (see Folkman-Lawrence reference). - Manfred Scheucher, Feb 09 2022, based on comment by Matthew J. Samuel, Jan 19 2013
Also the number of tilings of the 2-dimensional zonotope constructed from D vectors. The zonotope Z(D,d) is the projection of the D-dimensional hypercube onto the d-dimensional space and the tiles are the projections of the d-dimensional faces of the hypercube. Here d=2 and D varies.
Also the number of simple arrangements of n pseudolines in the Euclidean plane. - Manfred Scheucher, Jun 22 2023

			This is a wiring diagram, one sample of the 62 objects that are counted for n=5:
  1-1-1-1 4-4 5-5
         X   X
  2 3-3 4 1 5 4-4
   X   X   X
  3 2 4 3 5 1 3-3
     X   X   X
  4-4 2 5 3-3 1 2
       X       X
  5-5-5 2-2-2-2 1
Each X denotes a comparator that exchanges the two incoming strands from the left. The whole network has n*(n-1)/2 such comparators and exchanges the order 12345 at the left edge into the reverse order 54321 at the right edge. It is also a pseudoline arrangement consisting of n x-monotone curves (from left to right), which pairwise cross exactly once.

Shin-ichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 1-6.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. Armstrong, The sorting order on a Coxeter group, Journal of Combinatorial Theory 116 (2009), no. 8, 1285-1305.
M. Balko, R. Fulek, and J. Kynčl, Crossing Numbers and Combinatorial Characterization of Monotone Drawings of K_n, Discrete & Computational Geometry, Volume 53, Issue 1, 2015, Pages 107-143.
Helena Bergold, Stefan Felsner, and Manfred Scheucher, Extendability of higher dimensional signotopes, Proc. 38th Eur. Wksp. Comp. Geom. (EuroCG), 2022. See also arXiv:2303.04079 [math.CO], 2023.
Herman Chau, On Enumerating Higher Bruhat Orders Through Deletion and Contraction, arXiv:2412.10532 [math.CO], 2024. See p. 2.
Yunhyung Cho, Jang Soo Kim, and Eunjeong Lee, Enumerate of Gelfand-Cetlin type reduced words, arXiv:2009.06906 [math.CO], 2020. Mentions this sequence.
Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner, and Manfred Scheucher, An Improved Lower Bound on the Number of Pseudoline Arrangements, arXiv:2402.13107 [math.CO], 2024. See p. 2.
H. Denoncourt, D. C. Ernst, and D. Story, On the number of commutation classes of the longest element in the symmetric group, arXiv:1602.08328 [math.HO], 2016.
Adrian Dumitrescu and Ritankar Mandal, New Lower Bounds for the Number of Pseudoline Arrangements, arXiv:1809.03619 [math.CO], 2018.
Stefan Felsner, On the number of arrangements of pseudolines, Proceedings of the twelfth annual symposium on Computational geometry. ACM, 1996. Also Discrete and Computational Geometry, 18 (1997),257-267. Gives a(10).
Stefan Felsner and Jacob E. Goodman, Pseudoline Arrangements, Chapter 5 of Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [Specific reference for this sequence] - _N. J. A. Sloane_, Nov 14 2023
S. Felsner and P. Valtr, Coding and Counting Arrangements of Pseudolines, Discrete and Computational Geometry, 46(3) (2011), 405-416.
S. Felsner and H. Weil, Sweeps, arrangements and signotopes, Discrete Applied Mathematics Volume 109, Issues 1-2, 2001, Pages 67-94.
J. Folkman and J. Lawrence, Oriented matroids, Journal of Combinatorial Theory, Series B 25 (1978), no. 2, 199-236.
Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [General reference for 2017 edition of the Handbook] - _N. J. A. Sloane_, Nov 14 2023
M. J. Hay, J. Schiff, and N. J. Fisch, Available free energy under local phase space diffusion, arXiv preprint arXiv:1604.08573 [math-ph], 2016, see Footnote 27.
J. Kawahara, T. Saitoh, R. Yoshinaka, and S. Minato, Counting Primitive Sorting Networks by PiDDs, Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-11-54, Oct. 2011.
D. E. Knuth, Axioms and Hulls, Lect. Notes Comp. Sci., Vol. 606 (1992) p. 35. [From _R. J. Mathar_, Apr 02 2009]
Ricardo Mamede, The commutation classes of a permutation, 14th Comb. Days, Univ. Coimbra (Portugal, 2024). See slide 10.
S. Minato, Techniques of BDD/ZDD: Brief History and Recent Activity, IEICE Transactions on Information and Systems, Vol. E96-D, No. 7, pp.1419-1429.
Yan Alves Radtke, Stefan Felsner, Johannes Obenaus, Sandro Roch, Manfred Scheucher, and Birgit Vogtenhuber, Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles, arXiv:2310.19711 [math.CO], 2023. See p. 41.
Matthew J. Samuel, Word posets, complexity, and Coxeter groups, arXiv:1101.4655 [math.CO], 2011.
M. J. Samuel, Word posets, with applications to Coxeter groups, arXiv preprint arXiv:1108.3638 [cs.DM], 2011.
Manfred Scheucher, C++ program for enumeration
B. E. Tenner, Tiling-based models of perimeter and area, arXiv:1811.00082 [math.CO], 2018.
M. Widom, N. Destainville, R. Mosseri, and F. Bailly, Two-dimensional random tilings of large codimension, Proceedings of the 7th International Conference on Quasicrystals (ICQ7, Stuttgart), arXiv:cond-mat/9912275 [cond-mat.stat-mech], 1999.
M. Widom, N. Destainville, R. Mosseri, and F. Bailly, Two-dimensional random tilings of large codimension, Materials Science and Engineering: A, Volumes 294-296, 15 December 2000, Pages 409-412.
Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno, and Kunihiro Wasa, Ladder-Lottery Realization, 30th Canadian Conference on Computational Geometry (CCCG 2018) Winnipeg.
K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara, and K. Nakada, Efficient enumeration of all ladder lotteries and its application, Theoretical Computer Science, Vol. 411, pp. 1714-1722, 2010.
G. M. Ziegler, Higher Bruhat Orders and Cyclic Hyperplane Arrangements, Topology, Volume 32, 1993.
Index entries for sequences related to sorting.

Cf. A006246. See A005118 for primitive sorting networks with exactly one comparator ("X") per column. See A060596-A060601 for higher dimensions. Cf. A006247.

# classes: Wrapper for computing number of commutation classes;
#   pass a permutation as a list
# Returns number of commutation classes of reduced words
# Longest element is of the form [n, n-1, ..., 1] (see Comments)
classes:=proc(perm) option remember:
    RETURN(classesRecurse(Array(perm), 0, 1)):
end:
#classesRecurse: Recursive procedure for computing number of commutation classes
classesRecurse:=proc(perm, spot, negs) local swaps, i, sums, c, doneany:
    sums:=0:
    doneany:=0:
    for i from spot to ArrayNumElems(perm)-2 do
        if perm[i+1]>perm[i+2] then
            swaps:=perm[i+1]:
            perm[i+1]:=perm[i+2]:
            perm[i+2]:=swaps:
            c:=classes(convert(perm, `list`)):
            sums:=sums+negs*c+classesRecurse(perm, i+2, -negs):
            swaps:=perm[i+1]:
            perm[i+1]:=perm[i+2]:
            perm[i+2]:=swaps:
            doneany:=1:
        end:
    end:
    if spot=0 and doneany=0 then RETURN(1):
    else RETURN(sums):
    end:
end:
seq(classes([seq(n+1-i, i = 1 .. n)]), n = 1 .. 9)
# Matthew J. Samuel, Jan 23 2011, Jan 26 2011

classes[perm_List] := classes[perm] = classesRecurse[perm, 0, 1];
classesRecurse[perm_List, spot_, negs_] := Module[{swaps, i, Sums, c, doneany, prm = perm}, Sums = 0; doneany = 0; For[i = spot, i <= Length[prm]-2, i++, If[prm[[i+1]] > prm[[i+2]], swaps = prm[[i+1]]; prm[[i+1]] = prm[[i+2]]; prm[[i+2]] = swaps; c = classes[prm]; Sums = Sums + negs*c + classesRecurse[prm, i+2, -negs]; swaps = prm[[i+1]]; prm[[i+1]] = prm[[i+2]]; prm[[i+2]] = swaps; doneany = 1]]; If[spot == 0 && doneany == 0, Return[1], Return[Sums]]];
a[n_] := a[n] = classes[Range[n] // Reverse];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 9}] (* Jean-François Alcover, May 09 2017, translated from Maple *)

Felsner and Valtr show that 0.1887 <= log_2(a(n))/n^2 <= 0.6571 for sufficiently large n. - Jeremy Tan, Nov 20 2017

Dumitrescu and Mandal improved the lower bound to 0.2083 <= log_2(a(n))/n^2 for sufficiently large n. - Manfred Scheucher, Sep 13 2021

More terms from Sebastien Veigneau (sv(AT)univ-mlv.fr), Jan 15 1997
a(10) confirmed by Katsuhisa Yamanaka(yamanaka(AT)hol.is.uec.ac.jp), May 06 2009. This value was also confirmed by Takashi Horiyama of Saitama Univ.
a(11) from Katsuhisa Yamanaka(yamanaka(AT)hol.is.uec.ac.jp), May 06 2009
Reference with formula that the Maple program implements added and a(11) verified by Matthew J. Samuel, Jan 25 2011
Removed invalid comment concerning the denominators of the indicated polynomials; added a(12). - Matthew J. Samuel, Jan 30 2011
a(13) from Toshiki Saitoh, Oct 17 2011
a(14) and a(15) from Yuma Tanaka, Aug 20 2013
a(16) by Günter Rote, Dec 01 2021

A057863 a(n) = Product_{k=1..n} (2k-1)!!.

Original entry on oeis.org

1, 1, 3, 45, 4725, 4465125, 46414974375, 6272287562165625, 12714083695698776015625, 438120013555654794702228515625, 286849911214281324754704976473779296875, 3943988517696329309474874414036059896739501953125

Offset: 0

Eric W. Weisstein

a(n) is the coefficient of the closed form for BarnesG[(2n-1)/2].
a(n) is the hook product corresponding to the partition (n,n-1,...,2,1). a(n)=(n(n+1)/2)!/A005118(n+1). - Emeric Deutsch, May 21 2004
Hankel transform of A185998. - Paul Barry, Feb 08 2011
The Burchnall-Chaundy polynomials P_n(z) have leading term z^(n^2+n)/a(n). - Michael Somos, Jan 18 2023

			G.f. = 1 + x + 3*x^2 + 45*x^3 + 4725*x^4 + 4465125*x^5 + ... - _Michael Somos_, Jan 18 2023

Alois P. Heinz, Table of n, a(n) for n = 0..35
Alejandro H. Morales, Igor Pak, and Greta Panova, Hook formulas for skew shapes III. Multivariate and product formulas, arXiv:1707.00931 [math.CO], 2017.
A. P. Veselov and R. Wilcox, Burchnall-Chaundy polynomials and the Laurent Phenomenon, arXiv:1407.7394 [math-ph], 2014.
Eric Weisstein's World of Mathematics, Barnes G-Function

Cf. A000178, A005118, A074962, A086205, A089626.

a:= n-> mul((2*k+1)^(n-k), k=0..n):
seq(a(n), n=0..15);  # Alois P. Heinz, Nov 28 2012

a[n_] := Product[2^i Gamma[1/2+i]/Sqrt[Pi], {i, n}]
Table[Product[(2*k+1)^(n-k),{k,0,n}],{n,0,10}] (* Vaclav Kotesovec, Nov 13 2014 *)
Table[Product[(2k-1)!!,{k,1,n}],{n,0,10}] (* Vaclav Kotesovec, Nov 13 2014 *)
Table[2^(n(n+1)/2-1/24) Glaisher^(3/2) Pi^(-n/2-1/4) E^(-1/8) BarnesG[n+3/2], {n, 0, 10}] (* Vladimir Reshetnikov, Nov 06 2015 *)
Table[Sqrt[BarnesG[2*n + 2]] / (2^(n^2/2) * BarnesG[n+1] * Sqrt[Gamma[n+1]]), {n, 0, 12}] (* Vaclav Kotesovec, Apr 08 2021 *)

PARI
```
a(n)=prod(k=0,n-1,prod(i=0,k,2*i+1))
```

a(n) = Product_{k=0..n} (2*k+1)^(n-k).
a(n) ~ A^(1/2) * 2^(n^2/2+n+5/24) * n^(n^2/2+n/2+1/24) / exp(3*n^2/4+n/2+1/24), where A = 1.2824271291... is the Glaisher-Kinkelin constant (see A074962). - Vaclav Kotesovec, Nov 13 2014
a(n) = 2^(n*(n+1)/2-1/24) * A^(3/2) * Pi^(-n/2-1/4) * exp(-1/8) * G(n+3/2), where A is the Glaisher-Kinkelin constant, G is the Barnes G-function. - Vladimir Reshetnikov, Nov 06 2015
a(n) = sqrt(G(2*n+2)) / (2^(n^2/2) * G(n+1) * sqrt(Gamma(n+1))), where G is the Barnes G-function. - Vaclav Kotesovec, Apr 08 2021
From Michael Somos, Jan 18 2023: (Start)
a(n) = (-1)^floor((n+1)/2)*a(-1-n) for all n in Z.
a(n+1)*a(n-1) = (2*n+1)*a(n)^2 for all n in Z.
(4*n + 8)*a(n+1)^2*a(n+2)^2 = a(n)*a(n+2)^3 + a(n+1)^3*a(n+3) for all n in Z.(End)
a(n) = (1/2^(n*(n-1)/2)) * A086205(n). - Peter Bala, Feb 20 2023

Simpler description from Benoit Cloitre, May 03 2003

Definition and programs corrected by Vaclav Kotesovec, Nov 13 2014

A003121 Strict sense ballot numbers: n candidates, k-th candidate gets k votes.

Original entry on oeis.org

1, 1, 1, 2, 12, 286, 33592, 23178480, 108995910720, 3973186258569120, 1257987096462161167200, 3830793890438041335187545600, 123051391839834932169117010215648000, 45367448380314462649742951646437285434233600, 207515126854334868747300581954534054343817468395494400

Offset: 0

Colin Mallows

Also, number of even minus number of odd extensions of truncated (n-1) X n grid diagram.
Also, a(n) is the degree of the spinor variety, the complex projective variety SO(2n+1)/U(n). See Hiller's paper. - Burt Totaro (b.totaro(AT)dpmms.cam.ac.uk), Oct 29 2002
Also, number of ways of placing 1, ..., n*(n+1)/2 in a triangular array such that both rows and columns are increasing, i.e., the number of shifted standard Young tableaux of shape (n, n-1, ..., 1).
E.g., a(3) = 2 as we can write:
  1            1
  2 3    or    2 4
  4 5 6        3 5 6
(or transpose these to have shifted tableaux). - Jon Perry, Jun 13 2003, edited by Joel B. Lewis, Aug 27 2011
Also, the number of symbolic sequences on the n symbols 0,1, ..., n-1. A symbolic sequence is a sequence that has n occurrences of 0, n-1 occurrences of 1, ..., one occurrence of n-1 and satisfies the condition that between any two consecutive occurrences of the symbol i it has exactly one occurrence of the symbol i+1. For example, the two symbolic sequences on 3 symbols are 012010 and 010210. The Shapiro-Shapiro paper shows how such sequences arise in the study of the arrangement of the real roots of a polynomial and its derivatives. There is a natural bijection between symbolic sequences and the triangular arrays described above. - Peter Bala, Jul 18 2007
a(n) also appears to be the number of chains from w_0 down to 1 in a certain suborder of the strong Bruhat order on S_n: we let v cover (ij)*v only if i,j straddle the leftmost descent in v. For n=3 and drawing that descent with a |, this order is 3|21 > 23|1 > 13|2 & 2|13 > 123, with two maximal chains. - Allen Knutson (allenk(AT)math.cornell.edu), Oct 13 2008
Number of ways to arrange the numbers 1,2,...,n(n+1)/2 in a triangle so that the rows interlace; e.g., one of the 12 triangles counted by a(4) is
        6
      4   8
    2   5   9
  1   3   7   10
- Clark Kimberling, Mar 25 2012
Also, the number of maps from n X n pipe dreams (rc-graphs) to words of adjacent transpositions in S_n that send a crossing of pipes x and y in square (i,j) to the transposition (i+j-1,i+j) swapping x and y. Taking the pictorial image of a permutation as a wiring diagram, these are maps from pipe dreams to wiring diagrams that send crossings of pipes to crossings of similarly labeled wires. - Cameron Marcott, Nov 26 2012
Number of words of length T(n)=n*(n+1)/2 with n 1's, (n-1) 2's, ..., and 1 n such that counting the numbers from left to right we always have |1| > |2| > |3| > ... > |n|. The 12 words for n=4 are 1111222334, 1111223234, 1112122334, 1112123234, 1112212334, 1112213234, 1112231234, 1121122334, 1121123234, 1121212334, 1121213234 and 1121231234. - Jon Perry, Jan 27 2013
Regarding the comment dated Mar 25 2012, it is assumed that each row is in increasing order, as in the example dated Jul 12 2012. How many row-interlacing triangles are there without that restriction? - Clark Kimberling, Dec 02 2014
Number of maximal chains of length binomial(n+1,2) in the Tamari lattice T_{n+1}. For n=2 there is 1 maximal chain of length 3 in the Tamari lattice T_3. - Alois P. Heinz, Dec 04 2015
The normalized volume of the subpolytope of the Birkhoff polytope obtained by taking the convex hull of all n X n permutation matrices corresponding to permutations that avoid the patterns 132 and 312. - Robert Davis, Dec 04 2016
From Emily Gunawan, Feb 26 2022: (Start)
The number of maximal chains in the lattice of permutations which avoid both the patterns 132 and 312, as a sublattice of the weak order on the symmetric group. For example, there are exactly 12 maximal chains in the sublattice for the weak order on the symmetric group on 5 elements.
The number of words in the commutation class of the c-sorting word of the longest permutation w_0 in the symmetric group for the Coxeter element c = s_1 s_2 s_3 s_4 s_5 ... . For example, the c-sorting word of w_0 for s_1 s_2 s_3 s_4 is the reduced word s_1 s_2 s_3 s_4 | s_1 s_2 s_3 | s_1 s_2 | s_1, and there are exactly 12 words in its commutation class.
The number of maximal chains in the lattice of c-singletons for the symmetric group, for the Coxeter element c = s_1 s_2 s_3 s_4 s_5 ... . For example, there are exactly 12 maximal chains in the lattice of c-singletons for c = s_1 s_2 s_3 s_4. (End)

			From _R. H. Hardin_, Jul 06 2012: (Start)
The a(4) = 12 ways to fill a triangle with the numbers 0 through 9:
.
     5         6         6         5
    3 7       3 7       2 7       2 7
   1 4 8     1 4 8     1 4 8     1 4 8
  0 2 6 9   0 2 5 9   0 3 5 9   0 3 6 9
.
     5         3         3         4
    3 6       2 6       2 7       3 7
   1 4 8     1 5 8     1 5 8     1 5 8
  0 2 7 9   0 4 7 9   0 4 6 9   0 2 6 9
.
     4         4         5         4
    2 6       2 7       2 6       3 6
   1 5 8     1 5 8     1 4 8     1 5 8
  0 3 7 9   0 3 6 9   0 3 7 9   0 2 7 9
.
(End)

G. Kreweras, Sur un problème de scrutin à plus de deux candidats, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..30
E. Aas and S. Linusson, Continuous multiline queues and TASEP, 2014; also arxiv version, arXiv:1501.04417 [math.CO], 2015-2017.
Joerg Arndt, The a(5)=286 Young tableaux of shape [1,2,3,4,5].
D. E. Barton and C. L. Mallows, Some aspects of the random sequence, Ann. Math. Statist. 36 (1965) 236-260.
Andrew Beveridge, Ian Calaway, and Kristin Heysse, de Finetti Lattices and Magog Triangles, arXiv:1912.12319 [math.CO], 2019.
R. Davis and B. Sagan, Pattern-Avoiding Polytopes, arXiv:1609.01782 [math.CO], 2016.
William T. Dugan, Maura Hegarty, Alejandro H. Morales, and Annie Raymond, Generalized Pitman-Stanley flow polytopes, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #80.
William T. Dugan, Maura Hegarty, Alejandro H. Morales, and Annie Raymond, Generalized Pitman-Stanley polytope: vertices and faces, arXiv:2307.09925 [math.CO], 2023.
S. Fishel and L. Nelson, Chains of maximum length in the Tamari lattice, Proc. Amer. Math. Soc. 142 (2014), 3343-3353.
Joël Gay, Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups, Doctoral Thesis, Discrete Mathematics [cs.DM], Université Paris-Saclay, 2018.
H. Hiller, Combinatorics and intersection of Schubert varieties, Comment. Math. Helv. 57 (1982), 41-59.
C. Hohlweg, C. Lange, and H. Thomas, Permutahedra and generalized associahedra, arXiv:0709.4241 [math.CO], 2007-2008; Adv. Math. 226 (2011), no. 1, 608-640.
G. Kreweras, Sur un problème de scrutin à plus de deux candidats, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87. [Annotated scanned copy]
Joshua Maglione and Christopher Voll, Hall-Littlewood polynomials, affine Schubert series, and lattice enumeration, arXiv:2410.08075 [math.CO], 2024. See pp. 30, 39.
Colin Mallows, Letter to N. J. A. Sloane, date unknown.
Svante Linusson and Samu Potka, New properties of the Edelman-Greene bijection, arXiv:1804.10034 [math.CO], 2018.
N. Reading, Cambrian lattices, arXiv:math/0402086 [math.CO], 2004-2005; Adv. Math. 205 (2006), no. 2, 313-353.
F. Ruskey, Generating linear extensions of posets by transpositions, J. Combin. Theory, B 54 (1992), 77-101.
B. Shapiro and M. Shapiro, A few riddles behind Rolle's theorem, arXiv:math/0302215 [math.CA], 2003-2005; Amer. Math. Monthly, 119 (2012), 787-795.
George Story, Counting Maximal Chains in Weighted Voting Posets, Rose-Hulman Undergraduate Mathematics Journal, Vol. 14, No. 1, 2013.
R. M. Thrall, A combinatorial problem, Michigan Math. J. 1, (1952), 81-88.
Dennis White, Sign-balanced posets, Journal of Combinatorial Theory, Series A, Volume 95, Issue 1, July 2001, Pages 1-38.
Wikipedia, Tamari lattice

Cf. A005118, A018241, A007724, A004065, A131811, A064049, A064050.
A213457 is also closely related.
Cf. A000108, A027686, A282698.

f:= n-> ((n*n+n)/2)!*mul((i-1)!/(2*i-1)!, i=1..n); seq(f(n), n=0..20);

f[n_] := (n (n + 1)/2)! Product[(i - 1)!/(2 i - 1)!, {i, n}]; Array[f, 14, 0] (* Robert G. Wilson v, May 14 2013 *)

a(n)=((n*n+n)/2)!*prod(i=1,n,(i-1)!/(2*i-1)!)

a(n) = binomial(n+1, 2)!*(1!*2!*...*(n-1)!)/(1!*3!*...*(2n-1)!).

a(n) ~ sqrt(Pi) * exp(n^2/4 + n/2 + 7/24) * n^(n^2/2 + n/2 + 23/24) / (A^(1/2) * 2^(3*n^2/2 + n + 5/24)), where A = 1.2824271291... is the Glaisher-Kinkelin constant (see A074962). - Vaclav Kotesovec, Nov 13 2014

More terms from Michael Somos
Additional references from Frank Ruskey
Formula corrected by Eric Rowland, Jun 18 2010

A219311 Number T(n,k) of standard Young tableaux for partitions of n into exactly k distinct parts; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 3, 0, 1, 9, 0, 1, 14, 16, 0, 1, 34, 35, 0, 1, 55, 134, 0, 1, 125, 435, 0, 1, 209, 1213, 768, 0, 1, 461, 3454, 2310, 0, 1, 791, 10484, 11407, 0, 1, 1715, 28249, 44187, 0, 1, 3002, 80302, 200044, 0, 1, 6434, 231895, 680160, 292864

Offset: 0

Alois P. Heinz, Nov 17 2012

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=A003056(n). T(n,k) = 0 for k>A003056(n).

			A(4,2) = 3:
  +---------+  +---------+  +---------+
  | 1  2  3 |  | 1  2  4 |  | 1  3  4 |
  | 4 .-----+  | 3 .-----+  | 2 .-----+
  +---+        +---+        +---+
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1;
  0,  1,    2;
  0,  1,    3;
  0,  1,    9;
  0,  1,   14,    16;
  0,  1,   34,    35;
  0,  1,   55,   134;
  0,  1,  125,   435;
  0,  1,  209,  1213,   768;
  0,  1,  461,  3454,  2310;
  0,  1,  791, 10484, 11407;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
Wikipedia, Young tableau

Columns k=0-10 give: A000007, A000012 (for n>0), A047171(n) = A037952(n)-1, A219316, A219317, A219318, A219319, A219320, A219321, A219322, A219323.
Row sums give: A218293.
Row lengths are 1 + A003056(n).
T(A000217(k),k) = A005118(k+1).
Cf. A219272, A219274.

h:= proc(l) local n; n:=nops(l); add(i, i=l)!/mul(mul(1+l[i]-j+
      add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, k, l) `if`(n=0, h(l), `if`(n>k*(i-(k-1)/2), 0,
      g(n, i-1, min(k, i-1), l)+`if`(i>n, 0, g(n-i, i-1, k-1, [l[], i]))))
    end:
A:= proc(n, k) option remember; `if`(k<0, 0, g(n, n, k, [])) end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..20);

h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]!/Product[Product[1+l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}] ];
g[n_, i_, k_, l_] := If[n == 0, h[l], If[n > k*(i-(k-1)/2), 0, g[n, i-1, Min[k, i-1], l] + If[i > n, 0, g[n-i, i-1, k-1, Append[l, i]]]]];
a[n_, k_] := a[n, k] = If[k < 0, 0, g[n, n, k, {}]];
t[n_, k_] := a[n, k] - a[n, k-1];
Table[Table[t[n, k], {k, 0, Floor[(Sqrt[1+8*n]-1)/2]}], {n, 0, 20}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

A219274 Number T(n,k) of standard Young tableaux for partitions of n into distinct parts with largest part k; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 5, 16, 1, 4, 9, 49, 70, 168, 768, 1, 5, 14, 92, 204, 738, 3300, 7887, 15015, 48048, 292864, 1, 6, 20, 153, 405, 1815, 9460, 28743, 101673, 333905, 1946516, 4934930, 14454726, 34918884, 141892608, 1100742656, 1, 7, 27, 235, 715, 3630, 21307

Offset: 0

Alois P. Heinz, Nov 17 2012

T(n,k) is defined for n,k >= 0. T(n,k) = 0 iff n k*(k+1)/2 = A000217(k). The triangle contains only the nonzero terms.

			T(3,2) = 2:
+------+  +------+
| 1  2 |  | 1  3 |
| 3 .--+  | 2 .--+
+---+     +---+
Triangle T(n,k) begins:
1;
.  1;
.     1;
.     2,  1;
.         3,   1;
.         5,   4,   1;
.        16,   9,   5,   1;
.             49,  14,   6,   1;
.             70,  92,  20,   7,  1;
.            168, 204, 153,  27,  8, 1;
.            768, 738, 405, 235, 35, 9, 1;

Alois P. Heinz, Columns k = 0..22, flattened
Wikipedia, Young tableau

Column heights are A000124(k-1) for k>0.
Column sums give: A219275.
Row sums give: A218293.
Diagonal and lower diagonals give: A000012, A000027 (for n>1), A000096(n-1) (for n>2).
Leftmost nonzero elements give A219339.
Column of leftmost nonzero element is A002024(n) for n>0.
Triangle read by rows reversed gives: A219356.
T(A000217(n),n) = A005118(n+1).

h:= proc(l) local n; n:=nops(l); add(i, i=l)!/mul(mul(1+l[i]-j+
      add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, l) local s; s:=i*(i+1)/2;
      `if`(n=s, h([l[], seq(i-j, j=0..i-1)]), `if`(n>s, 0,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i-1, [l[], i]))))
    end:
T:= (n, k)-> `if`(k>n, 0, g(n-k, k-1, [k])):
seq(seq(T(n, k), n=k..k*(k+1)/2), k=0..7);

h[l_] := Module[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := Module[{s = i(i + 1)/2}, If[n == s, h[Join[l, Table[i - j, {j, 0, i - 1}]]], If[n > s, 0, g[n, i - 1, l] + If[i > n, 0, g[n - i, i - 1, Append[l, i]]]]]];
T[n_, k_] := If[k > n, 0, g[n - k, k - 1, {k}]];
Table[Table[T[n, k], {n, k, k(k + 1)/2}], {k, 0, 7}] // Flatten (* Jean-François Alcover, Sep 01 2023, after Alois P. Heinz *)

T(n,k) = A219272(n,k) - A219272(n,k-1) for k>0.

A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.

Original entry on oeis.org

1, 2, 4, 24, 816, 239968, 808814912, 38764383658368, 31491961129357837056, 503091371552266970507912704, 179763631086276515267399940231898112, 1609791936564515363272979180683040232936253440

Offset: 0

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Aug 28 2008

nonn

For each n, each vertex in the Hasse diagram of the poset corresponds to a Dyck path of size n. The chain polynomial, C(P,t)=(1 + sum_k(c_k*t^(k+1)), gives the breakdown of this sequence by number of vertices in the chain. The 1 in front of the sum in this equation denotes the empty chain. The coefficient, c_k, gives the number of chains of length k and the exponent, (k+1), indicates the number of vertices in the chain. Here are the chain polynomials corresponding to this sequence:
n=0 1
n=1 1 + t
n=2 1 + 2t + t^2
n=3 1 + 5t + 9t^2 + 7t^3 + 2t^4
n=4 1 + 14t + 70t^2 + 176 t^3+249t^4 + 202t^5 + 88 t^6 + 16 t^7
n=5 1 + 42t + 552t^2 + 3573t^3 + 13609t^4+ 33260 t^5 + 54430t^6 + 60517t^7 + 45248t^8 + 21824t^9 + 6144t^(10) + 768t^(11)
Note that for each n, the coefficient of t is equal to the Catalan number, C_n. It is well-known that the number of Dyck paths in D_n is given by C_n (A000108). The coefficient in front of the largest power of t gives the number of maximal (and also maximum) chains (A005118).

			a(3) = 24 since in D_3 there are 2 chains of length 3 (i.e., on 4 vertices in the Hasse diagram), 7 chains of length 2 (on 3 vertices), 9 chains of length 1 (on 2 vertices), 5 chains of length 0 (on 1 vertex) and the empty chain: 2 + 7 + 9 + 5 + 1 = 24 chains.

R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997.

J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Cf. A143673, A143674, A193629. Chains on one vertex: A000108. Number of maximal chains: A005118.

d:= proc(x, y, l) option remember;
      `if`(x=1, [[l[], y]], [seq(d(x-1, i, [l[], y])[], i=x-1..y)])
    end:
le:= proc(l1, l2) local i;
       for i to nops(l1) do if l1[i]>l2[i] then return false fi od;
       true
     end:
a:= proc(n) option remember; local l, m, g;
      if n=0 then return 1 fi;
      l:= d(n, n, []); m:= nops(l);
      g:= proc(t) option remember;
            1 +add(`if`(le(l[d], l[t]), g(d), 0), d=1..t-1);
          end;
      1+ add(g(h), h=1..m)
    end:
seq(a(n), n=0..7);  # Alois P. Heinz, Jul 26 2011

a(n) = 1 + Sum_{i,j in {1..C(n)}} (2*delta - zeta)^(-1)[i,j] where delta is the identity matrix and the zeta matrix is defined: zeta[a,b] = 1 if a<=b in D_n and 0 otherwise.

a(6)-a(11), from Alois P. Heinz, Jul 26 2011, Aug 01 2011

A219272 Number A(n,k) of standard Young tableaux for partitions of n into distinct parts with largest part <= k; triangle A(n,k), k>=0, 0<=n<=k*(k+1)/2, read by columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 5, 16, 1, 1, 1, 3, 4, 9, 25, 49, 70, 168, 768, 1, 1, 1, 3, 4, 10, 30, 63, 162, 372, 1506, 3300, 7887, 15015, 48048, 292864, 1, 1, 1, 3, 4, 10, 31, 69, 182, 525, 1911, 5115, 17347, 43758, 149721, 626769, 1946516, 4934930

Offset: 0

Alois P. Heinz, Nov 17 2012

A(n,k) is defined for n,k >= 0. A(n,k) = 0 iff n > k*(k+1)/2 = A000217(k). The triangle contains only the nonzero terms. A(n,k) = A(n,n) for k>=n.

			A(3,2) = 2:
+------+  +------+
| 1  2 |  | 1  3 |
| 3 .--+  | 2 .--+
+---+     +---+
A(3,3) = 3:
+------+  +------+  +---------+
| 1  2 |  | 1  3 |  | 1  2  3 |
| 3 .--+  | 2 .--+  +---------+
+---+     +---+
Triangle A(n,k) begins:
1,  1,  1,  1,   1,    1,    1,    1,    1, ...
.   1,  1,  1,   1,    1,    1,    1,    1, ...
.       1,  1,   1,    1,    1,    1,    1, ...
.       2,  3,   3,    3,    3,    3,    3, ...
.           3,   4,    4,    4,    4,    4, ...
.           5,   9,   10,   10,   10,   10, ...
.          16,  25,   30,   31,   31,   31, ...
.               49,   63,   69,   70,   70, ...
.               70,  162,  182,  189,  190, ...

Alois P. Heinz, Columns k = 0..22, flattened
Wikipedia, Young tableau

Column heights are A000124.
Column sums give: A219273.
Diagonal gives: A218293.
Leftmost nonzero elements give A219339.
Column of leftmost nonzero element is A002024(n) for n>0.
T(A000217(n),n) = A005118(n+1).

h:= proc(l) local n; n:=nops(l); add(i, i=l)!/mul(mul(1+l[i]-j+
      add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, l) local s; s:=i*(i+1)/2;
      `if`(n=s, h([l[], seq(i-j, j=0..i-1)]), `if`(n>s, 0,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i-1, [l[], i]))))
    end:
A:= (n, k)-> g(n, k, []):
seq(seq(A(n, k), n=0..k*(k+1)/2), k=0..7);

h[l_] := With[{n=Length[l]}, Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[ l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := g[n, i, l] = With[{s=i*(i+1)/2}, If[n==s, h[Join[l, Table[ i-j, {j, 0, i-1}]]], If[n>s, 0, g[n, i-1, l] + If[i>n, 0, g[n-i, i-1, Append[l, i]]]]]];
A[n_, k_] := g[n, k, {}];
Table[Table[A[n, k], {n, 0, k*(k+1)/2}], {k, 0, 7}] // Flatten (* Jean-François Alcover, Feb 29 2016, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} A219274(n,i).

A219339 Number of standard Young tableaux for partitions of n into distinct parts with largest part floor(sqrt(2*n)+1/2).

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 16, 49, 70, 168, 768, 3300, 7887, 15015, 48048, 292864, 1946516, 4934930, 14454726, 34918884, 141892608, 1100742656, 9732668946, 32773404950, 97848532782, 344699731090, 1020872973120, 5091106775040, 48608795688960, 586393249199550

Offset: 0

Alois P. Heinz, Nov 18 2012

nonn

a(n) is the leftmost nonzero element in row n of A219272, A219274.

Floor(sqrt(2*n)+1/2) = A002024(n) for n>0. There are no partitions of n into distinct parts with a smaller largest part.

			For n=5, we have floor(sqrt(2*n)+1/2) = 3, and a(5) = 5, because there are 5 standard Young tableaux for partitions of 5 into distinct parts with largest part 3:
+---------+  +---------+  +---------+  +---------+  +---------+
| 1  2  3 |  | 1  2  4 |  | 1  2  5 |  | 1  3  4 |  | 1  3  5 |
| 4  5 .--+  | 3  5 .--+  | 3  4 .--+  | 2  5 .--+  | 2  4 .--+
+------+     +------+     +------+     +------+     +------+

Alois P. Heinz, Table of n, a(n) for n = 0..300
Wikipedia, Young tableau

Cf. A005118 (subsequence), A219347.

h:= proc(l) local n; n:=nops(l); add(i, i=l)!/mul(mul(1+l[i]-j+
      add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, l) local s; s:=i*(i+1)/2;
      `if`(n=s, h([l[], seq(i-j, j=0..i-1)]), `if`(n>s, 0,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i-1, [l[], i]))))
    end:
a:= n-> g(n, floor(sqrt(2*n)+1/2), []):
seq(a(n), n=0..30);

h[l_] := (n = Length[l]; Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]); g[n_, i_, l_] := g[n, i, l] = (s = i*(i+1)/2; If[n==s, h[Join[l, Table[i-j, {j, 0, i-1}]] ], If[n>s, 0, g[n, i-1, l]+If[i>n, 0, g[n-i, i-1, Append[l, i]]]]] ); a[n_] := g[n, Floor[Sqrt[2*n]+1/2], {}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 16 2017, translated from Maple *)

a(n) = A219272(n,floor(sqrt(2*n)+1/2)) = A219274(n,floor(sqrt(2*n)+1/2)).

A018241 Number of simple allowable sequences on 1..n.

Original entry on oeis.org

1, 1, 2, 32, 4608, 7028736, 132089118720, 34998332896051200, 147462169661142781132800, 11008782516353752266715850342400, 16061608070479103314001351327405309952000, 500842967990688435516159987675099451681186775040000

Offset: 1

N. J. A. Sloane

J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 102.
G. Kreweras, Sur un problème de scrutin à plus de deux candidats, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87.

Alois P. Heinz, Table of n, a(n) for n = 1..40
G. Kreweras, Sur un problème de scrutin à plus de deux candidats, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87. [Annotated scanned copy]
R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., 5 (1984), 359-372.

Cf. A003121, A005118, A074962.

A018241 := proc(n) local i; (n-2)!*binomial(n,2)!/product( (2*i+1)^(n-i-1), i=0..n-2 ); end;

a[n_] := (n*(n-1)/2)!*(n-2)! / Product[ (2i+1)^(n-i-1), {i, 0, n-2}]; a[1] = 1; Table[ a[n], {n, 1, 11}] (* Jean-François Alcover, Jan 25 2012 *)

a(n) = (n-2)!*C(n,2)! / (1^{n-1} * 3^{n-2} * ... * (2n-3)^1).

a(n) ~ Pi * exp(n^2/4 - 3*n/2 + 7/24) * n^(n^2/2 + n/2 - 13/24) / (A^(1/2) * 2^(n^2 - n/2 - 19/24)), where A = 1.2824271291... is the Glaisher-Kinkelin constant (see A074962). - Vaclav Kotesovec, Nov 13 2014

A193536 Triangle T(n,k), n>=0, 0<=k<=C(n,2), read by rows: T(n,k) = number of k-length saturated chains in the poset of Dyck paths of semilength n ordered by inclusion.

Original entry on oeis.org

1, 1, 2, 1, 5, 5, 4, 2, 14, 21, 30, 38, 40, 32, 16, 42, 84, 168, 322, 578, 952, 1408, 1808, 1920, 1536, 768, 132, 330, 840, 2112, 5168, 12172, 27352, 58126, 115636, 212762, 356352, 532224, 687104, 732160, 585728, 292864, 429, 1287, 3960

Offset: 0

Alois P. Heinz, Jul 29 2011

			Poset of Dyck paths of semilength n=3:
.
.      A       A:/\      B:
.      |        /  \      /\/\
.      B       /    \    /    \
.     / \
.    C   D     C:        D:        E:
.     \ /         /\      /\
.      E       /\/  \    /  \/\    /\/\/\
.
Saturated chains of length k=0: A, B, C, D, E (5); k=1: A-B, B-C, B-D, C-E, D-E (5); k=2: A-B-C, A-B-D, B-C-E, B-D-E (4), k=3: A-B-C-E, A-B-D-E (2) => [5,5,4,2].
Triangle begins:
    1;
    1;
    2,   1;
    5,   5,   4,    2;
   14,  21,  30,   38,   40,    32,    16;
   42,  84, 168,  322,  578,   952,  1408,  1808,   1920,   1536,    768;
  132, 330, 840, 2112, 5168, 12172, 27352, 58126, 115636, 212762, 356352, ...

Alois P. Heinz, Rows n = 0..13, flattened
J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Row sums give: A166860. Columns k=0,1 give: A000108, A002054(n-1). Last elements of rows give: A005118. Row lengths give: A000124(n-1).

d:= proc(x, y, l) option remember;
      `if`(x<=1, [[y, l[]]], [seq(d(x-1, i, [y, l[]])[], i=x-1..y)])
    end:
T:= proc(n) option remember; local g, r, j;
      g:= proc(l) option remember; local r, i;
            r:= [1];
            for i to n-1 do if l[i]>i and (i=1 or l[i-1]x+y, r, [0, g(subsop(i=l[i]-1, l))[]], 0)
            fi od; r
          end;
      r:= [];
      for j in d(n, n, []) do
        r:= zip((x, y)->x+y, r, g(j), 0)
      od; r[]
    end:
seq(T(n), n=0..7);

zip = With[{m = Max[Length[#1], Length[#2]]}, PadRight[#1, m] + PadRight[#2, m]]&; d[x_, y_, l_] := d[x, y, l] = If[x <= 1, {Prepend[l, y]}, Flatten[t = Table [d[x-1, i, Prepend[l, y]], {i, x-1, y}], 1]];
T[n_] := T[n] = Module[{g, r0}, g[l_] := g[l] = Module[{r, i}, r = {1}; For[i = 1, i <= n-1 , i++, If [l[[i]]>i && (i == 1 || l[[i-1]] < l[[i]]), r = zip[r, Join[{0}, g[ReplacePart[l, i -> l[[i]]-1]]]]]]; r]; r0 = {}; Do[r0 = zip[r0, g[j]], {j, d[n, n, {}]}]; r0]; Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Feb 13 2017, translated from Maple *)

cp's OEIS Frontend

A006245 Number of primitive sorting networks on n elements; also number of rhombic tilings of a 2n-gon.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A057863 a(n) = Product_{k=1..n} (2k-1)!!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003121 Strict sense ballot numbers: n candidates, k-th candidate gets k votes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A219311 Number T(n,k) of standard Young tableaux for partitions of n into exactly k distinct parts; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A219274 Number T(n,k) of standard Young tableaux for partitions of n into distinct parts with largest part k; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions