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

%I #10 Sep 19 2024 04:46:23

%S 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,

%T 14,73,141,574,265,1854,0,2119,35,170,737,1104,4900,1854,14833,0,

%U 16687,81,576,1863,7814,9535,46353,14833,133496,0,148329,216,1556,8154,20704,88335,90852,482069,133496,1334961,0,1468457

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

%C 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.

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

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

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

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

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

%F 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;

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

%e 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).

%e Triangle starts:

%e 1;

%e 0, 1;

%e 1, 0, 1;

%e 1, 2, 0, 3;

%e 2, 2, 9, 0, 11;

%e 3, 11, 9, 44, 0, 53;

%p 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

%t 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]}]]];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Sep 19 2024 *)

%Y Cf. A000142, A000166, A000255, A001565.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Sep 09 2010