A061343 Number of standard shifted tableaux with n entries.

1, 1, 2, 3, 6, 12, 27, 63, 154, 398, 1055, 2970, 8503, 25651, 78483, 250487, 811802, 2723130, 9295483, 32653552, 116866283, 428464743, 1600474365, 6102119282, 23690388631, 93631999867, 376561553417, 1538997717423, 6395852269479, 26978392034357, 115628083386280, 502520979828775

Offset: 1

Author

V. Reiner and D. White (reiner(AT)math.umn.edu), Jun 07 2001

Keywords

• nonn
• nice

Comments

Number of ballot sequences (see A000085) where the number of occurrences of k in any prefix is strictly greater than the number of occurrences of k+1. - Joerg Arndt, May 21 2016

Examples

			From _Joerg Arndt_, May 21 2016: (Start)
The a(7) = 27 tableaux correspond to the following ballot sequences (dots denote zeros).
##:     ballot sequence          partition
01:    [ . . . . . . . ]       [ 7 . . . . . . ]
02:    [ . . . . . . 1 ]       [ 6 1 . . . . . ]
03:    [ . . . . . 1 . ]       [ 6 1 . . . . . ]
04:    [ . . . . . 1 1 ]       [ 5 2 . . . . . ]
05:    [ . . . . 1 . . ]       [ 6 1 . . . . . ]
06:    [ . . . . 1 . 1 ]       [ 5 2 . . . . . ]
07:    [ . . . . 1 1 . ]       [ 5 2 . . . . . ]
08:    [ . . . . 1 1 1 ]       [ 4 3 . . . . . ]
09:    [ . . . . 1 1 2 ]       [ 4 2 1 . . . . ]
10:    [ . . . 1 . . . ]       [ 6 1 . . . . . ]
11:    [ . . . 1 . . 1 ]       [ 5 2 . . . . . ]
12:    [ . . . 1 . 1 . ]       [ 5 2 . . . . . ]
13:    [ . . . 1 . 1 1 ]       [ 4 3 . . . . . ]
14:    [ . . . 1 . 1 2 ]       [ 4 2 1 . . . . ]
15:    [ . . . 1 1 . . ]       [ 5 2 . . . . . ]
16:    [ . . . 1 1 . 1 ]       [ 4 3 . . . . . ]
17:    [ . . . 1 1 . 2 ]       [ 4 2 1 . . . . ]
18:    [ . . . 1 1 2 . ]       [ 4 2 1 . . . . ]
19:    [ . . 1 . . . . ]       [ 6 1 . . . . . ]
20:    [ . . 1 . . . 1 ]       [ 5 2 . . . . . ]
21:    [ . . 1 . . 1 . ]       [ 5 2 . . . . . ]
22:    [ . . 1 . . 1 1 ]       [ 4 3 . . . . . ]
23:    [ . . 1 . . 1 2 ]       [ 4 2 1 . . . . ]
24:    [ . . 1 . 1 . . ]       [ 5 2 . . . . . ]
25:    [ . . 1 . 1 . 1 ]       [ 4 3 . . . . . ]
26:    [ . . 1 . 1 . 2 ]       [ 4 2 1 . . . . ]
27:    [ . . 1 . 1 2 . ]       [ 4 2 1 . . . . ]
(End)
		

References

• D. E. Knuth, The Art of Computer Programming, Vol. 3 (Sorting and searching), page 71, Section 5.1.4, Exercise 21 (page 67 in the second edition).

Links

• Joerg Arndt, Table of n, a(n) for n = 1..101
• Joerg Arndt, PARI/GP script to compute terms.
• R. Srinivasan, On a theorem of Thrall in combinatorial analysis, The American Mathematical Monthly, 70(1), 1963, pp. 41-44.
• R. M. Thrall, A combinatorial problem, Michigan Math. J. 1, (1952), 81-88.

Crossrefs

Cf. A000085, A003121 (strict ballot sequences with partition [j, j-1, ..., 3, 2, 1]).

Formula

a(n) is the sum over all partitions into distinct parts of Thrall's formula (4) on page 83, see the PARI script arndt-A061343.gp. - Joerg Arndt, May 09 2013

Extensions

More terms from Joerg Arndt, May 08 2013