A114593 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n, having k ascents of length at least 2 (1 <= k <= floor(n/2), n >= 2).
1, 2, 4, 2, 8, 10, 16, 36, 5, 32, 112, 42, 64, 320, 224, 14, 128, 864, 960, 168, 256, 2240, 3600, 1200, 42, 512, 5632, 12320, 6600, 660, 1024, 13824, 39424, 30800, 5940, 132, 2048, 33280, 119808, 128128, 40040, 2574, 4096, 78848, 349440, 489216, 224224, 28028, 429
Offset: 2
Examples
T(4,2)=2 because we have (UU)D(UU)DDD and (UU)DD(UU)DD, where U=(1,1), D=(1,-1) (ascents of length at least two are shown between parentheses). Triangle starts: 1; 2; 4, 2; 8, 10; 16, 36, 5; 32, 112, 42; 64, 320, 224, 14;
Links
- Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Programs
-
Maple
T:=proc(n,k) if k<=floor(n/2) then 2^(n-2*k)*binomial(n+1,k)*binomial(n-k-1,k-1)/(n+1) else 0 fi end: for n from 2 to 14 do seq(T(n,k),k=1..floor(n/2)) od;
-
Mathematica
m = 13(*rows*); G = 0; Do[G = Series[(1 + G^2 (2 + t z) z)/(1 + 2 z), {t, 0, m+1}, {z, 0, m+1}] // Normal // Expand, {m+2}]; Rest[CoefficientList[ #, t]]& /@ CoefficientList[G-1, z][[3;;]] // Flatten (* Jean-François Alcover, Jan 22 2019 *)
Formula
T(n, k) = 2^(n-2k)*binomial(n+1, k)*binomial(n-k-1, k-1)/(n+1) (1 <= k <= floor(n/2)). G.f. = G-1, where G=G(t, z) satisfies z(2+tz)G^2 - (1+2z)G + 1 = 0.
Comments