|
%I #26 Jan 22 2015 05:22:23
%S 1,1,0,1,1,0,1,2,1,0,1,5,3,1,0,1,13,8,3,1,0,1,39,22,10,3,1,0,1,120,65,
%T 32,10,3,1,0,1,401,208,103,37,10,3,1,0,1,1385,703,344,136,37,10,3,1,0,
%U 1,5069,2517,1206,501,151,37,10,3,1,0,1,19170,9390,4421,1890,622,151,37,10,3,1,0
%N Number T(n,k) of self-inverse permutations p on [n] where the minimal transposition distance equals k (k=0 for the identity permutation); triangle T(n,k), n>=0, 0<=k<=n, read by rows.
%C Columns k=0 and k=1 respectively give A000012 and A000085(n)-A170941(n).
%C Row sums give A000085.
%C Diagonal T(2n,n) gives A005493(n-1) for n>0.
%C Reversed rows converge to A005493.
%H Joerg Arndt and Alois P. Heinz, <a href="/A239145/b239145.txt">Rows n = 0..30, flattened</a>
%F T(n,k) = A239144(n,k-1) - A239144(n,k) for k>0, T(n,0) = 1.
%e T(4,0) = 1: 1234.
%e T(4,1) = 5: 1243, 1324, 2134, 2143, 4321.
%e T(4,2) = 3: 1432, 3214, 3412.
%e T(4,3) = 1: 4231.
%e Triangle T(n,k) begins:
%e 00: 1;
%e 01: 1, 0;
%e 02: 1, 1, 0;
%e 03: 1, 2, 1, 0;
%e 04: 1, 5, 3, 1, 0;
%e 05: 1, 13, 8, 3, 1, 0;
%e 06: 1, 39, 22, 10, 3, 1, 0;
%e 07: 1, 120, 65, 32, 10, 3, 1, 0;
%e 08: 1, 401, 208, 103, 37, 10, 3, 1, 0;
%e 09: 1, 1385, 703, 344, 136, 37, 10, 3, 1, 0;
%e 10: 1, 5069, 2517, 1206, 501, 151, 37, 10, 3, 1, 0;
%p b:= proc(n, k, s) option remember; `if`(n=0, 1, `if`(n in s,
%p b(n-1, k, s minus {n}), b(n-1, k, s) +add(`if`(i in s, 0,
%p b(n-1, k, s union {i})), i=1..n-k-1)))
%p end:
%p T:= (n, k)-> `if`(k=0, 1, b(n, k-1, {})-b(n, k, {})):
%p seq(seq(T(n, k), k=0..n), n=0..14);
%t b[n_, k_, s_List] := b[n, k, s] = If[n == 0, 1, If[MemberQ[s, n], b[n-1, k, s ~Complement~ {n}], b[n-1, k, s] + Sum[If[MemberQ[s, i], 0, b[n-1, k, s ~Union~ {i}]], {i, 1, n - k - 1}]]] ; T[n_, k_] := If[k == 0, 1, b[n, k-1, {}] - b[n, k, {}]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* _Jean-François Alcover_, Jan 22 2015, after Maple *)
%K nonn,tabl
%O 0,8
%A _Joerg Arndt_ and _Alois P. Heinz_, Mar 11 2014
|
