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,6

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.

Links

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

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

Example

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;

Prog

(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

Crossrefs

Row lengths give A038507.

Cf. A000085.

Sequence in context: A265232 A011016 A096540 * A111569 A371926 A213786

Adjacent sequences: A277078 A277079 A277080 * A277082 A277083 A277084

Keyword

nonn,tabf

Author

Christian Bean, Sep 28 2016

Status

approved