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

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, 728, 1428, 1, 7, 33, 130, 455, 1428, 3876, 7752, 1, 8, 42, 182, 700, 2448, 7752, 21318, 43263, 1, 9, 52, 245, 1020, 3876, 13566, 43263, 120175, 246675

Offset: 0

Author

Henry Bottomley, Mar 12 2002

Keywords

• nonn
• tabl

Comments

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

Reflected version of A110616. - Philippe Deléham, Jun 15 2007

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

Row sums appear to be in A098746. - R. J. Mathar, May 30 2014

Examples

			Rows start
  1;
  1,  1;
  1,  2,  3;
  1,  3,  7, 12;
  1,  4, 12, 30, 55;
		

Links

• M. H. Albert et al., Restricted permutations and queue jumping, Discrete Math., 287 (2004), 129-133.
• Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 18.

Crossrefs

Columns include A000012, A000027, A055998.

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

Cf. triangles A007318, A009766, A069270.

Formula

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

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

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