A164341 Irregular triangle read by rows: T(n,k) is the number of decompositions into involutions of a permutation that has a cycle structure given by the k-th partition of n.

1, 1, 2, 2, 3, 2, 4, 4, 3, 6, 4, 10, 5, 4, 6, 6, 6, 8, 26, 6, 5, 8, 12, 8, 6, 20, 12, 12, 20, 76, 7, 6, 10, 12, 10, 8, 12, 18, 16, 12, 20, 30, 24, 52, 232, 8, 7, 12, 15, 20, 12, 10, 12, 24, 24, 20, 16, 24, 18, 76, 40, 24, 40, 78, 60, 152, 764, 9, 8, 14, 18, 20, 14, 12, 15, 20, 30, 24, 54

Offset

0,3

Comments

Partitions are in Abramowitz and Stegun ordering (A036036). First column is n. The n-th row has A000041(n) columns.

If T(n,k) is multiplied by weighing factor A036039(n,k) (Triangle of multinomial coefficients "M_2") then the resulting rows sum to A000085(n)^2 (square of number of involutions).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..2713 (rows 0..20)

T. Kyle Petersen and Bridget Eileen Tenner, How to write a permutation as a product of involutions (and why you might care), arXiv:1202.5319 [math.CO], 2012.

Example

Triangle begins:
  0 | 1;
  1 | 1;
  2 | 2, 2;
  3 | 3, 2, 4;
  4 | 4, 3, 6, 4, 10;
  5 | 5, 4, 6, 6, 6, 8, 26;
  6 | 6, 5, 8, 12, 8, 6, 20, 12, 12, 20, 76;
  7 | 7, 6, 10, 12, 10, 8, 12, 18, 16, 12, 20, 30, 24, 52, 232;
  ...
T(7,7)= 12 since the partition 3;3;1 represents a cycle structure of a permutation that can be decomposed into involutions in 12 ways: 3*3=9 ways by splitting each 3-cycle into a 1-cycle and a 2-cycle, and 3 more ways by combining both 3-cycles to produce three 2-cycles.

Mathematica

Needs["DiscreteMath`Combinatorica`"]; countinvolutions[cyclestructure_List]:= Times@@ ( (Plus@@ Table[(2k)!/k!/2^k Binomial[ #2, 2k] #1^(#2-2k) #1^k, {k, 0, #2/2}]&) @@@ ({First@#, Length@#}& /@ Split[cyclestructure]) ); Table[countinvolutions /@ Reverse/@ Sort[Sort/@ Partitions[n]], {n, 10}]

Prog

(PARI)
B(n, e)=sum(k=0, n\2, binomial(n, 2*k)*e^(n-k)*(2*k)!/(k!*2^k))
C(sig)={my(S=Set(sig)); prod(k=1, #S, my(c=#select(t->t==S[k], sig)); B(c, S[k]))}
Row(n)={apply(C, [Vecrev(p) | p<-partitions(n)])}
{ for(n=0, 7, print(Row(n))) } \\ Andrew Howroyd, Oct 05 2025

Crossrefs

Cf. A000041 (row lengths), A036036, A036039, A000085, A164342 (row sums), A173869.

Sequence in context: A328405 A049822 A140060 * A333257 A334968 A124771

Adjacent sequences: A164338 A164339 A164340 * A164342 A164343 A164344

Keyword

nonn,tabf

Author

Wouter Meeussen, Aug 13 2009

Extensions

Typo fixed by Franklin T. Adams-Watters, Aug 29 2009

a(0)=1 prepended by Andrew Howroyd, Oct 05 2025

Status

approved