This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003121 Strict sense ballot numbers: n candidates, k-th candidate gets k votes.
(Formerly M2048)

%I M2048

%S 1,1,1,2,12,286,33592,23178480,108995910720,3973186258569120,

%T 1257987096462161167200,3830793890438041335187545600,

%U 123051391839834932169117010215648000,45367448380314462649742951646437285434233600

%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 by 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

%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 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 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 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="http://arXiv.org/abs/math.CA/0302215">A few riddles behind Rolle's theorem</a>, Amer. Math. Monthly, 119 (2012), 787-795.

%H George Story, <a href="http://www.rose-hulman.edu/mathjournal/archives/2013/vol14-n1/paper12/v14n1-12pd.pdf">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.

%F a(n) = C(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 The a(4) = 12 ways to fill a triangle with the numbers 0 through 9:

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

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

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

%e - _R. H. Hardin_, Jul 06 2012

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

%K nonn,nice,easy,changed

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified February 1 09:46 EST 2015. Contains 254020 sequences.