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

[Brad Klee]

Hi Richard,

These type of triangles can be made from any set of generators, as in the
following:

http://ptpb.pw/ZA4X

where I give the example of a triangle for { cyclic(n) & transpositions(n)
} in Out[3]; though, I suppose this triangle is less interesting than the
other two as the generator set is not as simple as transpositions or
involutions.

The difficult part is computing the terms above brute force limit.

It could be helpful to have the row lengths ( ? ) .

Thanks,

Brad



On Mon, Dec 19, 2016 at 6:24 AM, Richard J. Mathar <mathar at mpia-hd.mpg.de>
wrote:

> 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 .
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>