A226356 Number of representations of the n-th factorial group as a (nondecreasing) product of (nontrivial) cyclic groups.

0, 0, 1, 2, 3, 10, 20, 91, 207, 792, 2589, 17749, 52997

Offset

0,4

Comments

The algorithm given which generates and counts a(n) goes as follows:

1. Consider the product [1,2,3,...,n] as Z_1 x Z_2 x ... x Z_n and "refine" wherever possible to create a multiset. For example, Z_6 ~= Z_2 x Z_3, so [1,2,3,4,5,6] refines as the multiset [2,2,3,3,4,5] or {2:2,3:2,4:1,5:1}.

2. Place the above multiset at the top of a (ranked) poset, row 0.

3. Set i=0.

4. While there exists an element on the i-th row which, generate the (i+1)-th row of elements: those which are coarsed from elements on the i-th row.

5. Find the number of representations generated.

Links

Table of n, a(n) for n=0..12.

Formula

With Z_k denoting the cyclic group on k letters, let G_0:=Z_1 and for all positive integers i, set G_i:=G_(i-1) x Z_i. Then a(n) is the number of (isomorphic) representations of G_n as a (nondecreasing) product of (nontrivial) cyclic groups.

Example

Note: in the following ~= denotes isomorphism.
For example, G_0=Z_1 which cannot be represented as a product of nontrivial cyclic groups. Hence, a(0)=0. Likewise, G_1=G_0 x Z_1~=Z_1, so a(1)=0.
However G_2~=Z_2 is the only such representation of G_2.
For G_5=Z_1 x Z_2 x Z_3 x Z_4 x Z_5, we have exactly the following representations, sorted by the number of terms:
*Z_2 x Z_3 x Z_4 x Z_5,
*Z_4 x Z_5 x Z_6, Z_3 x Z_4 x Z_10, Z_2 x Z_5 x Z_12, Z_2 x Z_4 x Z_15, Z_2 x Z_3 x Z_20, and
*Z_6 x Z_20, Z_4 x Z_30, Z_10 x Z_12, Z_2 x Z_60.
Hence, a(5)=10.

Prog

(Sage)
#NOTE: by uncommenting the second return argument, the reader is given the array of representations.
def d_split(prod):
    p_counts={}
    for term in prod:
        for p, m in term.factor():
            pm = p^m
            if pm in p_counts:
                p_counts[pm]+=1
            else:
                p_counts[pm]=1
    return p_counts
def factorial_group_reps(m):
    if m<2:
        return 0
    i=0
    widest_rep=d_split([Integer(n) for n in range(1, m+1)])
    w_max=sum([widest_rep[p] for p in widest_rep])
    rep_poset=[[widest_rep]]
    r_count=1
    while w_max-i>m//2:
        row_new=[]
        for rep in rep_poset[i]:
            for [a, b] in Combinations(rep, 2):
                if gcd([a, b])==1:
                    rep_new=rep.copy()
                    if rep_new[a]==1:
                        rep_new.pop(a)
                    else:
                        rep_new[a]-=1
                    if rep_new[b]==1:
                        rep_new.pop(b)
                    else:
                        rep_new[b]-=1
                    if a*b in rep_new:
                        rep_new[a*b]+=1
                    else:
                        rep_new[a*b]=1
                    if not rep_new in row_new:
                        r_count+=1
                        row_new.append(rep_new)
        rep_poset.append(row_new)
        i+=1
    return r_count#, rep_poset
for i in range(11):
    # for i>10, a(i) is a very tedious computation for this algorithm
    print(i, factorial_group_reps(i))

Crossrefs

Sequence in context: A089791 A297872 A298135 * A141050 A354720 A252865

Adjacent sequences: A226353 A226354 A226355 * A226357 A226358 A226359

Keyword

nonn,more

Author

Alexander Riasanovsky, Jun 04 2013

Extensions

a(11) and a(12) added by Alexander Riasanovsky, Jun 06 2013

Status

approved