This module contains a function to generate (equivalence classes of) triangular tableaux of size k, strictly increasing to the right and to the bottom. For example
1 2 4 3 5 8 6 7 9 10
is such a tableau of size 4.
The numbers filling a tableau always consist of an interval [1..c]
;
c
is called the content of the tableaux. There is a unique tableau
of minimal content 2k-1
:
1 2 3 3 4 5 4 5 6 7
Let us call the tableaux with maximal content (that is, m = binomial (k+1) 2
)
standard. The number of standard tableaux are
1, 1, 2, 12, 286, 33592, 23178480, ...
OEIS:A003121, "Strict sense ballot numbers", http://www.research.att.com/~njas/sequences/A003121.
See R. M. Thrall, A combinatorial problem, Michigan Math. J. 1, (1952), 81-88.
The number of tableaux with content c=m-d
are
d= | 0 1 2 3 ... -----+---------------------------------------------- k=2 | 1 k=3 | 2 1 k=4 | 12 18 8 1 k=5 | 286 858 1001 572 165 22 1 k=6 | 33592 167960 361114 436696 326196 155584 47320 8892 962 52 1
We call these "Kostka tableaux" (in the lack of a better name), since they are in bijection with the simplicial cones in a canonical simplicial decompositions of the Gelfand-Tsetlin cones (the content corresponds to the dimension), which encode the combinatorics of Kostka numbers.
- type Tableau a = [[a]]
- newtype Tri = Tri {}
- type TriangularArray a = Array Tri a
- fromTriangularArray :: TriangularArray a -> Tableau a
- triangularArrayUnsafe :: Tableau a -> TriangularArray a
- kostkaTableaux :: Int -> [TriangularArray Int]
- _kostkaTableaux :: Int -> [Tableau Int]
- countKostkaTableaux :: Int -> [Int]
- kostkaContent :: TriangularArray Int -> Int
- _kostkaContent :: Tableau Int -> Int
Documentation
Set of (i,j)
pairs with i>=j>=1
.
type TriangularArray a = Array Tri aSource
Triangular arrays
fromTriangularArray :: TriangularArray a -> Tableau aSource
kostkaTableaux :: Int -> [TriangularArray Int]Source
Generates all tableaux of size k
. Effective for k<=6
.
_kostkaTableaux :: Int -> [Tableau Int]Source
countKostkaTableaux :: Int -> [Int]Source
_kostkaContent :: Tableau Int -> IntSource