combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Safe HaskellNone
LanguageHaskell2010

Math.Combinat.Tableaux.GelfandTsetlin.Cone

Contents

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

Types

type Tableau a = [[a]] Source #

A tableau is simply represented as a list of lists.

newtype Tri Source #

Set of (i,j) pairs with i>=j>=1.

Constructors

Tri 

Fields

Instances
Eq Tri Source # 
Instance details

Defined in Math.Combinat.Tableaux.GelfandTsetlin.Cone

Methods

(==) :: Tri -> Tri -> Bool #

(/=) :: Tri -> Tri -> Bool #

Ord Tri Source # 
Instance details

Defined in Math.Combinat.Tableaux.GelfandTsetlin.Cone

Methods

compare :: Tri -> Tri -> Ordering #

(<) :: Tri -> Tri -> Bool #

(<=) :: Tri -> Tri -> Bool #

(>) :: Tri -> Tri -> Bool #

(>=) :: Tri -> Tri -> Bool #

max :: Tri -> Tri -> Tri #

min :: Tri -> Tri -> Tri #

Show Tri Source # 
Instance details

Defined in Math.Combinat.Tableaux.GelfandTsetlin.Cone

Methods

showsPrec :: Int -> Tri -> ShowS #

show :: Tri -> String #

showList :: [Tri] -> ShowS #

Ix Tri Source # 
Instance details

Defined in Math.Combinat.Tableaux.GelfandTsetlin.Cone

Methods

range :: (Tri, Tri) -> [Tri] #

index :: (Tri, Tri) -> Tri -> Int #

unsafeIndex :: (Tri, Tri) -> Tri -> Int

inRange :: (Tri, Tri) -> Tri -> Bool #

rangeSize :: (Tri, Tri) -> Int #

unsafeRangeSize :: (Tri, Tri) -> Int

Show a => DrawASCII (TriangularArray a) Source # 
Instance details

Defined in Math.Combinat.Tableaux.GelfandTsetlin.Cone

type TriangularArray a = Array Tri a Source #

Triangular arrays

ASCII

Content

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

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)