[seqfan] Generating the symmetric group with minimal products of involutions

[Richard J. Mathar]

Here is another triangular (keyword:tabf) sequence that may be
missing and of interest to the OEIS:

The number of elements of the symmetric group S_n that can be
generated as a product of k involutions starting from the unit
element, i.e. starting from the permutation (1,2,3....n).
We construct each element of the permutation group S_n as 
  invo(1)*invo(2)*...invo(k)*(1,2,3,...n),
minimizing k, the involutions not necessarily distinct, and build a histogram of
how many elements of S_n have the same k.
The number of involutions invo(.) which may be factors in the construction
is A001189(n). 

That number triangle T(n,k) has row sums A000142(n) = n! and should start at n=1 , k>=0 as
1: 1 ;
2: 1 1 ;
3: 1 3 2 ;
4: 1 9 14 ;
5: 1 25 94 ;
6: 1 75 644 ;
7: 1 231 4808 ;
8: 1 763 39556 ;
9: 1 2619 ...

The column k=0 is always 1: the unit element is obtained
by not using any product with any involution. 
The column k=1 is A001189, counting the involutions themselves.
The sum of the remaining columns k>=2 is A066052.

T(n,0)=1.
T(n,1)=A001189(n).
sum_{k>=2} T(n,k)=A066052(n).
sum_{k>=0} T(n,k)=A000142(n).

There is a related entry A094638: the number of transpositions needed
to generate all elements of the permutation group S_n: see the comment
of Petersen from October 2008 .