A180196 Triangle read by rows: T(n,k) is the number of permutations of [n] that have k isolated entries (0 <= k <= n).

1, 0, 1, 1, 0, 1, 1, 2, 0, 3, 2, 2, 9, 0, 11, 3, 11, 9, 44, 0, 53, 7, 20, 75, 44, 265, 0, 309, 14, 73, 141, 574, 265, 1854, 0, 2119, 35, 170, 737, 1104, 4900, 1854, 14833, 0, 16687, 81, 576, 1863, 7814, 9535, 46353, 14833, 133496, 0, 148329, 216, 1556, 8154, 20704, 88335, 90852, 482069, 133496, 1334961, 0, 1468457

Offset: 0

Author

Emeric Deutsch, Sep 09 2010

Keywords

• nonn
• tabl

Comments

An entry j of a permutation p is isolated if it is not preceded by j-1 and not followed by j+1. For example, the permutation 23178564 has 2 isolated entries: 1 and 4.

Sum of entries in row n is n! = A000142(n).

T(n,n) = d(n) + d(n-1) = A000255(n-1), where d(i)=A000166(i) are the derangement numbers.

T(n,n-2) = d(n) (n >= 2).

T(n,n-3) = d(n-1) (n >= 3).

Sum_{k=0..n} k*T(n,k) = (n-2)!*(n^3 - 3n^2 + 5n - 4) = A001565(n-2) (n >= 2).

Examples

			T(4,2)=9 because we have 124'3', 1'4'23, 1'342', 3'124', 4'3'12, 2'1'34, 231'4', 4'231', and 342'1' (the isolated entries are marked).
Triangle starts:
  1;
  0,  1;
  1,  0,  1;
  1,  2,  0,  3;
  2,  2,  9,  0, 11;
  3, 11,  9, 44,  0, 53;
		

Crossrefs

Cf. A000142, A000166, A000255, A001565.

Programs

Maple

d[ -1] := 0: d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k < n then sum(binomial(n-1-j, j-k-1)*binomial(j, k)*(d[j]+d[j-1]), j = k+1 .. floor((1/2)*n+(1/2)*k)) elif k = n then d[n]+d[n-1] else 0 end if end proc: for n from 0 to 10 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

Mathematica

T[n_, k_] := With[{d = Subfactorial}, Which[k == n == 0, 1, k == n, d[n] + d[n - 1], True, Sum[Binomial[n - 1 - j, j - k - 1]*Binomial[j, k]*(d[j] + d[j - 1]), {j, k + 1, Floor[(n + k)/2]}]]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 19 2024 *)

Formula

T(n,k) = Sum_{j=k+1..floor((n+k)/2)} binomial(n-1-j, j-k-1)*binomial(j,k)*(d(j) + d(j-1)), if k < n;

T(n,n) = d(n) + d(n-1); d(i)=A000166(i) are the derangement numbers.