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
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
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
Comments