

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 mth partition of n.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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


MATHEMATICA

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


CROSSREFS

Cf. A000041, A036039, A000085, A164342.
Sequence in context: A088936 A049822 A140060 * A124771 A066589 A007897
Adjacent sequences: A164338 A164339 A164340 * A164342 A164343 A164344


KEYWORD

nonn,tabf


AUTHOR

Wouter Meeussen, Aug 13 2009


EXTENSIONS

Typo fixed by Franklin T. AdamsWatters, Aug 29 2009


STATUS

approved



