cp's OEIS Frontend

A373766 Triangle read by rows, T(n,k) with n,k > 1, is the number of subsequences of length k over all permutations of [n], which are neither increasing or decreasing.

%I A373766 #19 Jul 07 2024 21:11:55
%S A373766 0,0,4,0,64,22,0,800,550,118,0,9600,9900,4248,718,0,117600,161700,
%T A373766 104076,35182,5038,0,1505280,2587200,2220288,1125824,322432,40318,0,
%U A373766 20321280,41912640,44960832,30397248,13058496,3265758,362878,0,290304000,698544000,899216640,759931200,435283200
%N A373766 Triangle read by rows, T(n,k) with n,k > 1, is the number of subsequences of length k over all permutations of [n], which are neither increasing or decreasing.
%C A373766 Column T(n, 1) was omitted in the presentation of this sequence. Its definition may depend on the usage. In the combinatorics of subsequences it may be convenient to define T(n, 1) = 0, but if this sequence will be interpreted differently for example as polynomial coefficients then T(n, 1) = -n*n! could be a mathematically more natural definition.
%F A373766 T(n, k) = n!*binomial(n, k)-2*((n - k)! * binomial(n, n - k)^2).
%F A373766 An alternative definition of T(n, k) which includes k < 2 can be done by Laguerre polynomials:
%F A373766  Sum_{k=0..n} T(n, k)*x^k = n!*((1 + x)^n - 2*L_{n}(-x)), where L_{n} is the n-th Laguerre polynomial.
%e A373766 The triangle begins:
%e A373766  n| k: 2|      3|      4|      5|     6|    7|
%e A373766 ==============================================
%e A373766 [2]    0,
%e A373766 [3]    0,      4
%e A373766 [4]    0,     64,     22
%e A373766 [5]    0,    800,    550,    118
%e A373766 [6]    0,   9600,   9900,   4248,   718
%e A373766 [7]    0, 117600, 161700, 104076, 35182, 5038
%e A373766 .
%e A373766 T(3, 3) = 4 because:
%e A373766   {1, 2, 3} has no subsequences which are neither increasing or decreasing.
%e A373766   {1, 3, 2} has {1, 3, 2}
%e A373766   {2, 1, 3} has {2, 1, 3}
%e A373766   {2, 3, 1} has {2, 3, 1}
%e A373766   {3, 1, 2} has {3, 1, 2}
%e A373766   {3, 2, 1} has no subsequences which are neither increasing or decreasing.
%o A373766 (PARI) T(n, k) = n!*binomial(n, k)-2*((n-k)! * binomial(n, n-k)^2)
%o A373766 (PARI) row(n) = if(n==2, [0], abs(Vecrev(-n!*((-1)^n*2*pollaguerre(n)-(-1+x)^n))[3..n+1]))
%Y A373766 Cf. A144084.
%K A373766 nonn,tabl
%O A373766 2,3
%A A373766 _Thomas Scheuerle_, Jun 18 2024