login
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, 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,3
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.
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.
EXAMPLE
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.
PROG
(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]))
CROSSREFS
Cf. A144084.
Sequence in context: A247119 A296439 A228557 * A358294 A298616 A366828
KEYWORD
nonn,tabl
AUTHOR
Thomas Scheuerle, Jun 18 2024
STATUS
approved