[seqfan] A Dyck path curiosity

David Scambler dscambler at bmm.com
Wed Nov 17 07:20:40 CET 2010


If the Dyck paths with semi-length n are decomposed according to how many distinct ascent lengths k appear then this triangle results:

T(n,k) =
1:.....1
2:.....2
3:.....2.........3
4:.....4........10
5:.....2........40
6:....10........92........30
7:.....2.......280.......147
8:....20.......682.......728
9:....14......1734......3114
10:...49......4507.....11520.......720
11:....2.....11407.....42427......4950
12:..217.....29397....148038.....30360
13:....2.....75699....511901....155298
14:..438....200804...1723540....749658
15:..310....518175...5814365...3329235.....32760

When n is prime and k=1 T(n,1) = 2. (i.e. the path with all ascents length 1 and the path with one ascent length n)

T(n,1) = 1, 2, 2, 4, 2, 10, 2, 20, 14, 49, 2, 217, 2, 438, 310, ...

Apparently...
When n reaches a new triangular number a new distinct length category is introduced.
At the point that n reaches the k-th triangular number the number of paths in the new category is 
1, 3, 30, 720, 32760, ... which is equal to n*(n-1)*...*(n-k+2).

dave 




More information about the SeqFan mailing list