Bumping Algorithm

Given a permutation {p_1,p_2,...,p_n} of {1,...,n}, the bumping algorithm constructs a standard Young tableau by inserting the p_i one by one into an already constructed Young tableau. To apply the bumping algorithm, start with {{p_1}}, which is a Young tableau. If p_1 through p_k have already been inserted, then in order to insert p_(k+1), start with the first line of the already constructed Young tableau and search for the first element of this line which is greater than p_(k+1). If there is no such element, append p_(k+1) to the first line and stop. If there is such an element (say, p_p), exchange p_p for p_(k+1), search the second line using p_p, and so on.

See also

Tableau Class, Young Tableau

Explore with Wolfram|Alpha


Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Referenced on Wolfram|Alpha

Bumping Algorithm

Cite this as:

Weisstein, Eric W. "Bumping Algorithm." From MathWorld--A Wolfram Web Resource.

Subject classifications