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, 1, 10, 63, 320, 1428

Offset

0,5

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

Links

Table of n, a(n) for n=0..59.

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.

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

Example

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

Crossrefs

Columns include A000012, A000027, A055998.

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

Cf. triangles A007318, A009766, A069270.

Sequence in context: A102473 A011117 A368401 * A193092 A263484 A293985

Adjacent sequences: A069266 A069267 A069268 * A069270 A069271 A069272

Keyword

nonn,tabl

Author

Henry Bottomley, Mar 12 2002

Status

approved