cp's OEIS Frontend

A239144 Number T(n,k) of self-inverse permutations p on [n] such that all transposition distances (if any) are larger than k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

%I A239144 #19 Jan 19 2015 08:41:02
%S A239144 1,1,1,2,1,1,4,2,1,1,10,5,2,1,1,26,13,5,2,1,1,76,37,15,5,2,1,1,232,
%T A239144 112,47,15,5,2,1,1,764,363,155,52,15,5,2,1,1,2620,1235,532,188,52,15,
%U A239144 5,2,1,1,9496,4427,1910,704,203,52,15,5,2,1,1
%N A239144 Number T(n,k) of self-inverse permutations p on [n] such that all transposition distances (if any) are larger than k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
%C A239144 T(n,k) is defined for all n, k >= 0: T(n,k) = 1 for k >= n.
%C A239144 Columns k=0 and k=1 respectively give A000085 and A170941 (involutions on [n] without adjacent transpositions).
%C A239144 Diagonal T(2n,n) gives A000110(n).
%H A239144 Joerg Arndt and Alois P. Heinz, <a href="/A239144/b239144.txt">Rows n = 0..30, flattened</a>
%e A239144 T(4,0) = 10: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412, 4231, 4321.
%e A239144 T(4,1) = 5: 1234, 1432, 3214, 3412, 4231.
%e A239144 T(4,2) = 2: 1234, 4231.
%e A239144 T(4,3) = 1: 1234.
%e A239144 Triangle T(n,k) begins:
%e A239144 00:      1;
%e A239144 01:      1,    1;
%e A239144 02:      2,    1,    1;
%e A239144 03:      4,    2,    1,   1;
%e A239144 04:     10,    5,    2,   1,   1;
%e A239144 05:     26,   13,    5,   2,   1,  1;
%e A239144 06:     76,   37,   15,   5,   2,  1,  1;
%e A239144 07:    232,  112,   47,  15,   5,  2,  1, 1;
%e A239144 08:    764,  363,  155,  52,  15,  5,  2, 1, 1;
%e A239144 09:   2620, 1235,  532, 188,  52, 15,  5, 2, 1, 1;
%e A239144 10:   9496, 4427, 1910, 704, 203, 52, 15, 5, 2, 1, 1;
%p A239144 b:= proc(n, k, s) option remember; `if`(n=0, 1, `if`(n in s,
%p A239144       b(n-1, k, s minus {n}), b(n-1, k, s) +add(`if`(i in s, 0,
%p A239144       b(n-1, k, s union {i})), i=1..n-k-1)))
%p A239144     end:
%p A239144 T:= (n, k)-> b(n, k, {}):
%p A239144 seq(seq(T(n, k), k=0..n), n=0..14);
%t A239144 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_] := b[n, k, {}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* _Jean-François Alcover_, Jan 19 2015, after _Alois P. Heinz_ *)
%Y A239144 Cf. A239145.
%K A239144 nonn,tabl
%O A239144 0,4
%A A239144 _Joerg Arndt_ and _Alois P. Heinz_, Mar 11 2014