A277081 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged under the operation of replacing a permutation with its inverse.

1, 1, 1, 1, 1, 2, 1, 1, 4, 7, 8, 7, 4, 1, 1, 10, 52, 190, 546, 1302, 2660, 4754, 7535, 10692, 13672, 15820, 16604, 15820, 13672, 10692, 7535, 4754, 2660, 1302, 546, 190, 52, 10, 1, 1, 26, 372, 3822, 31306, 216086, 1300420, 6981650, 33992275, 151945820

Offset: 0

Author

Christian Bean, Sep 28 2016

Keywords

• nonn
• tabf

Comments

T(n,k) is the number of size k subsets of S_n that remain unchanged under the operation of replacing a permutation with its inverse.

Examples

			For n = 3 and k = 3 the subsets unchanged by inverse are {213,132,123}, {321,132,123}, {321,213,123}, {231,312,123}, {321,132,213}, {132,312,231},{213,312,231}, {321,231,312} hence T(3,3) = 8. (Here we are using the one-line notation for permutations, not the product of cycles form.)
Triangle starts:
1, 1;
1, 1;
1, 2, 1;
1, 4, 7, 8, 7, 4, 1;
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..880 (rows 0..6)

Crossrefs

Row lengths give A038507.

Cf. A000085.

Programs

PARI

\\ here b(n) is A000085(n).
b(n)={sum(k=0, n\2, n!/((n-2*k)!*2^k*k!))}
Row(n)={my(t=b(n)); vector(n!+1, k, k--; sum(i=0, k\2, binomial((n!-t)/2, i)*binomial(t, k-2*i)))}
{ for(n=0, 4, print(Row(n))) } \\ Andrew Howroyd, Feb 03 2021

Formula

T(n,k) = Sum( C((n! - I(n))/2, i)*C(I(n), k - 2*i) for i in [0..floor(k/2)]) where I(n) = A000085(n).