Safe Haskell | None |
---|---|
Language | Haskell2010 |
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 such standard tableaux are
1, 1, 2, 12, 286, 33592, 23178480, ...
OEIS:A003121, "Strict sense ballot numbers", https://oeis.org/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 "GT simplex 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.
Synopsis
- type Tableau a = [[a]]
- newtype Tri = Tri {}
- type TriangularArray a = Array Tri a
- fromTriangularArray :: TriangularArray a -> Tableau a
- triangularArrayUnsafe :: Tableau a -> TriangularArray a
- asciiTriangularArray :: Show a => TriangularArray a -> ASCII
- asciiTableau :: Show a => Tableau a -> ASCII
- gtSimplexContent :: TriangularArray Int -> Int
- _gtSimplexContent :: Tableau Int -> Int
- invertGTSimplexTableau :: TriangularArray Int -> TriangularArray Int
- _invertGTSimplexTableau :: [[Int]] -> [[Int]]
- gtSimplexTableaux :: Int -> [TriangularArray Int]
- _gtSimplexTableaux :: Int -> [Tableau Int]
- countGTSimplexTableaux :: Int -> [Int]
Types
Set of (i,j)
pairs with i>=j>=1
.
type TriangularArray a = Array Tri a Source #
Triangular arrays
fromTriangularArray :: TriangularArray a -> Tableau a Source #
triangularArrayUnsafe :: Tableau a -> TriangularArray a Source #
ASCII
asciiTriangularArray :: Show a => TriangularArray a -> ASCII Source #
Content
gtSimplexContent :: TriangularArray Int -> Int Source #
invertGTSimplexTableau :: TriangularArray Int -> TriangularArray Int Source #
We can flip the numbers in the tableau so that the interval [1..c]
becomes
[c..1]
. This way we a get a maybe more familiar form, when each row and each
column is strictly decreasing (to the right and to the bottom).
_invertGTSimplexTableau :: [[Int]] -> [[Int]] Source #
Enumeration
gtSimplexTableaux :: Int -> [TriangularArray Int] Source #
Generates all tableaux of size k
. Effective for k<=6
.
countGTSimplexTableaux :: Int -> [Int] Source #
Note: This is slow (it actually generates all the tableaux)