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.

0, 0, 4, 0, 64, 22, 0, 800, 550, 118, 0, 9600, 9900, 4248, 718, 0, 117600, 161700, 104076, 35182, 5038, 0, 1505280, 2587200, 2220288, 1125824, 322432, 40318, 0, 20321280, 41912640, 44960832, 30397248, 13058496, 3265758, 362878, 0, 290304000, 698544000, 899216640, 759931200, 435283200

Offset: 2

Author

Thomas Scheuerle, Jun 18 2024

Keywords

• nonn
• tabl

Comments

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.

Examples

			The triangle begins:
 n| k: 2|      3|      4|      5|     6|    7|
==============================================
[2]    0,
[3]    0,      4
[4]    0,     64,     22
[5]    0,    800,    550,    118
[6]    0,   9600,   9900,   4248,   718
[7]    0, 117600, 161700, 104076, 35182, 5038
.
T(3, 3) = 4 because:
  {1, 2, 3} has no subsequences which are neither increasing or decreasing.
  {1, 3, 2} has {1, 3, 2}
  {2, 1, 3} has {2, 1, 3}
  {2, 3, 1} has {2, 3, 1}
  {3, 1, 2} has {3, 1, 2}
  {3, 2, 1} has no subsequences which are neither increasing or decreasing.
		

Crossrefs

Cf. A144084.

Programs

PARI

T(n, k) = n!*binomial(n, k)-2*((n-k)! * binomial(n, n-k)^2)

PARI

row(n) = if(n==2, [0], abs(Vecrev(-n!*((-1)^n*2*pollaguerre(n)-(-1+x)^n))[3..n+1]))

Formula

T(n, k) = n!*binomial(n, k)-2*((n - k)! * binomial(n, n - k)^2).

An alternative definition of T(n, k) which includes k < 2 can be done by Laguerre polynomials:

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.