ON THE YOUNG-FIBONACCI INSERTION ALGORITHM
JANVIER NZEUTCHAP
Abstract. This work is concerned with some properties of the Young-Fibonacci insertion algo-
rithm and its relation with Fomin’s growth diagrams. It also investigates a relation between the
combinatorics of Young-Fibonacci tableaux and the study of Okada’s algebra associated to the
Young-Fibonacci lattice. The original algorithm was introduced by Roby and we redefine it in such
a way that both the insertion and recording tableaux of any permutation are conveniently inter-
preted as chains in the Young-Fibonacci lattice. A property of Killpatrick’s evacuation is given a
simpler proof, but this evacuation is no longer needed in making Roby’s and Fomin’s constructions
coincide. We provide the set of Young-Fibonacci tableaux of size n with a structure of graded poset,
induced by the weak order on permutations of the symmetric group, and realized by transitive clo-
sure of elementary transformations on tableaux. We show that this poset gives a combinatorial
interpretation of the coefficients in the transition matrix from the analogue of complete symmet-
ric functions to analogue of the Schur functions in Okada’s algebra. We end with a quite similar
observation for four posets on Young-tableaux studied by Taskin.
Contents
1. Introduction 1
1.1. The Young-Fibonacci lattice 2
2. Young-Fibonacci tableaux and Young-Fibonacci insertion algorithm 3
2.1. Converting a chain in YFL into a standard Young-Fibonacci tableau 3
2.2. Redefining the Young-Fibonacci Insertion Algorithm 4
3. Young-Fibonacci insertion and growth in differential posets 6
3.1. Equivalence between Roby’s and Fomin’s constructions 7
3.2. Another viewpoint of Killpatrick’s evacuation for Young-Fibonacci tableaux 8
4. Fibonacci numbers and a statistic on Young-Fibonacci tableaux 9
5. A weak order on Young-Fibonacci tableaux 10
6. A connection with Okada’s algebra associated to the Young-Fibonacci lattice 15
7. Kostka numbers, the Littlewood Richardson rule, and four posets on Young tableaux 16
Concluding remarks and perspectives 18
Acknowledgements 18
References 19
1. Introduction
The Young lattice (YL) is defined on the set of partitions of positive integers, with covering
relations given by the natural inclusion order. The differential poset nature of this graph was
generalized by Fomin who introduced graph duality [13]. With this extension he introduced [15] a
generalization of the classical Robinson-Schensted-Knuth [1, 2] algorithm, giving a general scheme
for establishing bijective correspondences between couples of saturated chains in dual graded graphs,
both starting at a vertex of rank 0 and having a common end point of rank n, on the one hand,
and permutations of the symmetric group Sn on the other hand. This approach naturally leads to
the Robinson-Schensted insertion algorithm.
2000 Mathematics Subject Classification. Primary 05-06; Secondary 05E99.
Key words and phrases. Schensted-Fomin, insertion algorithm, Young-Fibonacci, lattice, tableaux, evacuation,
poset, Okada’s algebra, Kostka numbers.
http://arxiv.org/abs/0704.1969v1
2 J. NZEUTCHAP
Roby [17] gave an insertion algorithm analogous to the Schensted correspondence, which maps
a permutation σ onto a couple made of a Young-Fibonacci tableau P (σ) and a path tableau Q(σ).
Roby’s path tableau Q(σ) is canonically interpreted as a saturated chain in the Fibonacci lattice
Z(1) introduced by Stanley [11] and also by Fomin [14]. Roby also showed that Fomin’s approach
is partially equivalent to his construction.
Indeed in Roby’s construction, only the saturated chain Q̂ obtained from Fomin’s growth diagram
has an interpretation as a representation of the path tableau Q(σ), while there seems to be no way to
translate the Young-Fibonacci tableau P (σ) into its equivalent chain P̂ . Contrarily to the approach
of Killpatrick [8] who has used an evacuation to relate the two constructions of Roby and Fomin,
we show that with a suitable mechanism for converting a saturated chain in the Young-Fibonacci
lattice into a Young-Fibonacci tableau, Roby’s construction naturally coincides with Fomin’s one.
The paper is organized as follows. In Section 1.1 we recall the definition of the Young-Fibonacci
lattice, then in Section 2 we define a mechanism for converting a saturated chain in this lattice
into a standard Young-Fibonacci tableau. In the same section, we also introduce a modification in
Roby’s algorithm, in such a way that both the insertion and recording tableaux of any permutation
will have an interpretation in terms of saturated chain in the Young-Fibonacci lattice. In Section
3.1 we relate Roby’s algorithm with Fomin’s construction using growth diagrams and we compare it
to Killpatrick’s work. In Section 4, we define an analogue of Kostka numbers for Young-Fibonacci
tableaux, and we point out one of their relation with usual Fibonacci numbers. In Section 5 we
define and we study some properties of a poset on Young-Fibonacci tableaux. This poset turns
out to be a model for the interpretation as well as the computation of another analogue of Kostka
numbers, introduced by Okada [16] in an analogue of the algebra of symmetric functions, associated
to the Young-Fibonacci lattice. We prove this result is Section 6, and in the last section of the
paper we prove a similar result relating usual Kostka numbers with four posets on Young-tableaux
studied by Taskin [9].
1.1. The Young-Fibonacci lattice.
A Fibonacci diagram or snakeshape of size n is a column by column graphical representation of
a composition of an integer n, with parts equal to 1 or 2. The number of such compositions is the
nth Fibonacci number. A partial order is defined on the set of all snakeshapes, in such a way to
obtain an analogue of the Young lattice of partitions of integers (YL). This lattice is called the
Young-Fibonacci lattice (YFL) and it was introduced by Stanley [11] and also by Fomin [14]. As
we will see in the sequel, there is a considerable similarity between the two lattices, as well as the
combinatorics of tableaux their induce. The covering relations in YFL are given below, for any
snakeshape u.
(1) u is covered by the snakeshape obtained by attaching a single box just in front ;
(2) u is covered by the snakeshape obtained by adding a single box on top of its first single-boxed
column, reading u from left to right.
(3) if u starts with a series of two-boxed columns, then it is covered by all snakeshapes obtained
by inserting a single-boxed column just after any of those columns.
The rank |u| of a snakeshape u is the sum of digits of the corresponding Fibonacci word. Its
length will be denoted ℓ(u). Let u and v be two snakeshapes such that v covers u in YFL, the cell
added to u to obtain v is an inner corner of v, it is also called an outer corner of u.
Remark 1.1. Young-Fibonacci tableaux (YFT) will naturally appear as numberings of snake-
shapes, satisfying certain conditions described in the sequel, the same way as Young tableaux
are numberings of partitions of integers with prescribed numbering conditions. The numbering
conditions of Young-Fibonacci tableaux are deduced from the description of the Young-Fibonacci
insertion algorithm (Section 2.2).
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 3
Below is a pictorial representation of a finite realization of YFL, from rank 0 up to rank n = 4,
with black cells representing inner corners.
Figure 1. The Young-Fibonacci lattice.
Now let us look at the problem of converting a saturated chain in YFL into a standard YFT.
2. Young-Fibonacci tableaux and Young-Fibonacci insertion algorithm
In YL, any saturated chain starting at the empty partition can be canonically converted into a
standard Young tableau, and this representation is convenient in many ways. It consists in labeling
the boxes as their occur in the chain. As already observed by Roby [17], one question which presents
itself is to do the same in YFL for any saturated chain starting at the empty snakeshape ∅. The need
of such a conversion mechanism will appear in section 3.1 in the interpretation of two saturated
chains in a growth diagram.
One may also use the canonical labeling to convert a saturated chain of YFL into a tableau,
but Roby had already pointed out that one major problem with this canonical labeling is that
except for the trivial rule that each element in the top row must be greater than the one below it,
no other obvious rules govern what numberings are allowed for a given shape. We suggest that one
first defines simple rules governing what numberings are allowed for a given shape, so that it be
easy to decide if a numbering of a snakeshape is a legitimate Young-Fibonacci tableau or not. The
convention we use is described in the next section.
2.1. Converting a chain in YFL into a standard Young-Fibonacci tableau.
Since we do not use the same conventions as Roby [17] and Fomin [13], let us give the following
definition of Young-Fibonacci tableaux.
Definition 2.1. A numbering of a snakeshape with distinct nonnegative integers is a standard
Young-Fibonacci tableau (SYFT) under the following conditions.
(1) entries are strictly increasing in columns ;
(2) any entry on top in any column has no entry greater than itself on its right.
To convert a chain in YFL into a standard YFT, one will follow the canonical approach as
far as the new box added to the chain lies in the first column. Example with the chain Q̂ =
(∅, 1, 2, 12, 22, 221, 2211, 21211) ; the sub-chain (∅, 1, 2, 12, 22) is converted as follows.
∅ → 1 →
4 J. NZEUTCHAP
Now moving from the shape 22 to the shape 221 in YFL, one inserts a box just after a two-boxed
column of the previous shape. In such a situation, one will move the entry on top in that column
into the newly created box, and then shift the other entries of the top row to the right. Finally, if
n is the largest entry in the partial tableau obtained, then label the box on top in the first column
with (n + 1).
The conversion started above keeps on as follows, xk means that writing or moving the label x
is the kth action performed during the current step.
22 → 221 :
3 1 21
3 1 2
3 1 2
221 → 2211 :
3 1 2
3 1 2
3 1 41 2
3 1 4 2
3 1 4 2
2211 → 21211 :
3 1 4 2
3 1 4 2
3 61 1 4 2
3 6 1 4 2
It easily follows from the description above that this mechanism produces only legitimate YFT
(Definition 2.1), and that the conversion is reversible. Now another question which presents itself
is how to count standard YFT of a given shape u 6= ∅, we denote this number by Fu. Let us first
recall the formula counting linear extensions of a binary tree poset P.
(2.1) |Ext(P)| =
d1d2 · · · dn
where for the ith node vi, di is the number of nodes v ≤P vi. This formula is due to Knuth [3], and
since any snakeshape u can be canonically assimilated to a poset Pu, then we have the following.
Proposition 2.2. Standard Young-Fibonacci tableaux of a given shape are counted by the hook-
length formula for binary trees.
To apply the formula to a snakeshape u, count it cells from right to left and from bottom to top,
labeling the first box and each box appearing in the bottom row of any two-boxed column. The
number of standard YFT of the given shape is the product of all the labels obtained.
Example 2.3. Let us consider u = 2212.
a snakeshape
u = 2212
its poset Pu
hook lengths
6 4 1
F2212 =
2×3×5×7
= 6× 4× 1
2.2. Redefining the Young-Fibonacci Insertion Algorithm.
We refer the reader to [17, 8] for a description of the original algorithm ; below is the one we
consider.
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 5
Definition 2.4. The Young-Fibonacci insertion algorithm maps a permutation σ onto a couple of
standard YFT built as follows. The insertion tableau P (σ) is built by reading σ from right to left,
matching any of the letters encountered (and not yet matched) with the maximal one (not yet
matched) on its left if any, provided that the latter be greater than the first. The recording tableau
Q(σ) records the positions of the letters, in the reverse order of the one in which they are matched.
Example 2.5. For σ = 2715643, we have the following.
2 7 1 5 6 4 3
1 2 3 4 5 6 7
• P (σ) =
7 6 2
3 4 5 1
and Q(σ) =
7 6 3
2 5 4 1
Remark 2.6. That both P (σ) and Q(σ) are standard Young-Fibonacci tableaux (Definition 2.1)
is clear from the description of the algorithm. This is not the case in the original algorithm where
P (σ) and Q(σ) are not of the same type. Indeed, with the original insertion algorithm, the insertion
tableau is the same as the tableau P (σ) above, but the recording tableau Q(σ) which follows does
not satisfy Definition 2.1.
QRoby(σ) =
3 7 4
2 6 5 1
The definition of Q(σ) we adopt is inspired from the hypoplactic [4] and sylvester [5] insertion
algorithms, where Q(σ) also records the positions in σ of the labels of P (σ). With this definition,
some essential properties of the Young-Fibonacci correspondence have a much easier combinatorial
proof, which is not always the case in [17]. For example, let us recall the involution property.
Theorem 2.7. [17] For any permutation σ, P (σ−1) = Q(σ).
Proof. Consider the geometric construction by Killpatrick [8], and recall that P (σ) corresponds to
reading vertical coordinates of the rightmost and uppermost x in that order, for any broken line. As
for Q(σ), we have defined it in such a way that it corresponds to reading horizontal coordinates of
the uppermost and rightmost x in that order. The construction for σ−1 is obtained by transposing
the one for σ. �
Another fundamental property of Roby’s algorithm which is easily proved using Definition 2.4
follows.
Theorem 2.8. [17] Let σ be an involution of the symmetric group, then the cycle decomposition
of σ is the column reading of its insertion tableau P (σ).
We give two other canonical words associated with a tableau t ; so if we let YFC(t) denotes
the equivalence class made of permutations having t as insertion tableau, then YFC(t) has at least
three canonical elements. The first canonical element is its canonical involution, that is the only
involution the cycles of which coincide with the columns of t, as stated in Theorem 2.8. The two
other canonical elements are the maximal (resp. minimal) element for the lexicographical order.
We will make use of these elements in Section 5.
Lemma 2.9. Let t be a Young-Fibonacci tableau, w1 the left-to-right reading of its top row and w2
the right-to-left reading of its bottom row, then w1.w2 (where . denotes the usual concatenation of
words) is the maximal element (for the lexicographical order) of YFC(t), it is denoted wtmax.
Lemma 2.10. The word consisting of the right-to-left and up-down column reading of t is the
minimal element (for the lexicographical order) of YFC(t), it is denoted wtmin.
Proof. Clear from the description of the Young-Fibonacci insertion algorithm. �
6 J. NZEUTCHAP
An example is given with the tableau t below ; its canonical involution is (13)(26)(48)(5)(7) =
36185274, the maximal canonical element is 86315274, and the minimal one is 31562784.
8 6 3
4 7 2 5 1
We will see (Theorem 5.12) that YFC(t) is the set of linear extensions of a given poset, and
additionally, YFC(t) is an interval of the weak order on the symmetric group (Theorem 5.9).
3. Young-Fibonacci insertion and growth in differential posets
In this section we show that with the modification we have introduced in Roby’s original insertion
algorithm, together with the conversion mechanism discussed in section 2.1, the Young-Fibonacci
insertion algorithm naturally coincides with Fomin’s approach using growth diagrams. So we claim
that Killpatrick’s evacuation [8] is no longer needed in making the two constructions coincide. We
give a simplification of Killpatrick’s theorem relating Roby’s original algorithm to Fomin’s one
through an evacuation process, and we will later need this evacuation in the proof of Theorem 6.2
giving a combinatorial interpretation of Okada’s analogue of Kostka numbers.
Let us recall that Fomin’s construction with growth diagrams consists in using some local rules
in filling a diagram giving rise to a pair of saturated chains in YL. For any permutation σ, the
growth diagram d(σ) is build the following way. First draw the permutation matrix of σ ; next fill
the left and lower boundary of d(σ) with the empty snakeshape ∅. The rest of the construction is
iterative ; d(σ) is filled from the lower left corner to the upper right corner, following the diagonal.
At each step and for any configuration as pictured below, z is obtained by applying the local rules
to the vertices t, x, y and the permutation matrix element α. We refer the reader to [15] for more
details on this construction.
a1 α b1
Figure 2. A square in a growth diagram.
Algorithm 1 : local rules for YFL
1: if x 6= y and y 6= t then
2: z := t, with a two-boxed column added in front
3: else
4: if x = y = t and α = 1 then
5: z := t, with a single-boxed column added in front
6: else
7: z is defined in such a way that the edge bi is degenerated whenever ai is degenerated
8: end if
9: end if
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 7
3.1. Equivalence between Roby’s and Fomin’s constructions.
Let us build Fomin’s growth diagram for the permutation σ = 2715643.
∅ � �� ���
∅ � � ��
∅ � � ��
∅ � � ��
∅ � � ��
∅ � � �
∅ ∅ ∅ � � � � �
∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅
Figure 3. Example of growth diagram for the Young-Fibonacci insertion.
We get the paths Q̂ = (∅, 1, 2, 12, 22, 221, 2211, 21211) and P̂ = (∅, 1, 11, 21, 211, 1211, 2211, 21211)
on the upper and right boundary respectively. Now let us convert them into Young-Fibonacci
tableaux, using the mechanism discussed in section 2.1.
∅ → 1 → 2 1 →
2 4 1
2 5 4 1
7 6 3
2 5 4 1
= Q̂(σ) = Q(σ)
∅ → 1 →
3 4 1
6 5 2
3 4 1
7 6 2
3 4 5 1
= P̂ (σ) = P (σ)
So as we can see on this example, the two constructions naturally coincide.
Remark 3.1. Let us mention that because Roby used the canonical labeling to convert a chain
into a tableau, there seemed to be no way to convert the chain P̂ into its equivalent tableau P (σ).
Killpatrick’s algorithm was then an approach to relate P̂ with P (σ). Our own approach consists
in the introduction of a modification of the original algorithm, and a new labeling process.
Theorem 3.2. Let (P̂ (σ), Q̂(σ)) be the pair of Young-Fibonacci tableaux obtained from the permu-
tation σ by using Fomin’s growth diagram and let (P (σ), Q(σ)) be the Young-Fibonacci insertion
and recording tableaux using Roby’s insertion modified (Definition 2.4), then P̂ (σ) = P (σ) and
Q̂(σ) = Q(σ).
Proof. The equality P̂ (σ) = P (σ) follows from that any snakeshape P̂k appearing in P̂ is the shape
of the tableau P (σ/[1..k]) where σ/[1..k] is the restriction of σ to the interval [1..k]. Indeed, the path
P̂ is obtained applying to P (σ) the reverse process of the one described in section 2.1. In so doing,
the cell added to P̂k to get P̂k+1 lies in the first column when either σ/[1..k+1] ends with the letter
k + 1 or σ/[1..k+1] does not end with the letter k + 1 but σ/[1..k] ends with the letter k. A quite
similar reasoning is used to prove the equality Q̂(σ) = Q(σ). �
8 J. NZEUTCHAP
3.2. Another viewpoint of Killpatrick’s evacuation for Young-Fibonacci tableaux.
For a tableau t, this operation is defined only for top entries of the columns of t. Let a0 be such
an entry, the tableau resulting from the evacuation of a0 is denoted ev(t, a0) and is built as follows.
(1) if a0 is a single-boxed column, then just delete this column and, if this is necessary, shift
one component of the remaining tableau to connect it with the other one (e.g of line 3 in
the table below) ;
(2) otherwise, the box containing a0 is emptied and one compares the entry a1 that was just
below a0 with the entry a2 on top of the column just to the right if any. If a2 < a1 then
this terminates the evacuation process (e.g of line 4 in the table below). Otherwise, move
a2 on top of a1, creating a new empty box in the tableau. If the new empty box is a
single-boxed column, then this terminates the evacuation process (e.g of line 7, step 4, in
the table below), otherwise, iteratively repeat the process with the entries just below and
to the right of this new empty box.
Let t be a tableau of size n and shape u. If one successively evacuates the entries n, (n−1), · · · , 1
from t, labeling the boxes of u according to the positions of the empty cells at the end of the
evacuation of entries, one gets a path tableau denoted ev(t). Recall that a path tableau is the
canonical labeling of a saturated chain.
Remark 3.3. ev(t) is the same tableau as the one described by Killpatrick [8], with Young-
Fibonacci tableaux defined as in Definition 2.1.
7 t =
7 6 2
3 4 5 1
• 6 2
3 4 5 1
6 • 2
3 4 5 1
6 5 2
3 4 • 1 7
6 5 2
3 4 1
• 5 2
3 4 1
5 • 2
3 4 1
3 4 1
3 4 1
3 • 1
3 5 7
4 6 2
3 5 7
1 1 → • ev(t) =
4 6 2
3 5 7 1
Table 1. Evacuation on Young-Fibonacci tableaux.
Lemma 3.4. Let w be a word with no letter repeated, let a0 be one of its letters appearing as a
top element in a column of P (w), and let w0 be the word obtained from w by deleting the only
occurrence of a0, then ev(P (w), a0) = P (w0).
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 9
Proof. Easily from the description of the evacuation and the description of the Young-Fibonacci
insertion algorithm (Definition 2.4). �
We give a simpler proof of the following theorem by Killpatrick, relating ev(P (σ)) with P̂ .
Indeed, using the canonical labeling, Roby has converted the path P̂ into a path tableau P̂ (σ) and
Theorem 3.5. [8] ev(P (σ)) = P̂ (σ).
Proof. Follows from Lemma 3.4 and the remark that any snakeshape P̂k appearing in P̂ is the
shape of the tableau P (σ/[1..k]) where σ/[1..k] is the restriction of σ to the interval [1..k]. �
4. Fibonacci numbers and a statistic on Young-Fibonacci tableaux
In this section we point out a property of Young-Fibonacci numbers defined as an analogue of
Kostka numbers. Recall that the usual Kostka numbers Kλ, µ are defined for two partitions λ and µ
of the same integer n and they appear when expressing Schur functions sλ in terms of the monomial
symmetric functions mµ, and in the expression of the complete symmetric functions hµ in terms of
Schur functions sλ.
(4.1) sλ =
Kλ, µmµ ; hµ =
Kλ, µ sλ
We will not focus on the algebraic interpretation of the Kλ, µ but rather on their combinatorial
interpretation in terms of tableaux. Indeed, Kλ, µ counts the number of distinct semi-standard
Young-tableaux of shape λ and valuation µ, that is to say with µi entries i for i = 1 .. ℓ(µ). It is
then natural to introduce the same definition with Young-Fibonacci tableaux.
Definition 4.1. A semi-standard Young-Fibonacci tableau is a numbering of a snakeshape with
nonnegative integers, not necessarily distinct, preserving the conditions stated in Definition 2.1.
Definition 4.2. Let u and v be two snakeshapes of size n, the Young-Fibonacci number associated
to u and v, denoted Nu, v is the number of distinct semi-standard Young-Fibonacci tableaux of
shape u and valuation v, that is to say with vi entries i for i = 1 .. ℓ(v).
For example, for u = 221 and v = 1211, there are 4 distinct semi-standard Young-Fibonacci
tableaux of shape u and valuation v. So N221, 1211 = 4.
1 2 2
2 1 2
2 2 1
3 1 2
Proposition 4.3. Young-Fibonacci numbers are generated by the recurrence formulas below, where
both u and v are snakeshapes.
(4.2)
N∅, ∅ = 1 ; N2, 2 = 0
N1u, v1 = Nu, v ; N1u, v2 = Nu, v1
N2u, v1 =
w∈ v1
− Nu,w ; N2u, v2 =
w∈ v1
− Nu, w1
where v1
denotes the multiset of snakeshapes obtained from v either by deleting a single occurrence
of 1, or by decreasing a single entry not equal to 1, for example 21121
= [1112, 212, 212, 2111].
Proof. Easily from the definition of Young-Fibonacci tableaux and Young-Fibonacci numbers. �
10 J. NZEUTCHAP
v = 222 2211 2121 2112 21111 1221 1212 12111 1122 11211 11121 11112 111111
u = 222 2 3 4 5 6 4 5 6 5 7 8 12 15
2211 4 5 5 7 9 5 7 9 7 9 9 12 15
2121 2 3 4 4 5 4 4 5 4 6 8 8 10
2112 1 1 1 1 1 2 2 3 3 4 4 4 5
21111 2 3 3 3 4 3 3 4 3 4 4 4 5
1221 2 2 3 4 4 3 4 4 4 4 6 8 8
1212 1 1 1 1 1 1 2 2 3 3 3 4 4
12111 2 2 2 3 3 2 3 3 3 3 3 4 4
1122 1 1 1 1 1 1 1 1 2 2 3 3 3
11211 1 1 2 2 2 2 2 2 2 2 3 3 3
11121 1 1 1 1 1 1 1 1 2 2 2 2 2
11112 0 0 0 0 0 1 1 1 1 1 1 1 1
111111 1 1 1 1 1 1 1 1 1 1 1 1 1
Table 2. Matrix of Young-Fibonacci numbers for n = 6.
Theorem 4.4. Let n ≥ 2 be a positive integer, then the number of couples (u, v) of snakeshapes of
size n such that Nu, v = 0 is the (n− 2)
th Fibonacci number.
Proof. The proof is done by induction on n. Indeed using equation (4.2) it is easy to see that
Nu, v 6= 0 whenever u 6= 1
n−22. So the problem is equivalent to counting the number of snakeshapes
v such that N
= 0. But N
= 0 if and only if there exists a snakeshape w such that
v = 2w. Then the problem is finally equivalent to counting the snakeshapes of size (n − 2), and
hence the result. �
5. A weak order on Young-Fibonacci tableaux
In what follows, we introduce a partial and graded order denoted � on the set YFTn of Young-
Fibonacci tableaux of size n. We will see (Theorem 5.8) that this partial ordering on YFTn is such
that the map from the weak order on the symmetric group Sn which sends each permutation σ
onto its Young-Fibonacci insertion tableau P (σ) is order-preserving. More particularly, standard
Young-Fibonacci classes on Sn are intervals of the weak order on Sn. Recall that the weak or-
der on permutations of Sn is the transitive closure of the relation σ ≤p τ if τ = σδi for some
i, where δi is the adjacent transposition (i i+1). An inversion of a permutation σ is a couple
(j, i), 1 ≤ i < j ≤ n such that σ−1(i) > σ−1(j), that is to say j appears on the left of i in σ.
Note that this is not the definition commonly used . The set of inversions of a permutation σ will
be denoted inv(σ), and the number of inversions denoted #inv(σ). We will be making use of an
analogous notion of non-inversion of a permutation σ which is a couple (i, j), 1 ≤ i < j ≤ n such
that σ−1(i) < σ−1(j), that is to say i appears on the left of j in σ. The set of non-inversions of a
permutation σ will be denoted ord(σ).
Definition 5.1. To introduce �, we define the operation of shifting an entry in a tableau t as
follows.
(1) the bottom entry a of any column of t may move and bump up the entry c on its left if c
is a single-boxed column of t. In the example below, the letter 1 is the one being shifted.
2 4 3 1
shift the entry 1
−−−−−−−−−−−−−−−−→
2 4 1
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 11
(2) In the case a was the bottom entry in a two-boxed column, the top entry b will just fall
down. In the two examples below, the letter 2 (resp. 3) is the one being shifted.
5 2 3 1
shift 2
−−−−−−−−→
2 4 3 1
5 3 1
shift 3
−−−−−−−−→
3 4 1
(3) In the case the column just to the left of a is two-boxed, with bottom entry c and a < c,
then a may replace c which on its turn is shifted to the right in such a way that if c < b
then c will just replace a ; otherwise c is placed as a new single-boxed column between a
and b, and b just falls down. In the two examples below, the letter 1 (resp. 2) is shifted.
2 1 3
shift 1
−−−−−−−−→
1 2 3
4 2 1
shift 2
−−−−−−−−→
2 4 3 1
Remark 5.2. It easily follows from the definition that shifting an entry in a tableau always produces
a legitimate tableau of the same size. In an analogous way, given a tableau t, one defines the reverse
operation of finding all the tableaux t′ such that shifting an entry in t′ gives back t. For example,
one will check that
3 4 1
is obtained from
5 3 1
4 3 1
3 4 2 1
by shifting 3 or 1.
Finally it is clear that this operation is antisymmetric, that is to say if t′ is obtained from t by
shifting a given entry, then t cannot be obtained from t′ by shifting an entry.
The latter observation is enforced by the following lemma which also defines the graduation of
the poset (YFTn,�) we will soon introduce.
Lemma 5.3. Let t2 be a tableau obtained by shifting an entry in a tableau t1, and let σ1 (resp. σ2)
be the minimal permutation canonically associated to t1 (resp. t2) as stated in Lemma 2.10, then
the inversions sets of σ1 and σ2 are related by the relation #inv(σ2) = #inv(σ1) + 1.
Proof. The proof takes into account all the situations one can encounter in shifting an entry in t1.
(1) t1 = T2
c a T1 and t2 = T2
a ⋆T1, where T1 and T2 are partial YFT having minimal canonical
words w1 and w2 (see Lemma 2.10 for the definition), and ⋆ means any entry preserving the
conditions of Definition 2.1, and possibly no entry. The minimal permutations associated
to t1 and t2 are σ1 = w1⋆acw2 and σ2 = w1⋆caw2 respectively, and clearly σ2 has one more
inversion than σ1.
(2) t1 = T2
c a T1 and t2 = T2
a c ⋆ T1, with a < c < d ; one has σ1 = w1 ⋆adcw2 and σ2 =
w1⋆cdaw2. The inversion (dc) appears in σ1 but not in σ2, whereas the inversions (da) and
(ca) appear in σ2 but not in σ1 ; so σ2 has one more inversion.
(3) t1 = T2
c a T1 and t2 = T2
a c T1, with a < c < b < d ; one has σ1 = w1badcw2 and
σ2 = w1bcdaw2. The inversion (dc) appears in σ1 but not in σ2, whereas the inversions (da)
and (ca) appear in σ2 but not in σ1 ; so σ2 has one more inversion. �
We are now in position to provide YFTn with a structure of poset.
Definition 5.4 (weak order on YFTn). Let t and t
′ be two tableaux of size n, then t is said smaller
than t′ and we write t � t′ if one can find a sequence t0 = t, t1, · · · , tk = t
′ of tableaux of size n
such that ti+1 be obtained from ti by shifting an entry, for i from 0 to k − 1.
Proposition 5.5. (YFTn,�) is a graded poset, the rank of a Young-Fibonacci tableau being the
number of inversions of its minimal canonical permutation.
12 J. NZEUTCHAP
Proof. Follows from Lemma 5.3. �
Remark 5.6. Note that this remarkable property of graduation of the poset of standard Young-
Fibonacci tableaux of size n does not apply to the similar poset YTn of standard Young tableaux
of size n. The reader interested may refer to [9] where Taskin studied many nice properties of four
partial orders on YTn.
ρ = 6
ρ = 5
ρ = 4
ρ = 3
ρ = 2
ρ = 1
54321 ρ = 0
Figure 4. The graded weak order on Young-Fibonacci tableaux of size 5.
Remark 5.7. As one will easily check it on the figure above, (YFTn,�) is not a lattice for n = 5
for example. Indeed let a =
5421 and b =
3421, then a and b do not have a least upper bound.
Theorem 5.8. Let t1 and t2 be two tableaux, then t1 � t2 if and only if one can find two permu-
tations τ1 and τ2 such that P (τ1) = t1, P (τ2) = t2 and τ1 ≤p τ2.
Proof. It is enough to prove this statement for the case t2 is obtained by shifting an entry in t1,
and the proof is carried out as a parallel process of the proof of Lemma 5.3. So go back to the
latter proof and
(1) take τi = σi ;
(2) take τ1 = w1⋆dacw2 and τ2 = w1⋆dcaw2 ;
(3) take τ1 = w1bdacw2 and τ2 = w1bdcaw2.
This shows that one can find two permutations τ1 and τ2 such that P (τ1) = t1, P (τ2) = t2 and
τ2 = τ1δi for some i, whenever t1 � t2. Reciprocally let τ1 and τ2 be two permutations such that
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 13
P (τ1) = t1 and P (τ2) = t2 and τ2 = τ1δi for some i. Then t2 is obtained from t1 by shifting the
entry i in t1. �
We now look at the structure of the Young-Fibonacci classes ; below are two pictures of the
poset (YFT4,�). On the picture on the left, vertices are Young-Fibonacci classes corresponding to
Young-Fibonacci tableaux in the picture on the right. Recall that the rank of a class is the number
of inversions of its minimal element in the lexicographical order. The unique involution of any class
is enclosed in a rectangle. A double edge means that there are two couples (τ1, τ2) and (τ
satisfying the conditions of Theorem 5.8.
3241 ρ=4
3142 ρ=3
1342 ρ=2
2134 1324
1243 ρ=1
1234 ρ=0
1 3 2
4 1 2
2 3 1
4 3 1
4 2 1
3 2 1
4 3 2 1
Figure 5. The graded weak order on Young-Fibonacci classes of size 4.
It is easy to check that each class appearing as a vertex of the poset (YFT4,�) is an interval of
the weak order (S4,≤p), and this is a general observation.
Theorem 5.9. Let t be a standard Young-Fibonacci tableau of size n, then YFC(t) is an interval
of the weak order (Sn,≤p), more over YFC(t) = [w
min, w
max].
To prove this statement, we will first relate YFC(t) with linear extensions of a poset canonically
associated to t, and then we will prove that the set of linear extensions of this poset is an interval
of the weak order.
Definition 5.10. Let t be a standard Young-Fibonacci tableau of size n, its canonical poset Pt is
the poset defined on the set {1, 2, ..., n} with the covering relations below.
(1) the right-to-left reading of the bottom row of t forms a chain in the poset ;
(2) each entry on top in a two-boxed column of t is covered by the corresponding entry on
bottom row.
Note 5.11. A permutation σ is a toset (totally ordered set) with covering relations defined by
σ(i) ≤σ σ(j) whenever i < j, that is to say x ≤σ y if x appears to the left of y in σ. Let P be
a poset and σ a permutation, σ is said to be a linear extension of P if its relations preserve the
relations in P, that is to say if x ≤P y then x ≤σ y. The set of linear extensions of a poset P will
be denoted Ext(P).
14 J. NZEUTCHAP
Theorem 5.12. Let t be a standard Young-Fibonacci tableau, then YFC(t) = Ext(Pt).
Proof. That any permutation σ having t as insertion tableau is a linear extension of Pt is clear
from Definitions 2.4 and 5.10. Conversely, if σ is a linear extension of Pt, then t is naturally built
reading σ from right to left following the description given in Definition 2.4. At each new step the
first letter one reads is the maximal one (for ≤Pt) not yet read in the chain described in rule (1) of
Definition 5.10. �
Theorem 5.13. Let t be a standard YFT of size n, then Ext(Pt) is the interval [w
min, w
max] in
(Sn,≤p).
To prove this statement we make use of the following well known lemma.
Lemma 5.14. Let σ and τ be two permutations of Sn, then the three properties below are equivalent.
(1) σ ≤p τ ;
(2) ord(τ) ⊆ ord(σ) ;
(3) inv(σ) ⊆ inv(τ).
Proof. (of Theorem 5.13) It easily follows from the definition that Pt can be partitioned into an
antichain A = (y1, y2, · · · , yℓ) and a chain C = (x1 <Pt x2 <Pt · · · <Pt xk) such that for i = 1..ℓ
there exists j(i) ≤ k such that yi <Pt xj(i), and additionally for i1 < i2 one has yi1 < yi2 and
xj(i1) <Pt xj(i2). For illustrations, we use the following example.
A = (3, 6, 7)
C = (2 <Pt 5 <Pt 1 <Pt 4)
7 6 3
4 1 5 2
a tableau t
of shape u = 2212
its canonical posetPt
The set I is made of the inver-
sions below.
(3, 2), (6, 1), (7, 4)
(3, 1), (6, 4)
(2, 1), (5, 1), (5, 4).
The set O is made of the or-
dered pairs below.
(2, 5), (2, 4), (1, 4)
(3, 5), (3, 4).
For σ ∈ Ext(P), inv(σ) includes at least the set
(yi, xj(i)), i = 1..ℓ
(yi, xr) / xj(i) > xr and xj(i) <Pt xr
(xi, xj) / xi > xj and xi <Pt xj
which is nothing but inv(wtmin) ; so by [Lemma 5.14 - (3)], w
min ≤p σ. Moreover, ord(σ) includes
at least the set
O = { (yi, xr) / xj(i) <Pt xr } ∪ { (xi, xj) / xi < xj and xi <Pt xj }
which is nothing but ord(wtmax) ; so by [Lemma 5.14 - (2)], σ ≤p w
max and hence σ ∈ [w
min, w
max].
Conversely, for σ ∈ [wtmin, w
max], applying Lemma 5.14 to w
min, σ and w
max it appears that σ has
the inversions yi ≤σ xj(i) for i = 1..ℓ, and the relations x1 <σ x2 <σ · · · <σ xk. So P (σ) = t and
hence σ ∈ Ext(Pt). �
Proof. (of Theorem 5.9) Follows from Theorem 5.12 and Theorem 5.13. �
Definition 5.15. Let u be a snakeshape of size n, the row canonical tableau rTu is the one such
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 15
(1) top cells of rTu are labeled with entries n, n− 1, · · · from left to right ;
(2) bottom cells in two-boxed columns are labeled with entries 1, 2, · · · from left to right.
The column canonical tableau cTu is built by labeling the cells of u from right to left and bottom
to top.
Lemma 5.16. Let u be a snakeshape of size n, then cTu (resp. rTu) is the unique tableau of shape u
having minimal rank ρumin (resp. maximal rank ρ
max) in the poset (YFTn,�). For any snakeshape
u, ρumin is the number of double-boxed columns of u and ρ
max is obtained as follows. Label each
bottom cell with the number of double-boxed columns on its left and do the same but add 1 for each
top cell of double-boxed columns of u. ρumax is the sum of labels obtained.
ρ = 12 1̂
ρ = 11 •
7 6 4
1 2 5 3
• row canonical tableau
• • •
• • •
ρ = 3 • •
7 5 2
6 4 3 1
column canonical tableau
• • •
ρ = 0 0̂
Figure 6. Row canonical and column canonical tableaux of shape 2212.
Proof. (of Lemma 5.16) Easily from the definitions. �
We will now relate (YFTn,�) to a transition matrix in Okada’s algebra associated to YFL.
6. A connection with Okada’s algebra associated to the Young-Fibonacci lattice
A Young-Fibonacci analogue of the ring of symmetric functions [6] was given and studied by S.
Okada [16], with a Young-Fibonacci analogue of Kostka numbers, appearing when expressing the
analogue of a complete symmetric function hv in terms of the analogue of Schur functions su.
(6.1) hv =
Ku, v su
Young-Fibonacci analogue of Kostka numbers are generated by the recurrence formulas below
[16], where Ka, b is defined for two snakeshapes of the same weight and ✄ denotes the covering
relation in YFL.
(6.2)
K1u, 1v = Ku, v (r1)
K2u, 2v = Ku, v (r2)
K1u, 2v = 0 (r3)
K2u, 1v =
w✄uKw, v (r4)
As it is stated below, the hook-length formula for binary trees illustrated in Example 2.3 is an
alternative formula for computingKu, 1n = Fu which is the dimension of a representation in Okada’s
algebra.
Proposition 6.1. Let u be a snakeshape of size n, then Fu is the dimension of the module Vu
corresponding to u in the nth homogenous component of Okada’s algebra associated to YFL.
16 J. NZEUTCHAP
Proof. dim(Vu) is the number of saturated chains from ∅ to u in YFL, hence the result. �
Here is a more general statement giving a combinatorial interpretation of Ku, v using (YFTn,�).
Theorem 6.2. Let u and v be two snakeshapes of size n, and let 1̂ be the maximal tableau in
(YFTn,�), then Ku, v is the number of tableaux t of shape u in the interval [rTv, 1̂].
1 2 3
1 4 2
1 3 2
5 1 2
1 4 3 2
5 1 3 2
4 1 2
5 4 1 2
Example 6.3. In the matrix below, the number
Ku, 1121 counts the number of standard Young-
Fibonacci tableaux of shape u in the interval
[rT1121, 1̂].
221 212 2111 122 1211 1121 1112 15
221 1 1 2 1 2 3 4 8
212 . 1 1 1 1 1 3 4
2111 . . 1 . 1 1 1 4
122 . . . 1 1 1 2 3
1211 . . . . 1 1 1 3
1121 . . . . . 1 1 2
1112 . . . . . . 1 1
15 . . . . . . . 1
Iterating this for each snakeshape v of size n,
one builds the transition matrix for expressing
the analogue of complete symmetric function hv
in terms of the analogue of Schur functions su.
Figure 7. (YFT5,�) and Okada’s analogue of Kostka matrix for n = 5.
Proof. (of Theorem 6.2) A proof consists in showing that for any couple (a, b) of snakeshapes
appearing in the left hand side of equation (6.2), there is a one-to-one correspondence between
tableaux satisfying the conditions of the theorem for (a, b) and those satisfying the conditions of
the theorem for the couples of snakeshapes in the corresponding right hand side of the relation.
For (r1), given a tableau t of shape u such that rTv � t, t is mapped onto the tableau t
′ of shape
1u obtained from t by attaching a cell labeled n+1 to its left, and rT1v � t
′. For (r2), one attaches
a two-boxed column to the left of t, with 1 as bottom entry and n+2 as top entry, in addition one
standardizes t by increasing all its entries. Then t′ is of shape 2u and rT2v � t
′. For (r3) it easily
follows from the definition of the operation of shifting an entry in a tableau that there is no tableaux
t1 and t2 of shape 1u and 2v respectively, such that t2 � t1. For (r4), let t be a tableau of shape
2u such that rT1v � t, then t is mapped onto the tableau t
′ = ev(t, n), that is the tableau obtained
from t by evacuating its maximal letter (the evacuation process originally due to Killpatrick [8] is
described in Section 3.2). Indeed, let w be the shape of t′, then w ✄ u and rTv � t
7. Kostka numbers, the Littlewood Richardson rule, and four posets on Young
tableaux
The poset (YFTn,�) of Young-Fibonacci tableaux we defined in Section 5 is an analogue of
one among four partial orders on the set YTn of standard Young tableaux of size n [9]. The
weak order (YTn,�weak) is defined as in Theorem 5.8 with P (σ) denoting the Schensted insertion
tableau of σ. Let λ and µ be two partitions of lengths ℓ(λ) and ℓ(µ), λ is said greater than µ in
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 17
the dominance order and one writes λ ≥dom µ if for each 1 ≤ i ≤ min(ℓ(λ), ℓ(µ)), the inequality
λ1 + λ2 + · · · + λi ≥ µ1 + µ2 + · · · + µi holds. Let t be a standard Young tableau of size n, and
1 ≤ i ≤ j ≤ n. We denote λ(t/i,j) the shape of the tableau obtained from t by first restricting t to
the segment [i, j], then lowering all entries by i − 1, and finally sliding the skew tableau obtained
into normal shape by jeu-de-taquin. The chain order �chain on standard Young tableaux is defined
as follows.
Definition 7.1. [9] Let t and t′ be two standard Young tableaux of size n, then t �chain t
′ if and
only if for each 1 ≤ i ≤ j ≤ n, λ(t/i,j) ≥dom λ(t
The reader interested may refer to [9] for the definition of the two other orders, as well as for
the properties of those posets. The four posets happen to coincide up to rank n = 5.
12345
Figure 8. Partial order on Young tableaux of size 5.
Below is a Young tableaux analogue of Theorem 6.2.
Theorem 7.2. Let λ, µ be two partitions of size n, let rTµ be the row canonical standard Young
tableau of shape µ, that is to say rTµ has shape µ and is increasingly filled from let to right and
bottom to top. And let 0̂ be the minimal tableau in the poset of standard Young tableaux of size n.
Then Kλ, µ is the number of standard Young tableaux of shape λ in the interval [0̂, rTµ], for any one
of the posets studied in [9].
18 J. NZEUTCHAP
1 2 4
1 2 5
1 2 4
1 2 4 5
1 2 3 4
0̂ = 1 2 3 4 5
Example 7.3. In the matrix below, the num-
ber Kλ, 221 counts the number of standard Young
tableaux of shape λ in the interval [0̂, rT221].
µ = 5 41 32 311 221 2111 11111
λ = 5 1 1 1 1 1 1 1
41 . 1 1 2 2 3 4
32 . . 1 1 2 3 5
311 . . . 1 1 3 6
221 . . . . 1 2 5
2111 . . . . . 1 4
11111 . . . . . . 1
Iterating this for each partition µ of size n,
one builds the transition matrix for expressing
the complete symmetric function hµ in terms of
the Schur functions sλ.
Figure 9. Poset of Young tableaux and Kostka matrix for n = 5.
Proof. (of Theorem 7.2) For a given partition µ, let nscrt(µ) be the row canonical semi-standard
Young tableau of shape µ, that is the tableau filled with 1’s on its first line, 2’s on its second line
and so on. Let nsclt(n) be the semi-standard Young tableau of shape n and having µi entries i
for i = 1..ℓ(µ). Consider the extension of Definition 7.1 to the set Tab(µ) of semi-standard Young
tableaux having µi entries i for i = 1..ℓ(µ). Then for each t ∈ Tab(µ), one has nsclt(n) �chain
t �chain nscrt(µ). There is a canonical bijection mapping (Tab(µ),�chain) onto ([0̂, rTµ],�chain)
and this map is order preserving. So Theorem 7.2 holds for the partial order �chain. From ([9],
Theorem 1.1) and the remark that [0̂, rTµ] = rTµ1 ∗ rTµ2 ∗ · · · ∗ rTµℓ(µ) , it follows that the set of
tableaux in [0̂, rTµ] does not depend on the choice of the partial order. �
Concluding remarks and perspectives
There are quite many similarities between the Robinson-Schensted algorithm and the Young-
Fibonacci insertion algorithm. As well as between the combinatorics of Young tableaux and the
combinatorics of Young-Fibonacci tableaux. One of the questions we have not explored in this
paper is the one of the existence of an algebra of Young-Fibonacci tableaux, which would be an
analogue of the Poirier-Reutenauer Hopf algebra of Young tableaux [12]. Such an algebra would
certainly help in giving a combinatorial description (in terms of tableaux) of the product of Schur
functions in Okada’s algebra associated to the Young-Fibonacci lattice. We are currently looking
for a suitable definition of this algebra.
Acknowledgements
The author is grateful to F. Hivert for helpful comments and suggestions throughout this work.
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 19
References
[1] C. Schensted, Longest increasing and decreasing subsequences. Canad. J. Math., vol. 13, 1961, pp. 179-191.
[2] D. E. Knuth, Permutations, matrices and generalized Young tableaux, Pacific J. Math. 34(1970), 709–727.
[3] —, The art of computer programming, vol.3: Searching and sorting (Addison-Wesley, 1973).
[4] D. Krob and J.-Y. Thibon, Noncommutative symmetric function IV: Quantum linear groups and Hecke algebras
at q=0, J. Alg. Comb. 6 (1997), 339-376.
[5] F. Hivert, J. C. Novelli, and J.-Y. Thibon, The Algebra of Binary Search Trees, Theo. Comp. Science 339(2005),
129-165.
[6] I. G. MacDonald, Symmetric functions and Hall Polynomials, 2nd ed, Clarendon Press, Oxford Sce Publications,
139(1995).
[7] J. Nzeutchap, On the Young-Fibonacci Insertion Algorithm, to appear in the Proceedings of FPSAC’07.
[8] K. Killpatrick, Evacuation and a Geometric Consturction for Fibonacci Tableaux, J. Comb. Th, Ser A, 110
(2005), 337-351.
[9] M. Taskin, Properties of four partial orders on standard Young tableaux, J. Comb. Theory, Ser A, 113(2006),
1092-1119.
[10] R. P. Stanley, Differential Posets, J. Amer. Math. Soc. 1 (1998), 919-961.
[11] —, The Fibonacci lattice, Fibonacci Quarterly 13(1998), 215-232.
[12] S. Poirier and C. Reutenauer, Algèbre de Hopf des tableaux, Ann. Sci. Math. Qébec 19 (1995), 79-90.
[13] S. V. Fomin, Duality of Graded Graphs, J. Alg. Comb. 3(1994), 357-404.
[14] —, Generalized Robinson-Schensted-Knuth correspondence, Zapiski Nauchn. Sem. LOMI. 155 (1986), 156-175.
[15] —, Schensted Algorithms for Dual Graded Graphs, J. Alg. Comb. 4(1995), 5-45.
[16] S. Okada, Algebras associated to the Young-Fibonacci lattice, Trans AMS 346(1994), 549-568.
[17] T. Roby, Applications and extensions of Fomin’s generalization of the Robinson-Schensted correspondence to
differential posets, Ph.D. thesis, MIT, 1991.
LITIS EA 4051 (Laboratoire d’Informatique, de Traitement de l’Information et des Systèmes),
Avenue de l’Université, 76800 Saint Etienne du Rouvray, France
E-mail address: janvier.nzeutchap@univ-mlv.fr
URL: http://monge.univ-mlv.fr/∼nzeutcha
	1. Introduction
	1.1. The Young-Fibonacci lattice
	2. Young-Fibonacci tableaux and Young-Fibonacci insertion algorithm
	2.1. Converting a chain in YFL into a standard Young-Fibonacci tableau
	2.2. Redefining the Young-Fibonacci Insertion Algorithm
	3. Young-Fibonacci insertion and growth in differential posets
	3.1. Equivalence between Roby's and Fomin's constructions
	3.2. Another viewpoint of Killpatrick's evacuation for Young-Fibonacci tableaux
	4. Fibonacci numbers and a statistic on Young-Fibonacci tableaux
	5. A weak order on Young-Fibonacci tableaux
	6. A connection with Okada's algebra associated to the Young-Fibonacci lattice
	7. Kostka numbers, the Littlewood Richardson rule, and four posets on Young tableaux
	Concluding remarks and perspectives
	Acknowledgements
	References

  This work is concerned with some properties of the Young-Fibonacci insertion
algorithm and its relation with Fomin's growth diagrams. It also investigates a
relation between the combinatorics of Young-Fibonacci tableaux and the study of
Okada's algebra associated to the Young-Fibonacci lattice. The original
algorithm was introduced by Roby and we redefine it in such a way that both the
insertion and recording tableaux of any permutation are \emph{conveniently}
interpreted as chains in the Young-Fibonacci lattice. A property of
Killpatrick's evacuation is given a simpler proof, but this evacuation is no
longer needed in making Roby's and Fomin's constructions coincide. We provide
the set of Young-Fibonacci tableaux of size $n$ with a structure of graded
poset, induced by the weak order on permutations of the symmetric group, and
realized by transitive closure of elementary transformations on tableaux. We
show that this poset gives a combinatorial interpretation of the coefficients
in the transition matrix from the analogue of complete symmetric functions to
analogue of the Schur functions in Okada's algebra. We end with a quite similar
observation for four posets on Young-tableaux studied by Taskin.

Introduction 1
1.1. The Young-Fibonacci lattice 2
2. Young-Fibonacci tableaux and Young-Fibonacci insertion algorithm 3
2.1. Converting a chain in YFL into a standard Young-Fibonacci tableau 3
2.2. Redefining the Young-Fibonacci Insertion Algorithm 4
3. Young-Fibonacci insertion and growth in differential posets 6
3.1. Equivalence between Roby’s and Fomin’s constructions 7
3.2. Another viewpoint of Killpatrick’s evacuation for Young-Fibonacci tableaux 8
4. Fibonacci numbers and a statistic on Young-Fibonacci tableaux 9
5. A weak order on Young-Fibonacci tableaux 10
6. A connection with Okada’s algebra associated to the Young-Fibonacci lattice 15
7. Kostka numbers, the Littlewood Richardson rule, and four posets on Young tableaux 16
Concluding remarks and perspectives 18
Acknowledgements 18
References 19
1. Introduction
The Young lattice (YL) is defined on the set of partitions of positive integers, with covering
relations given by the natural inclusion order. The differential poset nature of this graph was
generalized by Fomin who introduced graph duality [13]. With this extension he introduced [15] a
generalization of the classical Robinson-Schensted-Knuth [1, 2] algorithm, giving a general scheme
for establishing bijective correspondences between couples of saturated chains in dual graded graphs,
both starting at a vertex of rank 0 and having a common end point of rank n, on the one hand,
and permutations of the symmetric group Sn on the other hand. This approach naturally leads to
the Robinson-Schensted insertion algorithm.
2000 Mathematics Subject Classification. Primary 05-06; Secondary 05E99.
Key words and phrases. Schensted-Fomin, insertion algorithm, Young-Fibonacci, lattice, tableaux, evacuation,
poset, Okada’s algebra, Kostka numbers.
http://arxiv.org/abs/0704.1969v1
2 J. NZEUTCHAP
Roby [17] gave an insertion algorithm analogous to the Schensted correspondence, which maps
a permutation σ onto a couple made of a Young-Fibonacci tableau P (σ) and a path tableau Q(σ).
Roby’s path tableau Q(σ) is canonically interpreted as a saturated chain in the Fibonacci lattice
Z(1) introduced by Stanley [11] and also by Fomin [14]. Roby also showed that Fomin’s approach
is partially equivalent to his construction.
Indeed in Roby’s construction, only the saturated chain Q̂ obtained from Fomin’s growth diagram
has an interpretation as a representation of the path tableau Q(σ), while there seems to be no way to
translate the Young-Fibonacci tableau P (σ) into its equivalent chain P̂ . Contrarily to the approach
of Killpatrick [8] who has used an evacuation to relate the two constructions of Roby and Fomin,
we show that with a suitable mechanism for converting a saturated chain in the Young-Fibonacci
lattice into a Young-Fibonacci tableau, Roby’s construction naturally coincides with Fomin’s one.
The paper is organized as follows. In Section 1.1 we recall the definition of the Young-Fibonacci
lattice, then in Section 2 we define a mechanism for converting a saturated chain in this lattice
into a standard Young-Fibonacci tableau. In the same section, we also introduce a modification in
Roby’s algorithm, in such a way that both the insertion and recording tableaux of any permutation
will have an interpretation in terms of saturated chain in the Young-Fibonacci lattice. In Section
3.1 we relate Roby’s algorithm with Fomin’s construction using growth diagrams and we compare it
to Killpatrick’s work. In Section 4, we define an analogue of Kostka numbers for Young-Fibonacci
tableaux, and we point out one of their relation with usual Fibonacci numbers. In Section 5 we
define and we study some properties of a poset on Young-Fibonacci tableaux. This poset turns
out to be a model for the interpretation as well as the computation of another analogue of Kostka
numbers, introduced by Okada [16] in an analogue of the algebra of symmetric functions, associated
to the Young-Fibonacci lattice. We prove this result is Section 6, and in the last section of the
paper we prove a similar result relating usual Kostka numbers with four posets on Young-tableaux
studied by Taskin [9].
1.1. The Young-Fibonacci lattice.
A Fibonacci diagram or snakeshape of size n is a column by column graphical representation of
a composition of an integer n, with parts equal to 1 or 2. The number of such compositions is the
nth Fibonacci number. A partial order is defined on the set of all snakeshapes, in such a way to
obtain an analogue of the Young lattice of partitions of integers (YL). This lattice is called the
Young-Fibonacci lattice (YFL) and it was introduced by Stanley [11] and also by Fomin [14]. As
we will see in the sequel, there is a considerable similarity between the two lattices, as well as the
combinatorics of tableaux their induce. The covering relations in YFL are given below, for any
snakeshape u.
(1) u is covered by the snakeshape obtained by attaching a single box just in front ;
(2) u is covered by the snakeshape obtained by adding a single box on top of its first single-boxed
column, reading u from left to right.
(3) if u starts with a series of two-boxed columns, then it is covered by all snakeshapes obtained
by inserting a single-boxed column just after any of those columns.
The rank |u| of a snakeshape u is the sum of digits of the corresponding Fibonacci word. Its
length will be denoted ℓ(u). Let u and v be two snakeshapes such that v covers u in YFL, the cell
added to u to obtain v is an inner corner of v, it is also called an outer corner of u.
Remark 1.1. Young-Fibonacci tableaux (YFT) will naturally appear as numberings of snake-
shapes, satisfying certain conditions described in the sequel, the same way as Young tableaux
are numberings of partitions of integers with prescribed numbering conditions. The numbering
conditions of Young-Fibonacci tableaux are deduced from the description of the Young-Fibonacci
insertion algorithm (Section 2.2).
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 3
Below is a pictorial representation of a finite realization of YFL, from rank 0 up to rank n = 4,
with black cells representing inner corners.
Figure 1. The Young-Fibonacci lattice.
Now let us look at the problem of converting a saturated chain in YFL into a standard YFT.
2. Young-Fibonacci tableaux and Young-Fibonacci insertion algorithm
In YL, any saturated chain starting at the empty partition can be canonically converted into a
standard Young tableau, and this representation is convenient in many ways. It consists in labeling
the boxes as their occur in the chain. As already observed by Roby [17], one question which presents
itself is to do the same in YFL for any saturated chain starting at the empty snakeshape ∅. The need
of such a conversion mechanism will appear in section 3.1 in the interpretation of two saturated
chains in a growth diagram.
One may also use the canonical labeling to convert a saturated chain of YFL into a tableau,
but Roby had already pointed out that one major problem with this canonical labeling is that
except for the trivial rule that each element in the top row must be greater than the one below it,
no other obvious rules govern what numberings are allowed for a given shape. We suggest that one
first defines simple rules governing what numberings are allowed for a given shape, so that it be
easy to decide if a numbering of a snakeshape is a legitimate Young-Fibonacci tableau or not. The
convention we use is described in the next section.
2.1. Converting a chain in YFL into a standard Young-Fibonacci tableau.
Since we do not use the same conventions as Roby [17] and Fomin [13], let us give the following
definition of Young-Fibonacci tableaux.
Definition 2.1. A numbering of a snakeshape with distinct nonnegative integers is a standard
Young-Fibonacci tableau (SYFT) under the following conditions.
(1) entries are strictly increasing in columns ;
(2) any entry on top in any column has no entry greater than itself on its right.
To convert a chain in YFL into a standard YFT, one will follow the canonical approach as
far as the new box added to the chain lies in the first column. Example with the chain Q̂ =
(∅, 1, 2, 12, 22, 221, 2211, 21211) ; the sub-chain (∅, 1, 2, 12, 22) is converted as follows.
∅ → 1 →
4 J. NZEUTCHAP
Now moving from the shape 22 to the shape 221 in YFL, one inserts a box just after a two-boxed
column of the previous shape. In such a situation, one will move the entry on top in that column
into the newly created box, and then shift the other entries of the top row to the right. Finally, if
n is the largest entry in the partial tableau obtained, then label the box on top in the first column
with (n + 1).
The conversion started above keeps on as follows, xk means that writing or moving the label x
is the kth action performed during the current step.
22 → 221 :
3 1 21
3 1 2
3 1 2
221 → 2211 :
3 1 2
3 1 2
3 1 41 2
3 1 4 2
3 1 4 2
2211 → 21211 :
3 1 4 2
3 1 4 2
3 61 1 4 2
3 6 1 4 2
It easily follows from the description above that this mechanism produces only legitimate YFT
(Definition 2.1), and that the conversion is reversible. Now another question which presents itself
is how to count standard YFT of a given shape u 6= ∅, we denote this number by Fu. Let us first
recall the formula counting linear extensions of a binary tree poset P.
(2.1) |Ext(P)| =
d1d2 · · · dn
where for the ith node vi, di is the number of nodes v ≤P vi. This formula is due to Knuth [3], and
since any snakeshape u can be canonically assimilated to a poset Pu, then we have the following.
Proposition 2.2. Standard Young-Fibonacci tableaux of a given shape are counted by the hook-
length formula for binary trees.
To apply the formula to a snakeshape u, count it cells from right to left and from bottom to top,
labeling the first box and each box appearing in the bottom row of any two-boxed column. The
number of standard YFT of the given shape is the product of all the labels obtained.
Example 2.3. Let us consider u = 2212.
a snakeshape
u = 2212
its poset Pu
hook lengths
6 4 1
F2212 =
2×3×5×7
= 6× 4× 1
2.2. Redefining the Young-Fibonacci Insertion Algorithm.
We refer the reader to [17, 8] for a description of the original algorithm ; below is the one we
consider.
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 5
Definition 2.4. The Young-Fibonacci insertion algorithm maps a permutation σ onto a couple of
standard YFT built as follows. The insertion tableau P (σ) is built by reading σ from right to left,
matching any of the letters encountered (and not yet matched) with the maximal one (not yet
matched) on its left if any, provided that the latter be greater than the first. The recording tableau
Q(σ) records the positions of the letters, in the reverse order of the one in which they are matched.
Example 2.5. For σ = 2715643, we have the following.
2 7 1 5 6 4 3
1 2 3 4 5 6 7
• P (σ) =
7 6 2
3 4 5 1
and Q(σ) =
7 6 3
2 5 4 1
Remark 2.6. That both P (σ) and Q(σ) are standard Young-Fibonacci tableaux (Definition 2.1)
is clear from the description of the algorithm. This is not the case in the original algorithm where
P (σ) and Q(σ) are not of the same type. Indeed, with the original insertion algorithm, the insertion
tableau is the same as the tableau P (σ) above, but the recording tableau Q(σ) which follows does
not satisfy Definition 2.1.
QRoby(σ) =
3 7 4
2 6 5 1
The definition of Q(σ) we adopt is inspired from the hypoplactic [4] and sylvester [5] insertion
algorithms, where Q(σ) also records the positions in σ of the labels of P (σ). With this definition,
some essential properties of the Young-Fibonacci correspondence have a much easier combinatorial
proof, which is not always the case in [17]. For example, let us recall the involution property.
Theorem 2.7. [17] For any permutation σ, P (σ−1) = Q(σ).
Proof. Consider the geometric construction by Killpatrick [8], and recall that P (σ) corresponds to
reading vertical coordinates of the rightmost and uppermost x in that order, for any broken line. As
for Q(σ), we have defined it in such a way that it corresponds to reading horizontal coordinates of
the uppermost and rightmost x in that order. The construction for σ−1 is obtained by transposing
the one for σ. �
Another fundamental property of Roby’s algorithm which is easily proved using Definition 2.4
follows.
Theorem 2.8. [17] Let σ be an involution of the symmetric group, then the cycle decomposition
of σ is the column reading of its insertion tableau P (σ).
We give two other canonical words associated with a tableau t ; so if we let YFC(t) denotes
the equivalence class made of permutations having t as insertion tableau, then YFC(t) has at least
three canonical elements. The first canonical element is its canonical involution, that is the only
involution the cycles of which coincide with the columns of t, as stated in Theorem 2.8. The two
other canonical elements are the maximal (resp. minimal) element for the lexicographical order.
We will make use of these elements in Section 5.
Lemma 2.9. Let t be a Young-Fibonacci tableau, w1 the left-to-right reading of its top row and w2
the right-to-left reading of its bottom row, then w1.w2 (where . denotes the usual concatenation of
words) is the maximal element (for the lexicographical order) of YFC(t), it is denoted wtmax.
Lemma 2.10. The word consisting of the right-to-left and up-down column reading of t is the
minimal element (for the lexicographical order) of YFC(t), it is denoted wtmin.
Proof. Clear from the description of the Young-Fibonacci insertion algorithm. �
6 J. NZEUTCHAP
An example is given with the tableau t below ; its canonical involution is (13)(26)(48)(5)(7) =
36185274, the maximal canonical element is 86315274, and the minimal one is 31562784.
8 6 3
4 7 2 5 1
We will see (Theorem 5.12) that YFC(t) is the set of linear extensions of a given poset, and
additionally, YFC(t) is an interval of the weak order on the symmetric group (Theorem 5.9).
3. Young-Fibonacci insertion and growth in differential posets
In this section we show that with the modification we have introduced in Roby’s original insertion
algorithm, together with the conversion mechanism discussed in section 2.1, the Young-Fibonacci
insertion algorithm naturally coincides with Fomin’s approach using growth diagrams. So we claim
that Killpatrick’s evacuation [8] is no longer needed in making the two constructions coincide. We
give a simplification of Killpatrick’s theorem relating Roby’s original algorithm to Fomin’s one
through an evacuation process, and we will later need this evacuation in the proof of Theorem 6.2
giving a combinatorial interpretation of Okada’s analogue of Kostka numbers.
Let us recall that Fomin’s construction with growth diagrams consists in using some local rules
in filling a diagram giving rise to a pair of saturated chains in YL. For any permutation σ, the
growth diagram d(σ) is build the following way. First draw the permutation matrix of σ ; next fill
the left and lower boundary of d(σ) with the empty snakeshape ∅. The rest of the construction is
iterative ; d(σ) is filled from the lower left corner to the upper right corner, following the diagonal.
At each step and for any configuration as pictured below, z is obtained by applying the local rules
to the vertices t, x, y and the permutation matrix element α. We refer the reader to [15] for more
details on this construction.
a1 α b1
Figure 2. A square in a growth diagram.
Algorithm 1 : local rules for YFL
1: if x 6= y and y 6= t then
2: z := t, with a two-boxed column added in front
3: else
4: if x = y = t and α = 1 then
5: z := t, with a single-boxed column added in front
6: else
7: z is defined in such a way that the edge bi is degenerated whenever ai is degenerated
8: end if
9: end if
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 7
3.1. Equivalence between Roby’s and Fomin’s constructions.
Let us build Fomin’s growth diagram for the permutation σ = 2715643.
∅ � �� ���
∅ � � ��
∅ � � ��
∅ � � ��
∅ � � ��
∅ � � �
∅ ∅ ∅ � � � � �
∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅
Figure 3. Example of growth diagram for the Young-Fibonacci insertion.
We get the paths Q̂ = (∅, 1, 2, 12, 22, 221, 2211, 21211) and P̂ = (∅, 1, 11, 21, 211, 1211, 2211, 21211)
on the upper and right boundary respectively. Now let us convert them into Young-Fibonacci
tableaux, using the mechanism discussed in section 2.1.
∅ → 1 → 2 1 →
2 4 1
2 5 4 1
7 6 3
2 5 4 1
= Q̂(σ) = Q(σ)
∅ → 1 →
3 4 1
6 5 2
3 4 1
7 6 2
3 4 5 1
= P̂ (σ) = P (σ)
So as we can see on this example, the two constructions naturally coincide.
Remark 3.1. Let us mention that because Roby used the canonical labeling to convert a chain
into a tableau, there seemed to be no way to convert the chain P̂ into its equivalent tableau P (σ).
Killpatrick’s algorithm was then an approach to relate P̂ with P (σ). Our own approach consists
in the introduction of a modification of the original algorithm, and a new labeling process.
Theorem 3.2. Let (P̂ (σ), Q̂(σ)) be the pair of Young-Fibonacci tableaux obtained from the permu-
tation σ by using Fomin’s growth diagram and let (P (σ), Q(σ)) be the Young-Fibonacci insertion
and recording tableaux using Roby’s insertion modified (Definition 2.4), then P̂ (σ) = P (σ) and
Q̂(σ) = Q(σ).
Proof. The equality P̂ (σ) = P (σ) follows from that any snakeshape P̂k appearing in P̂ is the shape
of the tableau P (σ/[1..k]) where σ/[1..k] is the restriction of σ to the interval [1..k]. Indeed, the path
P̂ is obtained applying to P (σ) the reverse process of the one described in section 2.1. In so doing,
the cell added to P̂k to get P̂k+1 lies in the first column when either σ/[1..k+1] ends with the letter
k + 1 or σ/[1..k+1] does not end with the letter k + 1 but σ/[1..k] ends with the letter k. A quite
similar reasoning is used to prove the equality Q̂(σ) = Q(σ). �
8 J. NZEUTCHAP
3.2. Another viewpoint of Killpatrick’s evacuation for Young-Fibonacci tableaux.
For a tableau t, this operation is defined only for top entries of the columns of t. Let a0 be such
an entry, the tableau resulting from the evacuation of a0 is denoted ev(t, a0) and is built as follows.
(1) if a0 is a single-boxed column, then just delete this column and, if this is necessary, shift
one component of the remaining tableau to connect it with the other one (e.g of line 3 in
the table below) ;
(2) otherwise, the box containing a0 is emptied and one compares the entry a1 that was just
below a0 with the entry a2 on top of the column just to the right if any. If a2 < a1 then
this terminates the evacuation process (e.g of line 4 in the table below). Otherwise, move
a2 on top of a1, creating a new empty box in the tableau. If the new empty box is a
single-boxed column, then this terminates the evacuation process (e.g of line 7, step 4, in
the table below), otherwise, iteratively repeat the process with the entries just below and
to the right of this new empty box.
Let t be a tableau of size n and shape u. If one successively evacuates the entries n, (n−1), · · · , 1
from t, labeling the boxes of u according to the positions of the empty cells at the end of the
evacuation of entries, one gets a path tableau denoted ev(t). Recall that a path tableau is the
canonical labeling of a saturated chain.
Remark 3.3. ev(t) is the same tableau as the one described by Killpatrick [8], with Young-
Fibonacci tableaux defined as in Definition 2.1.
7 t =
7 6 2
3 4 5 1
• 6 2
3 4 5 1
6 • 2
3 4 5 1
6 5 2
3 4 • 1 7
6 5 2
3 4 1
• 5 2
3 4 1
5 • 2
3 4 1
3 4 1
3 4 1
3 • 1
3 5 7
4 6 2
3 5 7
1 1 → • ev(t) =
4 6 2
3 5 7 1
Table 1. Evacuation on Young-Fibonacci tableaux.
Lemma 3.4. Let w be a word with no letter repeated, let a0 be one of its letters appearing as a
top element in a column of P (w), and let w0 be the word obtained from w by deleting the only
occurrence of a0, then ev(P (w), a0) = P (w0).
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 9
Proof. Easily from the description of the evacuation and the description of the Young-Fibonacci
insertion algorithm (Definition 2.4). �
We give a simpler proof of the following theorem by Killpatrick, relating ev(P (σ)) with P̂ .
Indeed, using the canonical labeling, Roby has converted the path P̂ into a path tableau P̂ (σ) and
Theorem 3.5. [8] ev(P (σ)) = P̂ (σ).
Proof. Follows from Lemma 3.4 and the remark that any snakeshape P̂k appearing in P̂ is the
shape of the tableau P (σ/[1..k]) where σ/[1..k] is the restriction of σ to the interval [1..k]. �
4. Fibonacci numbers and a statistic on Young-Fibonacci tableaux
In this section we point out a property of Young-Fibonacci numbers defined as an analogue of
Kostka numbers. Recall that the usual Kostka numbers Kλ, µ are defined for two partitions λ and µ
of the same integer n and they appear when expressing Schur functions sλ in terms of the monomial
symmetric functions mµ, and in the expression of the complete symmetric functions hµ in terms of
Schur functions sλ.
(4.1) sλ =
Kλ, µmµ ; hµ =
Kλ, µ sλ
We will not focus on the algebraic interpretation of the Kλ, µ but rather on their combinatorial
interpretation in terms of tableaux. Indeed, Kλ, µ counts the number of distinct semi-standard
Young-tableaux of shape λ and valuation µ, that is to say with µi entries i for i = 1 .. ℓ(µ). It is
then natural to introduce the same definition with Young-Fibonacci tableaux.
Definition 4.1. A semi-standard Young-Fibonacci tableau is a numbering of a snakeshape with
nonnegative integers, not necessarily distinct, preserving the conditions stated in Definition 2.1.
Definition 4.2. Let u and v be two snakeshapes of size n, the Young-Fibonacci number associated
to u and v, denoted Nu, v is the number of distinct semi-standard Young-Fibonacci tableaux of
shape u and valuation v, that is to say with vi entries i for i = 1 .. ℓ(v).
For example, for u = 221 and v = 1211, there are 4 distinct semi-standard Young-Fibonacci
tableaux of shape u and valuation v. So N221, 1211 = 4.
1 2 2
2 1 2
2 2 1
3 1 2
Proposition 4.3. Young-Fibonacci numbers are generated by the recurrence formulas below, where
both u and v are snakeshapes.
(4.2)
N∅, ∅ = 1 ; N2, 2 = 0
N1u, v1 = Nu, v ; N1u, v2 = Nu, v1
N2u, v1 =
w∈ v1
− Nu,w ; N2u, v2 =
w∈ v1
− Nu, w1
where v1
denotes the multiset of snakeshapes obtained from v either by deleting a single occurrence
of 1, or by decreasing a single entry not equal to 1, for example 21121
= [1112, 212, 212, 2111].
Proof. Easily from the definition of Young-Fibonacci tableaux and Young-Fibonacci numbers. �
10 J. NZEUTCHAP
v = 222 2211 2121 2112 21111 1221 1212 12111 1122 11211 11121 11112 111111
u = 222 2 3 4 5 6 4 5 6 5 7 8 12 15
2211 4 5 5 7 9 5 7 9 7 9 9 12 15
2121 2 3 4 4 5 4 4 5 4 6 8 8 10
2112 1 1 1 1 1 2 2 3 3 4 4 4 5
21111 2 3 3 3 4 3 3 4 3 4 4 4 5
1221 2 2 3 4 4 3 4 4 4 4 6 8 8
1212 1 1 1 1 1 1 2 2 3 3 3 4 4
12111 2 2 2 3 3 2 3 3 3 3 3 4 4
1122 1 1 1 1 1 1 1 1 2 2 3 3 3
11211 1 1 2 2 2 2 2 2 2 2 3 3 3
11121 1 1 1 1 1 1 1 1 2 2 2 2 2
11112 0 0 0 0 0 1 1 1 1 1 1 1 1
111111 1 1 1 1 1 1 1 1 1 1 1 1 1
Table 2. Matrix of Young-Fibonacci numbers for n = 6.
Theorem 4.4. Let n ≥ 2 be a positive integer, then the number of couples (u, v) of snakeshapes of
size n such that Nu, v = 0 is the (n− 2)
th Fibonacci number.
Proof. The proof is done by induction on n. Indeed using equation (4.2) it is easy to see that
Nu, v 6= 0 whenever u 6= 1
n−22. So the problem is equivalent to counting the number of snakeshapes
v such that N
= 0. But N
= 0 if and only if there exists a snakeshape w such that
v = 2w. Then the problem is finally equivalent to counting the snakeshapes of size (n − 2), and
hence the result. �
5. A weak order on Young-Fibonacci tableaux
In what follows, we introduce a partial and graded order denoted � on the set YFTn of Young-
Fibonacci tableaux of size n. We will see (Theorem 5.8) that this partial ordering on YFTn is such
that the map from the weak order on the symmetric group Sn which sends each permutation σ
onto its Young-Fibonacci insertion tableau P (σ) is order-preserving. More particularly, standard
Young-Fibonacci classes on Sn are intervals of the weak order on Sn. Recall that the weak or-
der on permutations of Sn is the transitive closure of the relation σ ≤p τ if τ = σδi for some
i, where δi is the adjacent transposition (i i+1). An inversion of a permutation σ is a couple
(j, i), 1 ≤ i < j ≤ n such that σ−1(i) > σ−1(j), that is to say j appears on the left of i in σ.
Note that this is not the definition commonly used . The set of inversions of a permutation σ will
be denoted inv(σ), and the number of inversions denoted #inv(σ). We will be making use of an
analogous notion of non-inversion of a permutation σ which is a couple (i, j), 1 ≤ i < j ≤ n such
that σ−1(i) < σ−1(j), that is to say i appears on the left of j in σ. The set of non-inversions of a
permutation σ will be denoted ord(σ).
Definition 5.1. To introduce �, we define the operation of shifting an entry in a tableau t as
follows.
(1) the bottom entry a of any column of t may move and bump up the entry c on its left if c
is a single-boxed column of t. In the example below, the letter 1 is the one being shifted.
2 4 3 1
shift the entry 1
−−−−−−−−−−−−−−−−→
2 4 1
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 11
(2) In the case a was the bottom entry in a two-boxed column, the top entry b will just fall
down. In the two examples below, the letter 2 (resp. 3) is the one being shifted.
5 2 3 1
shift 2
−−−−−−−−→
2 4 3 1
5 3 1
shift 3
−−−−−−−−→
3 4 1
(3) In the case the column just to the left of a is two-boxed, with bottom entry c and a < c,
then a may replace c which on its turn is shifted to the right in such a way that if c < b
then c will just replace a ; otherwise c is placed as a new single-boxed column between a
and b, and b just falls down. In the two examples below, the letter 1 (resp. 2) is shifted.
2 1 3
shift 1
−−−−−−−−→
1 2 3
4 2 1
shift 2
−−−−−−−−→
2 4 3 1
Remark 5.2. It easily follows from the definition that shifting an entry in a tableau always produces
a legitimate tableau of the same size. In an analogous way, given a tableau t, one defines the reverse
operation of finding all the tableaux t′ such that shifting an entry in t′ gives back t. For example,
one will check that
3 4 1
is obtained from
5 3 1
4 3 1
3 4 2 1
by shifting 3 or 1.
Finally it is clear that this operation is antisymmetric, that is to say if t′ is obtained from t by
shifting a given entry, then t cannot be obtained from t′ by shifting an entry.
The latter observation is enforced by the following lemma which also defines the graduation of
the poset (YFTn,�) we will soon introduce.
Lemma 5.3. Let t2 be a tableau obtained by shifting an entry in a tableau t1, and let σ1 (resp. σ2)
be the minimal permutation canonically associated to t1 (resp. t2) as stated in Lemma 2.10, then
the inversions sets of σ1 and σ2 are related by the relation #inv(σ2) = #inv(σ1) + 1.
Proof. The proof takes into account all the situations one can encounter in shifting an entry in t1.
(1) t1 = T2
c a T1 and t2 = T2
a ⋆T1, where T1 and T2 are partial YFT having minimal canonical
words w1 and w2 (see Lemma 2.10 for the definition), and ⋆ means any entry preserving the
conditions of Definition 2.1, and possibly no entry. The minimal permutations associated
to t1 and t2 are σ1 = w1⋆acw2 and σ2 = w1⋆caw2 respectively, and clearly σ2 has one more
inversion than σ1.
(2) t1 = T2
c a T1 and t2 = T2
a c ⋆ T1, with a < c < d ; one has σ1 = w1 ⋆adcw2 and σ2 =
w1⋆cdaw2. The inversion (dc) appears in σ1 but not in σ2, whereas the inversions (da) and
(ca) appear in σ2 but not in σ1 ; so σ2 has one more inversion.
(3) t1 = T2
c a T1 and t2 = T2
a c T1, with a < c < b < d ; one has σ1 = w1badcw2 and
σ2 = w1bcdaw2. The inversion (dc) appears in σ1 but not in σ2, whereas the inversions (da)
and (ca) appear in σ2 but not in σ1 ; so σ2 has one more inversion. �
We are now in position to provide YFTn with a structure of poset.
Definition 5.4 (weak order on YFTn). Let t and t
′ be two tableaux of size n, then t is said smaller
than t′ and we write t � t′ if one can find a sequence t0 = t, t1, · · · , tk = t
′ of tableaux of size n
such that ti+1 be obtained from ti by shifting an entry, for i from 0 to k − 1.
Proposition 5.5. (YFTn,�) is a graded poset, the rank of a Young-Fibonacci tableau being the
number of inversions of its minimal canonical permutation.
12 J. NZEUTCHAP
Proof. Follows from Lemma 5.3. �
Remark 5.6. Note that this remarkable property of graduation of the poset of standard Young-
Fibonacci tableaux of size n does not apply to the similar poset YTn of standard Young tableaux
of size n. The reader interested may refer to [9] where Taskin studied many nice properties of four
partial orders on YTn.
ρ = 6
ρ = 5
ρ = 4
ρ = 3
ρ = 2
ρ = 1
54321 ρ = 0
Figure 4. The graded weak order on Young-Fibonacci tableaux of size 5.
Remark 5.7. As one will easily check it on the figure above, (YFTn,�) is not a lattice for n = 5
for example. Indeed let a =
5421 and b =
3421, then a and b do not have a least upper bound.
Theorem 5.8. Let t1 and t2 be two tableaux, then t1 � t2 if and only if one can find two permu-
tations τ1 and τ2 such that P (τ1) = t1, P (τ2) = t2 and τ1 ≤p τ2.
Proof. It is enough to prove this statement for the case t2 is obtained by shifting an entry in t1,
and the proof is carried out as a parallel process of the proof of Lemma 5.3. So go back to the
latter proof and
(1) take τi = σi ;
(2) take τ1 = w1⋆dacw2 and τ2 = w1⋆dcaw2 ;
(3) take τ1 = w1bdacw2 and τ2 = w1bdcaw2.
This shows that one can find two permutations τ1 and τ2 such that P (τ1) = t1, P (τ2) = t2 and
τ2 = τ1δi for some i, whenever t1 � t2. Reciprocally let τ1 and τ2 be two permutations such that
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 13
P (τ1) = t1 and P (τ2) = t2 and τ2 = τ1δi for some i. Then t2 is obtained from t1 by shifting the
entry i in t1. �
We now look at the structure of the Young-Fibonacci classes ; below are two pictures of the
poset (YFT4,�). On the picture on the left, vertices are Young-Fibonacci classes corresponding to
Young-Fibonacci tableaux in the picture on the right. Recall that the rank of a class is the number
of inversions of its minimal element in the lexicographical order. The unique involution of any class
is enclosed in a rectangle. A double edge means that there are two couples (τ1, τ2) and (τ
satisfying the conditions of Theorem 5.8.
3241 ρ=4
3142 ρ=3
1342 ρ=2
2134 1324
1243 ρ=1
1234 ρ=0
1 3 2
4 1 2
2 3 1
4 3 1
4 2 1
3 2 1
4 3 2 1
Figure 5. The graded weak order on Young-Fibonacci classes of size 4.
It is easy to check that each class appearing as a vertex of the poset (YFT4,�) is an interval of
the weak order (S4,≤p), and this is a general observation.
Theorem 5.9. Let t be a standard Young-Fibonacci tableau of size n, then YFC(t) is an interval
of the weak order (Sn,≤p), more over YFC(t) = [w
min, w
max].
To prove this statement, we will first relate YFC(t) with linear extensions of a poset canonically
associated to t, and then we will prove that the set of linear extensions of this poset is an interval
of the weak order.
Definition 5.10. Let t be a standard Young-Fibonacci tableau of size n, its canonical poset Pt is
the poset defined on the set {1, 2, ..., n} with the covering relations below.
(1) the right-to-left reading of the bottom row of t forms a chain in the poset ;
(2) each entry on top in a two-boxed column of t is covered by the corresponding entry on
bottom row.
Note 5.11. A permutation σ is a toset (totally ordered set) with covering relations defined by
σ(i) ≤σ σ(j) whenever i < j, that is to say x ≤σ y if x appears to the left of y in σ. Let P be
a poset and σ a permutation, σ is said to be a linear extension of P if its relations preserve the
relations in P, that is to say if x ≤P y then x ≤σ y. The set of linear extensions of a poset P will
be denoted Ext(P).
14 J. NZEUTCHAP
Theorem 5.12. Let t be a standard Young-Fibonacci tableau, then YFC(t) = Ext(Pt).
Proof. That any permutation σ having t as insertion tableau is a linear extension of Pt is clear
from Definitions 2.4 and 5.10. Conversely, if σ is a linear extension of Pt, then t is naturally built
reading σ from right to left following the description given in Definition 2.4. At each new step the
first letter one reads is the maximal one (for ≤Pt) not yet read in the chain described in rule (1) of
Definition 5.10. �
Theorem 5.13. Let t be a standard YFT of size n, then Ext(Pt) is the interval [w
min, w
max] in
(Sn,≤p).
To prove this statement we make use of the following well known lemma.
Lemma 5.14. Let σ and τ be two permutations of Sn, then the three properties below are equivalent.
(1) σ ≤p τ ;
(2) ord(τ) ⊆ ord(σ) ;
(3) inv(σ) ⊆ inv(τ).
Proof. (of Theorem 5.13) It easily follows from the definition that Pt can be partitioned into an
antichain A = (y1, y2, · · · , yℓ) and a chain C = (x1 <Pt x2 <Pt · · · <Pt xk) such that for i = 1..ℓ
there exists j(i) ≤ k such that yi <Pt xj(i), and additionally for i1 < i2 one has yi1 < yi2 and
xj(i1) <Pt xj(i2). For illustrations, we use the following example.
A = (3, 6, 7)
C = (2 <Pt 5 <Pt 1 <Pt 4)
7 6 3
4 1 5 2
a tableau t
of shape u = 2212
its canonical posetPt
The set I is made of the inver-
sions below.
(3, 2), (6, 1), (7, 4)
(3, 1), (6, 4)
(2, 1), (5, 1), (5, 4).
The set O is made of the or-
dered pairs below.
(2, 5), (2, 4), (1, 4)
(3, 5), (3, 4).
For σ ∈ Ext(P), inv(σ) includes at least the set
(yi, xj(i)), i = 1..ℓ
(yi, xr) / xj(i) > xr and xj(i) <Pt xr
(xi, xj) / xi > xj and xi <Pt xj
which is nothing but inv(wtmin) ; so by [Lemma 5.14 - (3)], w
min ≤p σ. Moreover, ord(σ) includes
at least the set
O = { (yi, xr) / xj(i) <Pt xr } ∪ { (xi, xj) / xi < xj and xi <Pt xj }
which is nothing but ord(wtmax) ; so by [Lemma 5.14 - (2)], σ ≤p w
max and hence σ ∈ [w
min, w
max].
Conversely, for σ ∈ [wtmin, w
max], applying Lemma 5.14 to w
min, σ and w
max it appears that σ has
the inversions yi ≤σ xj(i) for i = 1..ℓ, and the relations x1 <σ x2 <σ · · · <σ xk. So P (σ) = t and
hence σ ∈ Ext(Pt). �
Proof. (of Theorem 5.9) Follows from Theorem 5.12 and Theorem 5.13. �
Definition 5.15. Let u be a snakeshape of size n, the row canonical tableau rTu is the one such
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 15
(1) top cells of rTu are labeled with entries n, n− 1, · · · from left to right ;
(2) bottom cells in two-boxed columns are labeled with entries 1, 2, · · · from left to right.
The column canonical tableau cTu is built by labeling the cells of u from right to left and bottom
to top.
Lemma 5.16. Let u be a snakeshape of size n, then cTu (resp. rTu) is the unique tableau of shape u
having minimal rank ρumin (resp. maximal rank ρ
max) in the poset (YFTn,�). For any snakeshape
u, ρumin is the number of double-boxed columns of u and ρ
max is obtained as follows. Label each
bottom cell with the number of double-boxed columns on its left and do the same but add 1 for each
top cell of double-boxed columns of u. ρumax is the sum of labels obtained.
ρ = 12 1̂
ρ = 11 •
7 6 4
1 2 5 3
• row canonical tableau
• • •
• • •
ρ = 3 • •
7 5 2
6 4 3 1
column canonical tableau
• • •
ρ = 0 0̂
Figure 6. Row canonical and column canonical tableaux of shape 2212.
Proof. (of Lemma 5.16) Easily from the definitions. �
We will now relate (YFTn,�) to a transition matrix in Okada’s algebra associated to YFL.
6. A connection with Okada’s algebra associated to the Young-Fibonacci lattice
A Young-Fibonacci analogue of the ring of symmetric functions [6] was given and studied by S.
Okada [16], with a Young-Fibonacci analogue of Kostka numbers, appearing when expressing the
analogue of a complete symmetric function hv in terms of the analogue of Schur functions su.
(6.1) hv =
Ku, v su
Young-Fibonacci analogue of Kostka numbers are generated by the recurrence formulas below
[16], where Ka, b is defined for two snakeshapes of the same weight and ✄ denotes the covering
relation in YFL.
(6.2)
K1u, 1v = Ku, v (r1)
K2u, 2v = Ku, v (r2)
K1u, 2v = 0 (r3)
K2u, 1v =
w✄uKw, v (r4)
As it is stated below, the hook-length formula for binary trees illustrated in Example 2.3 is an
alternative formula for computingKu, 1n = Fu which is the dimension of a representation in Okada’s
algebra.
Proposition 6.1. Let u be a snakeshape of size n, then Fu is the dimension of the module Vu
corresponding to u in the nth homogenous component of Okada’s algebra associated to YFL.
16 J. NZEUTCHAP
Proof. dim(Vu) is the number of saturated chains from ∅ to u in YFL, hence the result. �
Here is a more general statement giving a combinatorial interpretation of Ku, v using (YFTn,�).
Theorem 6.2. Let u and v be two snakeshapes of size n, and let 1̂ be the maximal tableau in
(YFTn,�), then Ku, v is the number of tableaux t of shape u in the interval [rTv, 1̂].
1 2 3
1 4 2
1 3 2
5 1 2
1 4 3 2
5 1 3 2
4 1 2
5 4 1 2
Example 6.3. In the matrix below, the number
Ku, 1121 counts the number of standard Young-
Fibonacci tableaux of shape u in the interval
[rT1121, 1̂].
221 212 2111 122 1211 1121 1112 15
221 1 1 2 1 2 3 4 8
212 . 1 1 1 1 1 3 4
2111 . . 1 . 1 1 1 4
122 . . . 1 1 1 2 3
1211 . . . . 1 1 1 3
1121 . . . . . 1 1 2
1112 . . . . . . 1 1
15 . . . . . . . 1
Iterating this for each snakeshape v of size n,
one builds the transition matrix for expressing
the analogue of complete symmetric function hv
in terms of the analogue of Schur functions su.
Figure 7. (YFT5,�) and Okada’s analogue of Kostka matrix for n = 5.
Proof. (of Theorem 6.2) A proof consists in showing that for any couple (a, b) of snakeshapes
appearing in the left hand side of equation (6.2), there is a one-to-one correspondence between
tableaux satisfying the conditions of the theorem for (a, b) and those satisfying the conditions of
the theorem for the couples of snakeshapes in the corresponding right hand side of the relation.
For (r1), given a tableau t of shape u such that rTv � t, t is mapped onto the tableau t
′ of shape
1u obtained from t by attaching a cell labeled n+1 to its left, and rT1v � t
′. For (r2), one attaches
a two-boxed column to the left of t, with 1 as bottom entry and n+2 as top entry, in addition one
standardizes t by increasing all its entries. Then t′ is of shape 2u and rT2v � t
′. For (r3) it easily
follows from the definition of the operation of shifting an entry in a tableau that there is no tableaux
t1 and t2 of shape 1u and 2v respectively, such that t2 � t1. For (r4), let t be a tableau of shape
2u such that rT1v � t, then t is mapped onto the tableau t
′ = ev(t, n), that is the tableau obtained
from t by evacuating its maximal letter (the evacuation process originally due to Killpatrick [8] is
described in Section 3.2). Indeed, let w be the shape of t′, then w ✄ u and rTv � t
7. Kostka numbers, the Littlewood Richardson rule, and four posets on Young
tableaux
The poset (YFTn,�) of Young-Fibonacci tableaux we defined in Section 5 is an analogue of
one among four partial orders on the set YTn of standard Young tableaux of size n [9]. The
weak order (YTn,�weak) is defined as in Theorem 5.8 with P (σ) denoting the Schensted insertion
tableau of σ. Let λ and µ be two partitions of lengths ℓ(λ) and ℓ(µ), λ is said greater than µ in
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 17
the dominance order and one writes λ ≥dom µ if for each 1 ≤ i ≤ min(ℓ(λ), ℓ(µ)), the inequality
λ1 + λ2 + · · · + λi ≥ µ1 + µ2 + · · · + µi holds. Let t be a standard Young tableau of size n, and
1 ≤ i ≤ j ≤ n. We denote λ(t/i,j) the shape of the tableau obtained from t by first restricting t to
the segment [i, j], then lowering all entries by i − 1, and finally sliding the skew tableau obtained
into normal shape by jeu-de-taquin. The chain order �chain on standard Young tableaux is defined
as follows.
Definition 7.1. [9] Let t and t′ be two standard Young tableaux of size n, then t �chain t
′ if and
only if for each 1 ≤ i ≤ j ≤ n, λ(t/i,j) ≥dom λ(t
The reader interested may refer to [9] for the definition of the two other orders, as well as for
the properties of those posets. The four posets happen to coincide up to rank n = 5.
12345
Figure 8. Partial order on Young tableaux of size 5.
Below is a Young tableaux analogue of Theorem 6.2.
Theorem 7.2. Let λ, µ be two partitions of size n, let rTµ be the row canonical standard Young
tableau of shape µ, that is to say rTµ has shape µ and is increasingly filled from let to right and
bottom to top. And let 0̂ be the minimal tableau in the poset of standard Young tableaux of size n.
Then Kλ, µ is the number of standard Young tableaux of shape λ in the interval [0̂, rTµ], for any one
of the posets studied in [9].
18 J. NZEUTCHAP
1 2 4
1 2 5
1 2 4
1 2 4 5
1 2 3 4
0̂ = 1 2 3 4 5
Example 7.3. In the matrix below, the num-
ber Kλ, 221 counts the number of standard Young
tableaux of shape λ in the interval [0̂, rT221].
µ = 5 41 32 311 221 2111 11111
λ = 5 1 1 1 1 1 1 1
41 . 1 1 2 2 3 4
32 . . 1 1 2 3 5
311 . . . 1 1 3 6
221 . . . . 1 2 5
2111 . . . . . 1 4
11111 . . . . . . 1
Iterating this for each partition µ of size n,
one builds the transition matrix for expressing
the complete symmetric function hµ in terms of
the Schur functions sλ.
Figure 9. Poset of Young tableaux and Kostka matrix for n = 5.
Proof. (of Theorem 7.2) For a given partition µ, let nscrt(µ) be the row canonical semi-standard
Young tableau of shape µ, that is the tableau filled with 1’s on its first line, 2’s on its second line
and so on. Let nsclt(n) be the semi-standard Young tableau of shape n and having µi entries i
for i = 1..ℓ(µ). Consider the extension of Definition 7.1 to the set Tab(µ) of semi-standard Young
tableaux having µi entries i for i = 1..ℓ(µ). Then for each t ∈ Tab(µ), one has nsclt(n) �chain
t �chain nscrt(µ). There is a canonical bijection mapping (Tab(µ),�chain) onto ([0̂, rTµ],�chain)
and this map is order preserving. So Theorem 7.2 holds for the partial order �chain. From ([9],
Theorem 1.1) and the remark that [0̂, rTµ] = rTµ1 ∗ rTµ2 ∗ · · · ∗ rTµℓ(µ) , it follows that the set of
tableaux in [0̂, rTµ] does not depend on the choice of the partial order. �
Concluding remarks and perspectives
There are quite many similarities between the Robinson-Schensted algorithm and the Young-
Fibonacci insertion algorithm. As well as between the combinatorics of Young tableaux and the
combinatorics of Young-Fibonacci tableaux. One of the questions we have not explored in this
paper is the one of the existence of an algebra of Young-Fibonacci tableaux, which would be an
analogue of the Poirier-Reutenauer Hopf algebra of Young tableaux [12]. Such an algebra would
certainly help in giving a combinatorial description (in terms of tableaux) of the product of Schur
functions in Okada’s algebra associated to the Young-Fibonacci lattice. We are currently looking
for a suitable definition of this algebra.
Acknowledgements
The author is grateful to F. Hivert for helpful comments and suggestions throughout this work.
ON THE YOUNG-FIBONACCI INSERTION ALGORITHM 19
References
[1] C. Schensted, Longest increasing and decreasing subsequences. Canad. J. Math., vol. 13, 1961, pp. 179-191.
[2] D. E. Knuth, Permutations, matrices and generalized Young tableaux, Pacific J. Math. 34(1970), 709–727.
[3] —, The art of computer programming, vol.3: Searching and sorting (Addison-Wesley, 1973).
[4] D. Krob and J.-Y. Thibon, Noncommutative symmetric function IV: Quantum linear groups and Hecke algebras
at q=0, J. Alg. Comb. 6 (1997), 339-376.
[5] F. Hivert, J. C. Novelli, and J.-Y. Thibon, The Algebra of Binary Search Trees, Theo. Comp. Science 339(2005),
129-165.
[6] I. G. MacDonald, Symmetric functions and Hall Polynomials, 2nd ed, Clarendon Press, Oxford Sce Publications,
139(1995).
[7] J. Nzeutchap, On the Young-Fibonacci Insertion Algorithm, to appear in the Proceedings of FPSAC’07.
[8] K. Killpatrick, Evacuation and a Geometric Consturction for Fibonacci Tableaux, J. Comb. Th, Ser A, 110
(2005), 337-351.
[9] M. Taskin, Properties of four partial orders on standard Young tableaux, J. Comb. Theory, Ser A, 113(2006),
1092-1119.
[10] R. P. Stanley, Differential Posets, J. Amer. Math. Soc. 1 (1998), 919-961.
[11] —, The Fibonacci lattice, Fibonacci Quarterly 13(1998), 215-232.
[12] S. Poirier and C. Reutenauer, Algèbre de Hopf des tableaux, Ann. Sci. Math. Qébec 19 (1995), 79-90.
[13] S. V. Fomin, Duality of Graded Graphs, J. Alg. Comb. 3(1994), 357-404.
[14] —, Generalized Robinson-Schensted-Knuth correspondence, Zapiski Nauchn. Sem. LOMI. 155 (1986), 156-175.
[15] —, Schensted Algorithms for Dual Graded Graphs, J. Alg. Comb. 4(1995), 5-45.
[16] S. Okada, Algebras associated to the Young-Fibonacci lattice, Trans AMS 346(1994), 549-568.
[17] T. Roby, Applications and extensions of Fomin’s generalization of the Robinson-Schensted correspondence to
differential posets, Ph.D. thesis, MIT, 1991.
LITIS EA 4051 (Laboratoire d’Informatique, de Traitement de l’Information et des Systèmes),
Avenue de l’Université, 76800 Saint Etienne du Rouvray, France
E-mail address: janvier.nzeutchap@univ-mlv.fr
URL: http://monge.univ-mlv.fr/∼nzeutcha
	1. Introduction
	1.1. The Young-Fibonacci lattice
	2. Young-Fibonacci tableaux and Young-Fibonacci insertion algorithm
	2.1. Converting a chain in YFL into a standard Young-Fibonacci tableau
	2.2. Redefining the Young-Fibonacci Insertion Algorithm
	3. Young-Fibonacci insertion and growth in differential posets
	3.1. Equivalence between Roby's and Fomin's constructions
	3.2. Another viewpoint of Killpatrick's evacuation for Young-Fibonacci tableaux
	4. Fibonacci numbers and a statistic on Young-Fibonacci tableaux
	5. A weak order on Young-Fibonacci tableaux
	6. A connection with Okada's algebra associated to the Young-Fibonacci lattice
	7. Kostka numbers, the Littlewood Richardson rule, and four posets on Young tableaux
	Concluding remarks and perspectives
	Acknowledgements
	References
