cp's OEIS Frontend

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

%I A226356 #24 Mar 14 2020 07:05:23
%S A226356 0,0,1,2,3,10,20,91,207,792,2589,17749,52997
%N A226356 Number of representations of the n-th factorial group as a (nondecreasing) product of (nontrivial) cyclic groups.
%C A226356 The algorithm given which generates and counts a(n) goes as follows:
%C A226356 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}.
%C A226356 2. Place the above multiset at the top of a (ranked) poset, row 0.
%C A226356 3. Set i=0.
%C A226356 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.
%C A226356 5. Find the number of representations generated.
%F A226356 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.
%e A226356 Note: in the following ~= denotes isomorphism.
%e A226356 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.
%e A226356 However G_2~=Z_2 is the only such representation of G_2.
%e A226356 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:
%e A226356 *Z_2 x Z_3 x Z_4 x Z_5,
%e A226356 *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
%e A226356 *Z_6 x Z_20, Z_4 x Z_30, Z_10 x Z_12, Z_2 x Z_60.
%e A226356 Hence, a(5)=10.
%o A226356 (Sage)
%o A226356 #NOTE: by uncommenting the second return argument, the reader is given the array of representations.
%o A226356 def d_split(prod):
%o A226356     p_counts={}
%o A226356     for term in prod:
%o A226356         for p, m in term.factor():
%o A226356             pm = p^m
%o A226356             if pm in p_counts:
%o A226356                 p_counts[pm]+=1
%o A226356             else:
%o A226356                 p_counts[pm]=1
%o A226356     return p_counts
%o A226356 def factorial_group_reps(m):
%o A226356     if m<2:
%o A226356         return 0
%o A226356     i=0
%o A226356     widest_rep=d_split([Integer(n) for n in range(1,m+1)])
%o A226356     w_max=sum([widest_rep[p] for p in widest_rep])
%o A226356     rep_poset=[[widest_rep]]
%o A226356     r_count=1
%o A226356     while w_max-i>m//2:
%o A226356         row_new=[]
%o A226356         for rep in rep_poset[i]:
%o A226356             for [a,b] in Combinations(rep,2):
%o A226356                 if gcd([a,b])==1:
%o A226356                     rep_new=rep.copy()
%o A226356                     if rep_new[a]==1:
%o A226356                         rep_new.pop(a)
%o A226356                     else:
%o A226356                         rep_new[a]-=1
%o A226356                     if rep_new[b]==1:
%o A226356                         rep_new.pop(b)
%o A226356                     else:
%o A226356                         rep_new[b]-=1
%o A226356                     if a*b in rep_new:
%o A226356                         rep_new[a*b]+=1
%o A226356                     else:
%o A226356                         rep_new[a*b]=1
%o A226356                     if not rep_new in row_new:
%o A226356                         r_count+=1
%o A226356                         row_new.append(rep_new)
%o A226356         rep_poset.append(row_new)
%o A226356         i+=1
%o A226356     return r_count#,rep_poset
%o A226356 for i in range(11):
%o A226356     # for i>10, a(i) is a very tedious computation for this algorithm
%o A226356     print(i,factorial_group_reps(i))
%K A226356 nonn,more
%O A226356 0,4
%A A226356 _Alexander Riasanovsky_, Jun 04 2013
%E A226356 a(11) and a(12) added by _Alexander Riasanovsky_, Jun 06 2013