|
%I M2048 #174 Dec 30 2023 12:10:21
%S 1,1,1,2,12,286,33592,23178480,108995910720,3973186258569120,
%T 1257987096462161167200,3830793890438041335187545600,
%U 123051391839834932169117010215648000,45367448380314462649742951646437285434233600,207515126854334868747300581954534054343817468395494400
%N Strict sense ballot numbers: n candidates, k-th candidate gets k votes.
%C Also, number of even minus number of odd extensions of truncated (n-1) X n grid diagram.
%C 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
%C 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).
%C E.g., a(3) = 2 as we can write:
%C 1 1
%C 2 3 or 2 4
%C 4 5 6 3 5 6
%C (or transpose these to have shifted tableaux). - _Jon Perry_, Jun 13 2003, edited by _Joel B. Lewis_, Aug 27 2011
%C 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
%C 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
%C 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
%C 6
%C 4 8
%C 2 5 9
%C 1 3 7 10
%C - _Clark Kimberling_, Mar 25 2012
%C 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
%C 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
%C 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
%C 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
%C 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
%C From _Emily Gunawan_, Feb 26 2022: (Start)
%C 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.
%C 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.
%C 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)
%D 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, <a href="/A003121/b003121.txt">Table of n, a(n) for n = 0..30</a>
%H E. Aas and S. Linusson, <a href="http://www.diva-portal.org/smash/get/diva2:768232/FULLTEXT01.pdf">Continuous multiline queues and TASEP</a>, 2014; also <a href="https://arxiv.org/abs/1501.04417">arxiv version</a>, arXiv:1501.04417 [math.CO], 2015-2017.
%H Joerg Arndt, <a href="/A003121/a003121.txt">The a(5)=286 Young tableaux of shape [1,2,3,4,5]</a>.
%H D. E. Barton and C. L. Mallows, <a href="http://dx.doi.org/10.1214/aoms/1177700286">Some aspects of the random sequence</a>, Ann. Math. Statist. 36 (1965) 236-260.
%H Andrew Beveridge, Ian Calaway, and Kristin Heysse, <a href="https://arxiv.org/abs/1912.12319">de Finetti Lattices and Magog Triangles</a>, arXiv:1912.12319 [math.CO], 2019.
%H R. Davis and B. Sagan, <a href="https://arxiv.org/abs/1609.01782">Pattern-Avoiding Polytopes</a>, arXiv:1609.01782 [math.CO], 2016.
%H William T. Dugan, Maura Hegarty, Alejandro H. Morales, and Annie Raymond, <a href="https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2023/80.pdf">Generalized Pitman-Stanley flow polytopes</a>, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #80.
%H William T. Dugan, Maura Hegarty, Alejandro H. Morales, and Annie Raymond, <a href="https://arxiv.org/abs/2307.09925">Generalized Pitman-Stanley polytope: vertices and faces</a>, arXiv:2307.09925 [math.CO], 2023.
%H S. Fishel and L. Nelson, <a href="https://doi.org/10.1090/S0002-9939-2014-12069-7">Chains of maximum length in the Tamari lattice</a>, Proc. Amer. Math. Soc. 142 (2014), 3343-3353.
%H Joël Gay, <a href="https://tel.archives-ouvertes.fr/tel-01861199">Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups</a>, Doctoral Thesis, Discrete Mathematics [cs.DM], Université Paris-Saclay, 2018.
%H H. Hiller, <a href="http://dx.doi.org/10.5169/seals-43873">Combinatorics and intersection of Schubert varieties</a>, Comment. Math. Helv. 57 (1982), 41-59.
%H C. Hohlweg, C. Lange, and H. Thomas, <a href="https://arxiv.org/abs/0709.4241">Permutahedra and generalized associahedra</a>, arXiv:0709.4241 [math.CO], 2007-2008; Adv. Math. 226 (2011), no. 1, 608-640.
%H G. Kreweras, <a href="/A005118/a005118.pdf">Sur un problème de scrutin à plus de deux candidats</a>, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87. [Annotated scanned copy]
%H Colin Mallows, <a href="/A003121/a003121.pdf">Letter to N. J. A. Sloane, date unknown</a>.
%H Svante Linusson and Samu Potka, <a href="https://arxiv.org/abs/1804.10034">New properties of the Edelman-Greene bijection</a>, arXiv:1804.10034 [math.CO], 2018.
%H N. Reading, <a href="https://arxiv.org/abs/math/0402086">Cambrian lattices</a>, arXiv:math/0402086 [math.CO], 2004-2005; Adv. Math. 205 (2006), no. 2, 313-353.
%H F. Ruskey, <a href="http://dx.doi.org/10.1016/0095-8956(92)90067-8">Generating linear extensions of posets by transpositions</a>, J. Combin. Theory, B 54 (1992), 77-101.
%H B. Shapiro and M. Shapiro, <a href="https://arxiv.org/abs/math/0302215">A few riddles behind Rolle's theorem</a>, arXiv:math/0302215 [math.CA], 2003-2005; Amer. Math. Monthly, 119 (2012), 787-795.
%H George Story, <a href="https://scholar.rose-hulman.edu/rhumj/vol14/iss1/12">Counting Maximal Chains in Weighted Voting Posets</a>, Rose-Hulman Undergraduate Mathematics Journal, Vol. 14, No. 1, 2013.
%H R. M. Thrall, <a href="http://dx.doi.org/10.1307/mmj/1028989731">A combinatorial problem</a>, Michigan Math. J. 1, (1952), 81-88.
%H Dennis White, <a href="http://dx.doi.org/10.1006/jcta.2000.3146">Sign-balanced posets</a>, Journal of Combinatorial Theory, Series A, Volume 95, Issue 1, July 2001, Pages 1-38.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Tamari_lattice">Tamari lattice</a>
%F a(n) = binomial(n+1, 2)!*(1!*2!*...*(n-1)!)/(1!*3!*...*(2n-1)!).
%F 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
%e From _R. H. Hardin_, Jul 06 2012: (Start)
%e The a(4) = 12 ways to fill a triangle with the numbers 0 through 9:
%e .
%e 5 6 6 5
%e 3 7 3 7 2 7 2 7
%e 1 4 8 1 4 8 1 4 8 1 4 8
%e 0 2 6 9 0 2 5 9 0 3 5 9 0 3 6 9
%e .
%e 5 3 3 4
%e 3 6 2 6 2 7 3 7
%e 1 4 8 1 5 8 1 5 8 1 5 8
%e 0 2 7 9 0 4 7 9 0 4 6 9 0 2 6 9
%e .
%e 4 4 5 4
%e 2 6 2 7 2 6 3 6
%e 1 5 8 1 5 8 1 4 8 1 5 8
%e 0 3 7 9 0 3 6 9 0 3 7 9 0 2 7 9
%e .
%e (End)
%p f:= n-> ((n*n+n)/2)!*mul((i-1)!/(2*i-1)!, i=1..n); seq(f(n), n=0..20);
%t 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 *)
%o (PARI) a(n)=((n*n+n)/2)!*prod(i=1,n,(i-1)!/(2*i-1)!)
%Y Cf. A005118, A018241, A007724, A004065, A131811, A064049, A064050.
%Y A213457 is also closely related.
%Y Cf. A000108, A027686, A282698.
%K nonn,nice,easy
%O 0,4
%A _Colin Mallows_
%E More terms from _Michael Somos_
%E Additional references from _Frank Ruskey_
%E Formula corrected by _Eric Rowland_, Jun 18 2010
| 