combinat-0.2.5.0: Generation of various combinatorial objects.

Safe Haskell None

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

# Documentation

type Tableau a = [[a]]Source

newtype Tri Source

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

Constructors

 Tri FieldsunTri :: (Int, Int)

Instances

 Eq Tri Ord Tri Show Tri Ix Tri

type TriangularArray a = Array Tri aSource

Triangular arrays

Generates all tableaux of size `k`. Effective for `k<=6`.