%I
%S 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,
%T 6,10,12,10,8,12,18,16,12,20,30,24,52,232,8,7,12,15,20,12,10,12,24,24,
%U 20,16,24,18,76,40,24,40,78,60,152,764,9,8,14,18,20,14,12,15,20,30,24,54
%N Irregular triangle read by rows: a(n,m) counts the decompositions into involutions of a permutation that has a cycle structure given by the mth partition of n.
%C Partitions are in Abramowitz and Stegun ordering. First column is n. The nth row has A000041(n) columns.
%C 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).
%H T. Kyle Petersen and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/1202.5319">How to write a permutation as a product of involutions (and why you might care)</a>, arXiv:1202.5319, 2012
%e 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 3cycle into a 1cycle and a 2cycle, and 3 more ways by combining both 3cycles to produce three 2cycles.
%t Needs["DiscreteMath`Combinatorica`"]; countinvolutions[cyclestructure_List]:= Times@@ ( (Plus@@ Table[(2k)!/k!/2^k Binomial[ #2,2k] #1^(#22k) #1^k,{k,0,#2/2}]&) @@@ ({First@#,Length@#}& /@ Split[cyclestructure]) ); Table[countinvolutions /@ Reverse/@ Sort[Sort/@ Partitions[n]],{n,10}]
%Y Cf. A000041, A036039, A000085, A164342.
%K nonn,tabf
%O 1,2
%A _Wouter Meeussen_, Aug 13 2009
%E Typo fixed by _Franklin T. AdamsWatters_, Aug 29 2009
