

A003121


Strict sense ballot numbers: n candidates, kth candidate gets k votes.
(Formerly M2048)


12



1, 1, 1, 2, 12, 286, 33592, 23178480, 108995910720, 3973186258569120, 1257987096462161167200, 3830793890438041335187545600, 123051391839834932169117010215648000, 45367448380314462649742951646437285434233600, 207515126854334868747300581954534054343817468395494400
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Also, number of even minus number of odd extensions of truncated n1 by 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, ..., n1. A symbolic sequence is a sequence that has n occurrences of 0, n1 occurrences of 1, ..., one occurrence of n1 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 ShapiroShapiro 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 321 > 231 > 132 & 213 > 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 (rcgraphs) 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+j1,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, (n1) 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 rowinterlacing triangles are there without that restriction?  Clark Kimberling, Dec 02 2014
Number of maximal chains of length C(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 nxn permutation matrices corresponding to permutations that avoid the patterns 132 and 312.  Robert Davis, Dec 04 2016


REFERENCES

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), 6987.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..30
E. Aas and S. Linusson, Continuous multiline queues and TASEP, 2014
D. E. Barton and C. L. Mallows, Some aspects of the random sequence, Ann. Math. Statist. 36 (1965) 236260.
R. Davis and B. Sagan, PatternAvoiding Polytopes, arXiv:1609.01782 [math.CO], 2016.
H. Hiller, Combinatorics and intersection of Schubert varieties, Comment. Math. Helv. 57 (1982), 4159. [Broken link]
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), 6987. [Annotated scanned copy]
Colin Mallows, Letter to N. J. A. Sloane, date unknown.
F. Ruskey, Generating linear extensions of posets by transpositions, J. Combin. Theory, B 54 (1992), 77101.
B. Shapiro and M. Shapiro, A few riddles behind Rolle's theorem, Amer. Math. Monthly, 119 (2012), 787795.
George Story, Counting Maximal Chains in Weighted Voting Posets, RoseHulman Undergraduate Mathematics Journal, Vol. 14, No. 1, 2013.
R. M. Thrall, A combinatorial problem, Michigan Math. J. 1, (1952), 8188.
Dennis White, Signbalanced posets, Journal of Combinatorial Theory, Series A, Volume 95, Issue 1, July 2001, Pages 138.
Wikipedia, Tamari lattice


FORMULA

a(n) = C(n+1, 2)!*(1!*2!*...*(n1)!)/(1!*3!*...*(2n1)!).
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 GlaisherKinkelin constant (see A074962).  Vaclav Kotesovec, Nov 13 2014


EXAMPLE

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
.
 R. H. Hardin, Jul 06 2012


MAPLE

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


MATHEMATICA

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


PROG

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


CROSSREFS

Cf. A005118, A018241, A007724, A004065, A131811, A064049, A064050.
A213457 is also closely related.
Cf. A000108, A027686.
Sequence in context: A012444 A012754 A083568 * A211937 A176037 A057170
Adjacent sequences: A003118 A003119 A003120 * A003122 A003123 A003124


KEYWORD

nonn,nice,easy


AUTHOR

Colin Mallows


EXTENSIONS

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


STATUS

approved



