login
Second level generalization of Catalan triangle (0th level is Pascal's triangle A007318; first level is Catalan triangle A009766; 3rd level is A069270).
3

%I #26 Feb 26 2024 11:01:05

%S 1,1,1,1,2,3,1,3,7,12,1,4,12,30,55,1,5,18,55,143,273,1,6,25,88,273,

%T 728,1428,1,7,33,130,455,1428,3876,7752,1,8,42,182,700,2448,7752,

%U 21318,43263,1,9,52,245,1020,3876,13566,43263,120175,246675,1,10,63,320,1428

%N Second level generalization of Catalan triangle (0th level is Pascal's triangle A007318; first level is Catalan triangle A009766; 3rd level is A069270).

%C For the m-th level generalization of Catalan triangle T(n,k) = C(n+mk,k)*(n-k+1)/(n+(m-1)k+1); for n >= k+m: T(n,k) = T(n-m+1,k+1) - T(n-m,k+1); and T(n,n) = T(n+m-1,n-1) = C((m+1)n,n)/(mn+1).

%C Reflected version of A110616. - _Philippe Deléham_, Jun 15 2007

%C With offset 1 for n and k, T(n,k) is (conjecturally) the number of permutations of [n] that avoid the patterns 4-2-3-1 and 4-2-5-1-3 and for which the last ascent ends at position k (k=1 if there are no ascents). For example, T(4,1) = 1 counts 4321; T(4,2) = 3 counts 1432, 2431, 3421; T(4,3) = 7 counts 1243, 1342, 2143, 2341, 3142, 3241, 4132. - _David Callan_, Jul 22 2008

%C Row sums appear to be in A098746. - _R. J. Mathar_, May 30 2014

%H M. H. Albert et al., <a href="https://doi.org/10.1016/j.disc.2004.08.003">Restricted permutations and queue jumping</a>, Discrete Math., 287 (2004), 129-133.

%H Tad White, <a href="https://arxiv.org/abs/2401.01462">Quota Trees</a>, arXiv:2401.01462 [math.CO], 2024. See p. 18.

%F T(n, k) = C(n+2k, k)*(n-k+1)/(n+k+1).

%F For n >= k+2: T(n, k) = T(n-1, k+1) - T(n-2, k+1).

%F T(n, n) = T(n+1, n-1) = C(3n, n)/(2n+1).

%e Rows start

%e 1;

%e 1, 1;

%e 1, 2, 3;

%e 1, 3, 7, 12;

%e 1, 4, 12, 30, 55;

%Y Columns include A000012, A000027, A055998.

%Y Right-hand diagonals include A001764, A006013, A006629, A006630, A006631.

%Y Cf. triangles A007318, A009766, A069270.

%K nonn,tabl

%O 0,5

%A _Henry Bottomley_, Mar 12 2002