A338526 Triangle read by rows: T(n,k) is the number of permutations of k elements from [1..n] without consecutive adjacent values.

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

Author

Xiangyu Chen, Nov 07 2020

Keywords

• nonn
• tabl

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

Examples

			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
		

Crossrefs

Diagonal is A002464.

T(2n,n) gives A375022.

Programs

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

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