

A262180


Irregular triangle read by rows: number of occurrences of monotonic lattice paths below diagonal formed from all lattice paths below diagonal via bubblesortlike 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 bubblesortlike algorithm. The sorting is as follows: Column heights are sorted using bubblesort, but when swapping to the right, height is also incremented by 1. Then, the number of occurences of each monotonic path is counted starting from the steepest path (0, 1, 2, ..., n1) to the constant path (0, 0, 0, ..., 0). The result is this sequence formed from the number of occurences of monotonic paths.
Consider an nelement positive integer sequence where the ith term is at most i. The terms of the sequence are sorted in a bubblesortlike manner so that the newly formed sequences are nondecreasing sequences. The only difference of this sorting algorithm from bubblesort is that the value is incremented by 1 when swapping to the right. The number of occurences 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 occurences 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 nth row has A000245(n) terms for n > 1.


LINKS

Cosar Gozukirmizi, Table of n, a(n) for n = 1..429
Cosar Gozukirmizi, MuPAD script
C. Gozukirmizi, M.E. Kirkin and M. Demiralp, Probabilistic evolution theory for the solution of explicit autonomous ordinary differential equations: squarified telescope matrices, Journal of Mathematical Chemistry, 55 (2017), 175194. doi:10.1007/s1091001606788.
Wikipedia, Bubble sort


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
...


PROG

See MuPAD script under Links.


CROSSREFS

Sequence in context: A017817 A284834 A279677 * A320902 A189913 A240807
Adjacent sequences: A262177 A262178 A262179 * A262181 A262182 A262183


KEYWORD

nonn,tabf


AUTHOR

Cosar Gozukirmizi, Sep 14 2015


STATUS

approved



