login
The number of symmetric numerical sets with odd Frobenius number and no small atoms.
4

%I #22 Sep 13 2023 08:35:36

%S 1,1,2,3,6,10,20,37,73,139,275,533,1059,2075,4126,8134,16194,32058,

%T 63910,126932,253252,503933,1006056,2004838,4004124,7987149,15957964,

%U 31854676,63660327,127141415,254136782,507750109,1015059238,2028564292,4055812657,8107052520

%N The number of symmetric numerical sets with odd Frobenius number and no small atoms.

%C Definition using terminology of [MM]: Asigma(k)' is the number of symmetric numerical sets S with Frobenius number 2k-1. This is denoted A^\sigma_{2k-1}^\prime in [MM]. Asigma(k)' equals the number of sigma-admissible subsets L of {1,2,...,2k-2} such that if x is an element of M then 2k-1-x is not an element of M. It also equals the number of vertices at height k in the rooted tree shown in figure 5 of [MM]. For large k, Asigma(k)' is approximately equal to .23065 x 2^(k-1) [MM]. The number of symmetric numerical sets with Frobenius number 2k and no small atoms equals Asigma(k)' by theorem 19 of [MM].

%H Martin Fuller, <a href="/A164047/b164047.txt">Table of n, a(n) for n = 1..66</a>

%H J. Marzuola and A. Miller, <a href="http://arxiv.org/abs/0805.3493">Counting Numerical Sets with No Small Atoms</a>, arXiv:0805.3493 [math.CO], 2008.

%H J. Marzuola and A. Miller, <a href="https://doi.org/10.1016/j.jcta.2010.03.002">Counting numerical sets with no small atoms</a>, J. Combin. Theory A 117 (6) (2010) 650-667.

%F This theorem also provides a recursive connection with Asigma(k) from A158449: Asigma(2k+1)' = 2*Asigma(2k)' - Asigma(k).

%o (FORTRAN)

%o program good

%o ! This program calculates the cardinality of the number of symmetric numerical monoids without a small atom (or symmetric "good sets") for Frobenius number, $g$, as represented by $A_g^\sigma'$ defined in "Counting numerical sets with no small atoms" ([MM]) by Jeremy L. Marzuola and Andy Miller (to appear in Journal of Combinatorial Theory: A).

%o ! Here we set the parameters of computation. We represent a numerical set by binary representations of the elements below the Frobenius number. Namely, a $0$ means an element is not in a set and a $1$ means an element is in the set. The symmetric numerical sets will be stored in an array called $Gin$, which will be redefined for each $g$ for the purposes of iterating the algorithm. Each row of Gin corresponds to a numerical set, e.g. the row $Gin(3,-)=(1,1,0,1,0,0)$ would determine the numerical set ${1,2,4} \cup N_5$. This is a slight variation of the notation presented in Figure 5 of [MM], where only the initial half segment is presented since the remainder is clear by symmetry.

%o !The dimension here is limited only by the memory of the author's computers. With greater computational ability, you would be able to larger values of $g$.

%o !Generically we need only take the dimension of $z$ to be $Mit+3$.

%o INTEGER*1, DIMENSION(21290000,50) :: G1, Gin

%o INTEGER, DIMENSION(40) :: z

%o INTEGER j, Mit, N1, N2, k, n, flag1

%o !Initialize z to be zero in every component.

%o do j = 1,40 z(j) = 0 enddo

%o ! $Mit$ is the number of times we iterate our algorithm. Since we begin with $g=3$, the resulting output will print out $A_g^\sigma'$ as $g$ ranges from $1$ to $Mit+3$. At each stage of the iteration, we have $g=j+3$.

%o Mit = 24

%o ! We begin with the symmetric good sets for $g=3$ given by only $(1,0)$. We need these sets in order to run the algorithm suggested in the paper from the rooted tree in Figure 5 of [MM]. After each iteration of the code, $Gin$ will be redefined as the collection of symmetric good sets for $g = n+2$. If one wants to see the symmetric "good" sets for a specific $g$, one must print $Gin$ after the iteration leading to that $g$.

%o Gin(1,1) = 1

%o Gin(1,2) = 0

%o ! We determine the number, $z(g)$, of symmetric good sets for $g = 1,2,3$ for the implementation of the algorithm. In the notation of [MM], $z(g) = A_g^\sigma'$.

%o z(1) = 1

%o z(2) = 1

%o z(3) = 1

%o ! $N1$ will represent the number of symmetric good sets $A_g^\sigma'$ for Frobenius number $g$ and $N2$ is the size of the numerical sets themselves for the given $g$. Here we begin with $g = 3$, so $N1 = A_3^\sigma' = 1$. For $g=n$, we have $N2 = |{1,...,n-1}|=n-1$.

%o N1 = 1

%o N2 = 2

%o ! Here we implement the algorithm by building the good sets for $g=2n+1$ based on those that exist for $g=2n-1$.

%o do j = 1,Mit

%o flag1 = 0

%o ! If $g=2n$, we know from Theorem 19 of the paper that $z(2n)=z(2n-1)$.

%o if (mod(j,2) == 1) then

%o z(j+3) = z(j+2)

%o endif

%o ! If $g=2n+1$, we implement the algorithm discussed in [MM]. Mainly, we need to count $A_g^\sigma'$. See Figure 5 for a pictoral reference to this algorithm.

%o if (mod(j,2) == 0) then

%o do k = 1,N1

%o ! Let $G$ be a symmetric good set for $g=2n-1$. If $G$ is bivalent, we can build good sets of size of size $2n+1$ by adding $01$, $10$ to the middle of the set as described in Figure 5 of [MM].

%o if (maxval(Gin(k,1:N2/2)-Gin(k,N2/2+1:N2)) > 0) then

%o do n = 1,N2/2

%o G1(flag1+1,n) = Gin(k,n)

%o G1(flag1+2,n) = Gin(k,n)

%o G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n)

%o G1(flag1+2,N2/2+n+2) = Gin(k,N2/2+n)

%o enddo

%o G1(flag1+1,N2/2+1) = 1

%o G1(flag1+2,N2/2+1) = 0

%o G1(flag1+1,N2/2+2) = 0

%o G1(flag1+2,N2/2+2) = 1

%o flag1 = flag1+2

%o !erroneous? endif

%o else

%o do n = 1,N2/2

%o ! If $G$ is not bivalent, we can build further good sets for $g=2n+1$ by adding $10$ to the middle of the set as described in Figure 5 of [MM].

%o G1(flag1+1,n) = Gin(k,n)

%o G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n)

%o enddo

%o G1(flag1+1,N2/2+1) = 1

%o G1(flag1+1,N2/2+2) = 0

%o flag1 = flag1+1

%o endif

%o enddo

%o N1 = flag1

%o N2 = 2+j

%o ! Here we record the good sets, $Gin$, for the larger Frobenius number in order to move to the next stage of our algorithm.

%o Gin(1:flag1,1:N2) = G1(1:flag1,1:N2)

%o ! Here we record the number of good sets for $g=j+3$.

%o z(j+3) = flag1

%o endif

%o enddo

%o ! Here we print the total number of good symmetric numerical sets as output of the code for each of our computed Frobenius numbers.

%o write(*,*) z

%o end program

%o ! Edited by _M. F. Hasler_, Jan 31 2020

%Y Asigma(k)' is the same as the number of additive 2-bases for k-1 as described in A008929 and A066062. Related to Asigma(k) in A158449.

%K nonn

%O 1,3

%A Jeremy L. Marzuola (marzuola(AT)math.uni-bonn.de), Aug 08 2009

%E a(33) onwards from _Martin Fuller_, Sep 13 2023