login
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.
2
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
KEYWORD
nonn,tabf
AUTHOR
Christian Bean, Sep 28 2016
STATUS
approved