cp's OEIS Frontend

A245693 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.

%I A245693 #17 Feb 10 2021 03:41:59
%S A245693 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 A245693 3600,840,264,84,20,0,0,232,30240,6480,1920,648,216,52,0,0,764,282240,
%U A245693 55440,15120,4920,1776,612,152,0,0,2620,2903040,524160,131040,39600,13920,5232,1848,464,0,0,9496
%N A245693 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 A245693 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 A245693 Alois P. Heinz, <a href="/A245693/b245693.txt">Rows n = 0..140, flattened</a>
%F A245693 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 A245693 Triangle T(n,k) begins:
%e A245693 0 :      1;
%e A245693 1 :      0,    1;
%e A245693 2 :      0,    0,    2;
%e A245693 3 :      2,    0,    0,   4;
%e A245693 4 :     12,    2,    0,   0,  10;
%e A245693 5 :     72,   18,    4,   0,   0, 26;
%e A245693 6 :    480,  120,   36,   8,   0,  0, 76;
%e A245693 7 :   3600,  840,  264,  84,  20,  0,  0, 232;
%e A245693 8 :  30240, 6480, 1920, 648, 216, 52,  0,   0, 764;
%p A245693 g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:
%p A245693 H:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*
%p A245693              g(k-i)*(n-k-i)!, i=0..min(k, n-k)):
%p A245693 T:= (n, k)-> H(n, k) -H(n, k+1):
%p A245693 seq(seq(T(n, k), k=0..n), n=0..10);
%t A245693 g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];
%t A245693 H[n_, k_] := Sum[Binomial[n - k, i]*Binomial[k, i]*i!*
%t A245693      g[k - i]*(n - k - i)!, {i, 0, Min[k, n - k]}];
%t A245693 T[n_, k_] := H[n, k] - H[n, k + 1];
%t A245693 Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Feb 10 2021, after _Alois P. Heinz_ *)
%Y A245693 Column k=0 give A062119(n-1) for n>1.
%Y A245693 Row sums give A000142.
%Y A245693 Main diagonal gives A000085.
%Y A245693 Cf. A245692 (the same for endofunctions).
%K A245693 nonn,tabl
%O A245693 0,6
%A A245693 _Alois P. Heinz_, Jul 29 2014