login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

%D D. E. Barton and C. L. Mallows, Some aspects of the random sequence, Ann. Math. Statist. 36 (1965) 236-260.

%D H. Hiller. Combinatorics and intersection of Schubert varieties. Comment. Math. Helv. 57 (1982), 41-59.

%D G. Kreweras, Sur un probleme de scrutin a plus de deux candidats, Publications de l'Institut de Statistique de l'Universit\'{e} de Paris, 26 (1981), 69-87.

%D F. Ruskey, Generating linear extensions of posets by transpositions, J. Combin. Theory, B 54 (1992), 77-101.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D George Story, Counting Maximal Chains in Weighted Voting Posets, Rose-Hulman Undergraduate Mathematics Journal, Vol. 14, No. 1, 2013.

%D R. M. Thrall, A combinatorial problem, Michigan Math. J. 1, (1952), 81-88.

%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://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&amp;id=pdf_1&amp;handle=euclid.aoms/1177700286">Some aspects of the random sequence</a>, Ann. Math. Statist. 36 (1965) 236-260.

%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 R. M. Thrall, <a href="http://projecteuclid.org/Dienst/Repository/1.0/Disseminate/euclid.mmj/1028989731/body/pdf">A combinatorial problem</a>, Michigan Math. J. 1, (1952), 81-88.

%H Dennis White, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.3034">Sign-balanced posets</a>

%F a(n) = C(n+1, 2)!*(1!*2!*...*(n-1)!)/(1!*3!*...*(2n-1)!).

%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 ..0.2.6.9..0.2.5.9..0.3.5.9..0.3.6.9..

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

%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 October 25 17:33 EDT 2014. Contains 248557 sequences.