OFFSET
1,2
COMMENTS
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].
LINKS
J. Marzuola and A. Miller, Counting Numerical Sets with No Small Atoms, arXiv:0805.3493 [math.CO], 2008.
J. Marzuola and A. Miller, Counting numerical sets with no small atoms, J. Combin. Theory A 117 (6) (2010) 650-667.
FORMULA
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)
PROG
(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).
! 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].
!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.
!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
!Initialize z to be zero in every component. do j = 1, 40 z(j) = 0 enddo
! $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
! 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
! 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
! $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
! 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
! 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
! 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
! 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
! 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)
! = 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
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeremy L. Marzuola (marzuola(AT)math.uni-bonn.de), Aug 08 2009
STATUS
approved