login
Number T(n,k) of permutations on [n] that are self-inverse on [k] but not on [k+1]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
2

%I #17 Feb 10 2021 03:41:59

%S 1,0,1,0,0,2,2,0,0,4,12,2,0,0,10,72,18,4,0,0,26,480,120,36,8,0,0,76,

%T 3600,840,264,84,20,0,0,232,30240,6480,1920,648,216,52,0,0,764,282240,

%U 55440,15120,4920,1776,612,152,0,0,2620,2903040,524160,131040,39600,13920,5232,1848,464,0,0,9496

%N Number T(n,k) of permutations on [n] that are self-inverse on [k] but not on [k+1]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

%C T(n,k) counts permutations p:{1,...,n}-> {1,...,n} with p(p(i))=i for all i in {1,...,k} and p(p(k+1))<>k+1 if k<n.

%H Alois P. Heinz, <a href="/A245693/b245693.txt">Rows n = 0..140, flattened</a>

%F T(n,k) = H(n,k) - H(n,k+1) with H(n,k) = Sum_{i=0..min(k,n-k)} C(n-k,i) * C(k,i) * i! * A000085(k-i) * (n-k-i)!.

%e Triangle T(n,k) begins:

%e 0 : 1;

%e 1 : 0, 1;

%e 2 : 0, 0, 2;

%e 3 : 2, 0, 0, 4;

%e 4 : 12, 2, 0, 0, 10;

%e 5 : 72, 18, 4, 0, 0, 26;

%e 6 : 480, 120, 36, 8, 0, 0, 76;

%e 7 : 3600, 840, 264, 84, 20, 0, 0, 232;

%e 8 : 30240, 6480, 1920, 648, 216, 52, 0, 0, 764;

%p g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:

%p H:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*

%p g(k-i)*(n-k-i)!, i=0..min(k, n-k)):

%p T:= (n, k)-> H(n, k) -H(n, k+1):

%p seq(seq(T(n, k), k=0..n), n=0..10);

%t g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];

%t H[n_, k_] := Sum[Binomial[n - k, i]*Binomial[k, i]*i!*

%t g[k - i]*(n - k - i)!, {i, 0, Min[k, n - k]}];

%t T[n_, k_] := H[n, k] - H[n, k + 1];

%t Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Feb 10 2021, after _Alois P. Heinz_ *)

%Y Column k=0 give A062119(n-1) for n>1.

%Y Row sums give A000142.

%Y Main diagonal gives A000085.

%Y Cf. A245692 (the same for endofunctions).

%K nonn,tabl

%O 0,6

%A _Alois P. Heinz_, Jul 29 2014