login
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.
3

%I #14 Oct 12 2012 20:56:26

%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 m-th partition of n.

%C Partitions are in Abramowitz and Stegun ordering. First column is n. The n-th 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 3-cycle into a 1-cycle and a 2-cycle, and 3 more ways by combining both 3-cycles to produce three 2-cycles.

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

%Y Cf. A000041, A036039, A000085, A164342.

%K nonn,tabf

%O 1,2

%A _Wouter Meeussen_, Aug 13 2009

%E Typo fixed by _Franklin T. Adams-Watters_, Aug 29 2009