login
A061343
Number of standard shifted tableaux with n entries.
3
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,3
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
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, 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.
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
EXAMPLE
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)
CROSSREFS
Cf. A000085, A003121 (strict ballot sequences with partition [j, j-1, ..., 3, 2, 1]).
Sequence in context: A019525 A108915 A082395 * A057649 A104872 A006082
KEYWORD
nonn,nice
AUTHOR
V. Reiner and D. White (reiner(AT)math.umn.edu), Jun 07 2001
EXTENSIONS
More terms from Joerg Arndt, May 08 2013
STATUS
approved