login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A164047 The number of symmetric numerical sets with odd Frobenius number and no small atoms. 1
1, 1, 2, 3, 6, 10, 20, 37, 73, 139, 275, 533, 1059, 2075, 4126, 8134, 16194, 32058, 63910, 126932, 253252, 503933, 1006056, 2004838, 4004124, 7987149, 15957964, 31854676, 63660327, 127141415, 254136782, 507750109 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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].

REFERENCES

J. Marzuola and A. Miller. "Counting numerical sets with no small atoms." To appear in Journal of Combinatorial Theory: A.

LINKS

Table of n, a(n) for n=1..32.

J. Marzuola and A. Miller, Counting Numerical Sets with No Small Atoms

FORMULA

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

PROG

(Other) program good ! 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). ! 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.

!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^\sigma'$ as $g$ ranges from $1$ to $Mit+3$. At each stage of the iteration, we have $g=j+3$. Mit = 24

! 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$. Gin(1, 1) = 1 Gin(1, 2) = 0

! 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'$. z(1) = 1 z(2) = 1 z(3) = 1

! $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$. N1 = 1 N2 = 2

! Here we implement the algorithm by building 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 19 of the paper that $z(2n)=z(2n-1)$. if (mod(j, 2) == 1) then z(j+3) = z(j+2) endif

! 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. if (mod(j, 2) == 0) then do k = 1, N1

! 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]. 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+1, N2/2+n+2) = Gin(k, N2/2+n) G1(flag1+2, N2/2+n+2) = Gin(k, N2/2+n) enddo G1(flag1+1, N2/2+1) = 1 G1(flag1+2, N2/2+1) = 0 G1(flag1+1, N2/2+2) = 0 G1(flag1+2, N2/2+2) = 1 flag1 = flag1+2 endif else do n = 1, N2/2

! 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]. G1(flag1+1, n) = Gin(k, n) G1(flag1+1, N2/2+n+2) = Gin(k, N2/2+n) enddo G1(flag1+1, N2/2+1) = 1 G1(flag1+1, N2/2+2) = 0 flag1 = flag1+1 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 symmetric numerical sets as output of the code for each of our computed Frobenius numbers. write(*, *) z end program

CROSSREFS

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.

Sequence in context: A171682 A066062 A008929 * A158291 A045690 A007148

Adjacent sequences:  A164044 A164045 A164046 * A164048 A164049 A164050

KEYWORD

nonn

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 21 02:23 EDT 2017. Contains 289629 sequences.