Young–Fibonacci lattice

In mathematics, the Young–Fibonacci graph and Young–Fibonacci lattice, named after Alfred Young and Leonardo Fibonacci, are two closely related structures involving sequences of the digits 1 and 2.

They are named after the closely related Young's lattice and after the Fibonacci number of their elements at any given rank.

These initial conditions cause the sequence of values of f to be shifted by one position from the Fibonacci numbers: f (r) = Fr +1.

As Stanley (1988) shows, any two vertices x and y have a unique greatest common predecessor in this order (their meet) and a unique least common successor (their join); thus, this order is a lattice, called the Young–Fibonacci lattice.

A string x is a predecessor of another string y in this order exactly when the number of "2" digits remaining in y, after removing the longest common suffix of x and y, is at least as large as the number of all digits remaining in x after removing the common suffix.