login
Triangle read by rows: T(n,k) = number of k-classes of permutations of n letters avoiding the pattern 132 (n>=1, 0 <= k <= n-1).
1

%I #22 Jan 16 2022 00:16:31

%S 1,2,2,4,5,5,9,12,14,14,21,30,37,42,42,51,76,99,118,132,132,127,196,

%T 265,331,387,429,429,323,512,714,922,1124,1298,1430,1430,835,1353,

%U 1934,2568,3227,3872,4433,4862,4862,2188,3610,5268,7156,9225,11384,13507,15366,16796,16796

%N Triangle read by rows: T(n,k) = number of k-classes of permutations of n letters avoiding the pattern 132 (n>=1, 0 <= k <= n-1).

%C See Baril et al. (2014) for precise definition.

%C Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108).

%H J.-L. Baril, T. Mansour, A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equival.pdf">Equivalence classes of permutations modulo excedances</a>, Journal of Combinatorics, Volume 5 (2014), Number 4, doi:10.4310/JOC.2014.v5.n4.a4. See Table 2.

%F The proof of Theorem 3.1 in Baril et al. (2014) gives a recurrence for the numbers T(n,k).

%e 1

%e 2 2

%e 4 5 5

%e 9 12 14 14

%e 21 30 37 42 42

%e 51 76 99 118 132 132

%e 127 196 265 331 387 429 429

%e 323 512 714 922 1124 1298 1430 1430

%e 835 1353 1934 2568 3227 3872 4433 4862 4862

%e 2188 3610 5268 7156 9225 11384 13507 15366 16796 16796

%p A261665 := proc(n,k)

%p option remember;

%p if n = k then

%p A000108(n);

%p elif k < 0 or n <=k then

%p 0 ;

%p else

%p procname(n-1,k+1)+add(procname(n-1-i,k-i)*A000108(i),i=0..k) ;

%p end if;

%p end proc: # _R. J. Mathar_, Sep 07 2015

%t T[n_, k_] := T[n, k] = If[n == k, CatalanNumber[n], If[k < 0 || n <= k, 0, T[n-1, k+1] + Sum[T[n-1-i, k-i] CatalanNumber[i], {i, 0, k}]]];

%t Table[T[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* _Jean-François Alcover_, Apr 07 2020 *)

%Y Cf. A000108, A001006.

%K nonn,tabl

%O 1,2

%A _N. J. A. Sloane_, Sep 01 2015