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

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

1,2

Comments

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

If a(n,m) is multiplied by weighing factor A036039(n,m) (Triangle of multinomial coefficients "M_2") then the resulting rows add to A000085(n)^2 (square of count of involutions).

Links

Table of n, a(n) for n=1..78.

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

Example

Table begins 1; 2,2; 3,2,4; 4,3,6,4,10; 5,4,6,6,6,8,26; a(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}]

Crossrefs

Cf. A000041, A036039, A000085, A164342.

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

Status

approved