|
%I #7 Jan 30 2020 04:43:07
%S 1,3,10,37,140,542,2118,8337,32963,130787,520095,2071679,8261137,
%T 32970855
%N The number of numerical sets with odd Frobenius number and no small atoms.
%C Definition using terminology of [MM]: A(k)' is the number of numerical sets S with Frobenius number 2k-1. This is denoted A_{2k-1}^\prime in [MM]. (1) A(k)' equals the number of subsets L of {1,2,...,2k-2} such that (L,L) is an admissible pair. (2) A(k)' equals the number of subsets L of {1,2,...,2k-2} such that for each x in L there is y in L such that x+y<2k and x+y is not an element of L. (3) Also equals the number of vertices at height k in the rooted tree shown in figure 4 of [MM]. (4) For large k, A(k)' is approximately equal to .4844 x 4^(k-1) [MM].
%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 The number of numerical sets with Frobenius number 2k and no small atoms equals 2A(k)' by theorem 11 of [MM]. This theorem also leads to a recursive connection with A(k) of A158448 by A(2k+1)' = 2A(2k)'-A(k)
%o (Other) program good ! This program calculates the cardinality of the number of numerical monoids without a small atom (or "good sets") for Frobenius number, $g$, as represented by $A_g'$ 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 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 4 of [MM].
%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. INTEGER*1, DIMENSION(21290000,50) :: G1, Gin INTEGER, DIMENSION(40) :: z INTEGER j, Mit, N1, N2, k, n, flag1
%o !Initialize z to be zero in every component. 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'$ as $g$ ranges from $1$ to $Mit+3$. At each stage of the iteration, we have $g=j+3$. Mit = 30
%o ! We begin with the good sets for $g=3$ given by $(1,0),(0,0),(1,1)$. We need these sets in order to run the algorithm suggested in the paper from the rooted tree in Figure 4 of [MM]. After each iteration of the code, $Gin$ will be redefined as the collection of good sets for $g = n+2$. If one wants to see the "good" sets for a specific g, one must print Gin after the iteration leading to that $g$. Gin(1,1) = 1 Gin(1,2) = 0 Gin(2,1) = 0 Gin(2,2) = 0 Gin(3,1) = 1 Gin(3,2) = 1
%o ! We determine the number, $z(g)$, of good sets for $g = 1,2,3$ for the implementation of the algorithm. In the notation of [MM], $z(g) = A_g'$. z(1) = 1 z(2) = 2 z(3) = 3
%o ! $N1$ will represent the number of good sets $A_g'$ 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^' = 3$. For $g=n$, we have $N2 = |{1,...,n-1}|=n-1$. N1 = 3 N2 = 2
%o ! Here we implement the algorithm by building and counting the good sets for $g=2n+1$ based on those that exist for $g=2n-1$. do j = 1,Mit flag1 = 0
%o ! If $g=2n$, we know from Theorem 11 of the paper that $z(2n)=2 z(2n-1)$. if (mod(j,2) == 1) then z(j+3) = 2*z(j+2) endif
%o ! If $g=2n+1$, we implement the algorithm discussed in [MM]. Mainly, we need to count $A_g'$. See Figure 4 for a pictoral reference. if (mod(j,2) == 0) then do k = 1,N1
%o ! Let $G$ be a symmetric good set for $g=2n-1$. If $G$ is not quadrivalent as defined in [MM], we can build good sets of size $ g=2n+1$ by adding $00$, $10$, and $11$ to the middle of the set as described in Figure 4 of [MM]. if (maxval(Gin(k,1:N2/2)-Gin(k,N2/2+1:N2)) <= 0) then do n = 1,N2/2 G1(flag1+1,n) = Gin(k,n) G1(flag1+2,n) = Gin(k,n) G1(flag1+3,n) = Gin(k,n) G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n) G1(flag1+2,N2/2+n+2) = Gin(k,N2/2+n) G1(flag1+3,N2/2+n+2) = Gin(k,N2/2+n) enddo G1(flag1+1,N2/2+1) = 0 G1(flag1+2,N2/2+1) = 1 G1(flag1+3,N2/2+1) = 1 G1(flag1+1,N2/2+2) = 0 G1(flag1+2,N2/2+2) = 0 G1(flag1+3,N2/2+2) = 1 flag1 = flag1+3 else do n = 1,N2/2
%o ! If $G$ is quadrivalent as defined in [MM], we can build further good sets of size of size $g=2n+1$ by adding $00$, $10$, $01$ and $11$ to the middle of the set as described in Figure 4 of [MM]. G1(flag1+1,n) = Gin(k,n) G1(flag1+2,n) = Gin(k,n) G1(flag1+3,n) = Gin(k,n) G1(flag1+4,n) = Gin(k,n) G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n) G1(flag1+2,N2/2+n+2) = Gin(k,N2/2+n) G1(flag1+3,N2/2+n+2) = Gin(k,N2/2+n) G1(flag1+4,N2/2+n+2) = Gin(k,N2/2+n) enddo G1(flag1+1,N2/2+1) = 0 G1(flag1+2,N2/2+1) = 1 G1(flag1+3,N2/2+1)
%o ! = 1 G1(flag1+4,N2/2+1) = 0 G1(flag1+1,N2/2+2) = 0 G1(flag1+2,N2/2+2) = 0 G1(flag1+3,N2/2+2) = 1 G1(flag1+4,N2/2+2) = 1 flag1 = flag1+4 endif enddo N1 = flag1 N2 = 2+j ! Here, we record the good sets, $Gin$, for the larger Frobenius number in order to move to the next stage of our algorithm. Gin(1:flag1,1:N2) = G1(1:flag1,1:N2) ! Here we record the number of good sets for $g=j+3$. z(j+3) = flag1 endif enddo ! Here we print the total number of good numerical sets as output of the code for each of our computed Frobenius numbers. write(*,*) z end program
%K nonn
%O 1,2
%A Jeremy L. Marzuola (marzuola(AT)math.uni-bonn.de), Aug 08 2009
|
