combinat::ribbons – ribbons and tableaux of ribbon shape
The library combinat::ribbons provides functions for counting, generating, and manipulating ribbons and tableaux of ribbon shape. These objects are typed objects.
Superdomain
Categories
Cat::CombinatorialClassWith2DBoxedRepresentation
Axioms
Related Domains:
combinat::ribbonsTableaux, combinat::skewTableaux
Details:
First, a ribbon rib is a particular case of skew partition with a connection condition: the last box of a row is over the first one of the next row. (for details on skew partitions see combinat::skewPartitions). Due to this connection condition, a ribbon is completely defined by the lenght of each row.This is an example of a ribbon of shape [3, 2, 1]:
+---+
| |
+---+---+
| | |
+---+---+---+---+
| | | |
+---+---+---+
If we fill the boxes with numbers we get a special case of skew tableaux (see combinat::skewTableaux). Such kind of filling is a Young tableau of ribbon shape, or for shorter, a tableau of ribbon shape, if the numbers in the boxes verify some order constraints: they are non-decreasing along rows and (strictly) increasing from bottom to top along columns. As a ribbon is completely defined by the lenght of each line, a tableau of ribbon shape is entirely defined by the filling of each line given from top to bottom. This is the reason why the expression representation of a tableau of ribbon shape is the list of rows. Here is an example of tableau of ribbon shape [[4], [3, 3], [2, 2, 3]]:
+---+
| 4 |
+---+---+---+
| 3 | 3 |
+---+---+---+---+
| 2 | 2 | 3 |
+---+---+---+
Moreover, if every positive integer from 1 up to the number of cases appears exactly once, the tableau of ribbon shape is called standard. Here is an example of a standard tableau of ribbon shape [[3], [2, 4], [1, 5, 6]]:
+---+
| 1 |
+---+---+---+
| 2 | 4 |
+---+---+---+---+
| 3 | 5 | 6 |
+---+---+---+
A tableau of ribbon shape (as a typed object) has for expression the list of its rows, from top to bottom. For example, the above tableau of ribbon shape has for expression: [[3], [2, 4], [1, 5, 6]].
There is a 1:1 application between compositions and tableaux of ribbon shape, in particular there is a bijection between permutations and standard tableaux of ribbon shape. In the second case, given a permutation we construct its corresponding tableau of ribbon shape in this way: lengths of each row are lengths between the descents in the corresponding permutation (see combinat::permutations). For example to the permutation [2, 4, 1, 3, 6, 5] corresponds the following tableau of ribbon shape [1, 3, 2]:
+---+---+
| 2 | 4 |
+---+---+---+---+
| 1 | 3 | 6 |
+---+---+---+---+
| 5 |
+---+
Entries
|
"typeFilling" |
type for a filling without increasing conditions between cells. Type::ListOf(Type::ListOf(Type::NonNegInt)) . |
|
"typeRibbon" |
type for a filling with semi-standard conditions (checked with the isA function).Type::Predicate("Ribbon", dom::isA) . |
|
"typeStandardRibbon" |
type for a filling with standard conditions (checked with the isAStandard function).Type::Predicate("StandardRibbon", dom::isAStandard) . |
new – creating a new ribbon as a typed object or listing all the standard ribbons of a given shape
combinat::ribbons::new(Type::Union(combinat::compositions, dom::typeFilling ) x)
If the type is a typeFilling, creates the typed object for the corresponding ribbon x and returns its external representation.
If the argument is a shape, returns the list of all standard ribbons of shape x.
isA – test if an object is a tableau of ribbon shape
combinat::ribbons::isA(tableau of ribbon shape ribShapeTab, <composition shp>)
Returns whether ribShapeTab is a tableau of ribbon shape or not.
If the optional argument is present, it returns whether ribShapeTab is a tableau of shape the given ribbon shp or not.
isAStandard – test if an object is a standard tableau of ribbon shape
combinat::ribbons::isAStandard(tableau of ribbon shape ribShapeTab, <composition shp>)
Returns whether ribShapeTab is a standard tableau of ribbon shape or not.
If the optional argument is present, it returns whether ribShapeTab is a standard tableau of shape the ribbon shp or not.
fromShapeAndWord – tableau from its ribbon shape and natural reading
combinat::ribbons::fromShapeAndWord(composition shape, word w)
Returns the filling of the shape whose natural reading is the word w. Please note that the result is not necessarily a tableau of ribbon shape.
list – list of standard tableaux of a given ribbon shape
combinat::ribbons::list(composition shp)
Returns the list of the standard tableaux of shape the ribbon shp. We use the list function of permutation from descents (see combinat::permutations)
count – number of standard tableaux of ribbon shape
combinat::ribbons::count(composition shp)
Returns the number of standard tableaux of ribbon shape shp.
first – first standard tableaux of ribbon shape
combinat::ribbons::first(composition shp)
Returns the smallest standard tableaux of ribbon shape shp.
last – last standard tableaux of ribbon shape
combinat::ribbons::last(composition shp)
Returns the biggest standard tableaux of ribbon shape shp.
toWord – composition from a given tableau of ribbon shape
combinat::ribbons::toWord(tableau of ribbon shape ribTab)
Returns the composition corresponding to a given tableau of ribbon shape.
fromWord – tableau of ribbon shape from a composition
combinat::ribbons::fromWord(composition comp)
Returns the tableau of ribbon shape corresponding to a given composition. This function is the inverse of the previous function.
Ribbons are typed objects, which can be constructed as follows:
combinat::ribbons([[2, 3], [1, 4]])
+---+---+
| 2 | 3 |
+---+---+---+
| 1 | 4 |
+---+---+
These are two examples of testing whether an object is a tableau of ribbon shape. In the second one we provide the optional argument shape
combinat::ribbons::isA([[2, 3], [1, 4]],[2,2]);
combinat::ribbons::isA([[5, 6], [2, 3], [1,4]], [2, 2])
These are two examples of standard tableaux of ribbon shape:
combinat::ribbons::isAStandard([[3,4],[1,2]]);
combinat::ribbons::isAStandard([[2,4],[2,3]])
Here is the list of standard tableaux of ribbon shape 
:
combinat::ribbons::list([2,2])
-- +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ --
| | 1 | 3 | | 1 | 4 | | 2 | 3 | | 2 | 4 | | 3 | 4 | |
| +---+---+---+, +---+---+---+, +---+---+---+, +---+---+---+, +---+---+---+ |
| | 2 | 4 | | 2 | 3 | | 1 | 4 | | 1 | 3 | | 1 | 2 | |
-- +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ --
There are 
standard tableaux of shape the ribbon 
:
combinat::ribbons::count([3,2,2])
Given a word, we can build the corresponding tableau of ribbon shape: the result is not necessary a standard tableau of ribbon shape, it depends on the provided word.
combinat::ribbons::fromShapeAndWord([2, 3], [2, 5, 6, 1, 67])
+---+---+
| 2 | 5 |
+---+---+---+----+
| 6 | 1 | 67 |
+---+---+----+
These two functions permit to create a tableau of ribbon shape from a composition and vice versa.
combinat::ribbons::fromWord([1, 3, 2, 4])
+---+---+
| 1 | 3 |
+---+---+---+
| 2 | 4 |
+---+---+
combinat::ribbons::toWord(combinat::ribbons([[4, 5, 6], [2, 3], [1]]));
Changes in MuPAD 3.1
New Function.