

A226356


Number of representations of the nth factorial group as a (nondecreasing) product of (nontrivial) cyclic groups.


0



0, 0, 1, 2, 3, 10, 20, 91, 207, 792, 2589, 17749, 52997
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 ith row which, generate the (i+1)th row of elements: those which are coarsed from elements on the ith 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_(i1) 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: each . should be replaced by a tab (4 spaces)
#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 list(term.factor()):
...if p^m in p_counts:
....p_counts[p^m]+=1
...else:
....p_counts[p^m]=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_maxi>floor(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 A252865 A252868
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



