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

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

Adjacent sequences: A061340 A061341 A061342 * A061344 A061345 A061346

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