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

Author

Wouter Meeussen, Aug 13 2009

Keywords

• nonn
• tabf

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

Examples

			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.
		

Links

• 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

Crossrefs

Cf. A000041, A036039, A000085, A164342.

Programs

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}]

Extensions

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