login
Triangle T(n,k) read by rows: permutations on 123...n with one abc pattern and no aj pattern with j<=k, n>2, k<n-1.
3

%I #9 Sep 15 2013 12:44:00

%S 1,6,2,27,12,3,110,55,19,4,429,229,91,27,5,1638,912,393,136,36,6,6188,

%T 3549,1614,612,191,46,7,23256,13636,6447,2601,897,257,57,8,87210,

%U 52020,25332,10695,3951,1260,335,69,9,326876,197676,98532

%N Triangle T(n,k) read by rows: permutations on 123...n with one abc pattern and no aj pattern with j<=k, n>2, k<n-1.

%C See A228708 for further information.

%H J. Noonan and D. Zeilberger, <a href="http://arXiv.org/abs/math.CO/9808080">[math/9808080] The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns</a>. Also Adv. in Appl. Math. 17 (1996), no. 4, 381--407. MR1422065 (97j:05003).

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

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

%e Full triangle begins:

%e 0

%e 0,0

%e 0,0,0

%e 1,1,0,0

%e 6,6,2,0,0

%e 27,27,12,3,0,0

%e 110,110,55,19,4,0,0

%e 429,429,229,91,27,5,0,0

%e 1638,1638,912,393,136,36,6,0,0

%e 6188,6188,3549,1614,612,191,46,7,0,0

%e 23256,23256,13636,6447,2601,897,257,57,8,0,0

%e ...

%o (PARI) for(n=1,15, for(k=1,n-2,print1(binomial(2*n-k-1,n)-binomial(2*n-k-1,n+3)+binomial(2*n-2*k-2,n-k-4)-binomial(2*n-2*k-2,n-k-1)+binomial(2*n-2*k-3,n-k-4)-binomial(2*n-2*k-3,n-k-2)",")))

%Y See A228708 for the full triangle.

%Y T(n, 1) = A003517(n+1). Cf. A001089.

%K nonn,tabl,easy

%O 3,2

%A _Ralf Stephan_, May 21 2003