combinat-0.2.4.1: Generation of various combinatorial objects.Source codeContentsIndex
Math.Combinat.Tableaux.Kostka
Description

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.

Synopsis
type Tableau a = [[a]]
newtype Tri = Tri {
unTri :: (Int, Int)
}
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
type Tableau a = [[a]]Source
newtype Tri Source
Set of (i,j) pairs with i>=j>=1.
Constructors
Tri
unTri :: (Int, Int)
show/hide Instances
type TriangularArray a = Array Tri aSource
Triangular arrays
fromTriangularArray :: TriangularArray a -> Tableau aSource
triangularArrayUnsafe :: Tableau a -> TriangularArray 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 :: TriangularArray Int -> IntSource
_kostkaContent :: Tableau Int -> IntSource
Produced by Haddock version 2.6.1