login
A338526
Triangle read by rows: T(n,k) is the number of permutations of k elements from [1..n] without consecutive adjacent values.
6
1, 1, 1, 1, 2, 0, 1, 3, 2, 0, 1, 4, 6, 4, 2, 1, 5, 12, 18, 20, 14, 1, 6, 20, 48, 90, 124, 90, 1, 7, 30, 100, 272, 582, 860, 646, 1, 8, 42, 180, 650, 1928, 4386, 6748, 5242, 1, 9, 56, 294, 1332, 5110, 15912, 37566, 59612, 47622, 1, 10, 72, 448, 2450, 11604, 46250, 148648, 360642, 586540, 479306
OFFSET
0,5
COMMENTS
Also number of ways to arrange n non-attacking kings on an n X k board, with 0 or 1 in each row and 1 in each column. - Ron L.J. van den Burg, Aug 04 2024
FORMULA
T(n,k) = (n! + Sum_{p=1..k-1} (-1)^p (n-p)! Sum_{r=1..p} 2^r binomial(k-p,r) binomial(p-1,r-1) )/(n-k)!. - Ron L.J. van den Burg, Aug 04 2024
O.g.f.: Sum_{n>=0} Sum_{k=0..n} T(n,k)*x^n*y^k = Sum_{i>=0} i!(x*y*(1-x*y)/(1+x*y))^i/(1-x)^(i+1). - Ron L.J. van den Burg, Aug 14 2024
EXAMPLE
n\k 0 1 2 3 4 5 6 7 8
0 1
1 1 1
2 1 2 0
3 1 3 2 0
4 1 4 6 4 2
5 1 5 12 18 20 14
6 1 6 20 48 90 124 90
7 1 7 30 100 272 582 860 646
8 1 8 42 180 650 1928 4386 6748 5242
PROG
(PARI) isok(s, p) = {for (i=1, #s-1, if (abs(s[p[i+1]] - s[p[i]]) == 1, return (0)); ); return (1); }
T(n, k) = {my(nb = 0); forsubset([n, k], s, for(i=1, k!, if (isok(s, numtoperm(k, i)), nb++); ); ); nb; } \\ Michel Marcus, Nov 17 2020
CROSSREFS
Diagonal is A002464.
T(2n,n) gives A375022.
Sequence in context: A306914 A317023 A319284 * A182703 A354006 A307226
KEYWORD
nonn,tabl
AUTHOR
Xiangyu Chen, Nov 07 2020
STATUS
approved