|
|
A262180
|
|
Irregular triangle read by rows: number of occurrences of monotonic lattice paths below diagonal formed from all lattice paths below diagonal via bubble-sort-like algorithm.
|
|
1
|
|
|
1, 1, 2, 1, 1, 3, 3, 3, 1, 1, 3, 2, 1, 1, 4, 4, 8, 4, 4, 6, 6, 4, 1, 1, 4, 2, 1, 1, 6, 6, 8, 3, 3, 4, 3, 1, 1, 4, 3, 2, 1, 1, 5, 5, 10, 5, 5, 15, 15, 15, 5, 5, 15, 10, 5, 5, 10, 10, 20, 10, 10, 10, 10, 5, 1, 1, 5, 2, 1, 1, 10, 10, 10, 3, 3, 5, 3, 1, 1, 5, 3, 2, 1, 1, 10, 10, 20, 10, 10, 20, 20, 15, 4, 4, 15, 8, 4, 4, 10, 10, 15, 6, 6, 5, 4, 1, 1, 5, 4, 2, 1, 1, 10, 10, 15, 6, 6, 10, 8, 3, 3, 5, 4, 3, 1, 1, 5, 4, 3, 2, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Consider all lattice paths along the edges of a grid with n X n square cells that do not pass above the diagonal. All these paths are converted to monotonic lattice paths that do not pass above the diagonal by a bubble-sort-like algorithm. The sorting is as follows: Column heights are sorted using bubble-sort, but when swapping to the right, height is also incremented by 1. Then, the number of occurrences of each monotonic path is counted starting from the steepest path (0, 1, 2, ..., n-1) to the constant path (0, 0, 0, ..., 0). The result is this sequence formed from the number of occurrences of monotonic paths.
Consider an n-element positive integer sequence where the i-th term is at most i. The terms of the sequence are sorted in a bubble-sort-like manner so that the newly formed sequences are nondecreasing sequences. The only difference of this sorting algorithm from bubble-sort is that the value is incremented by 1 when swapping to the right. The number of occurrences of the newly formed nondecreasing sequences are counted starting from (1, 2, ..., n) down to (1, 1, ..., 1). The result is this sequence formed from the number of occurrences of nondecreasing sequences.
Note that when n is increased by 1, the new terms are appended to the sequence. The number of new terms is the difference between two consecutive Catalan numbers. Therefore, the sequence forms an irregular triangle where the n-th row has A000245(n) terms for n > 1.
|
|
LINKS
|
|
|
EXAMPLE
|
The sequence forms an irregular triangle.
1
1
2 1 1
3 3 3 1 1 3 2 1 1
4 4 8 4 4 6 6 4 1 1 4 2 1 1 6 6 8 3 3 4 3 1 1 4 3 2 1 1
...
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|