A133787 Number of wide partitions whose first part is of size n.

1, 3, 8, 24, 71, 226, 718, 7860, 26669, 91152, 316194, 1103506, 3892806, 13803606, 43946652

Offset

1,2

Comments

A wide partition is a partition with the property that any sub-partition (meaning, a partition obtained by taking some of the parts) dominates its conjugate.

A special case of Rota's Basis Conjecture is a generalization of the Dinitz Conjecture, namely that there is a diagram - a Young Tableaux such that you see 1 through n in each row of size n and at most one of each digit in each column - if and only if the partition is wide.

Links

Table of n, a(n) for n=1..15.

T. Chow, C. Fan, M. Goemans, J. Vondrak, Wide Partitions, Latin Tableaux and Rota's Basis Conjecture, Advances in Applied Mathematics, Vol. 31 (2003), No. 2, pp. 334-358.

Example

If a wide partition has its first part of size n, then it has to fit in an n X n grid, or it itself does not dominate its conjugate. a(2) is equal to 3 because {2}, {2,1} and {2,2} are all wide partitions.

Crossrefs

Sequence in context: A291243 A153774 A052855 * A080923 A118264 A006365

Adjacent sequences: A133784 A133785 A133786 * A133788 A133789 A133790

Keyword

hard,more,nonn

Author

Paul Raff, Jan 02 2008

Status

approved