Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many (equivalence classes of) periodic functions $f : \mathbb{Z} \rightarrow \mathbb{Z}$, of period $N$, satisfy $$\sum_{i \le n \le j} f(n) \in \{-1,0,1\}$$ for all pairs of integers $(i,j)$?

I consider two functions equivalent if they are related by a simple shift, hence "(equivalence classes of)".

I wrote a computer program to count these functions for small values of $N$, and it spit out the first dozen terms of http://oeis.org/A008965 . However, I can't see any simple relationship between the things being counted there (necklaces of beads grouped into sets), and the things I'm counting (periodic functions with a certain property). So what I'm really asking is why the numbers of functions are the same as the numbers of necklaces, or in other words how to map one problem onto the other.

As an example, here are the 13 functions for $N=6$:

[1, 0, 0, 0, 0, -1], [0, 1, 0, 0, 0, -1], [1, -1, 1, 0, 0, -1], [0, 0, 1, 0, 0, -1], [1, 0, -1, 1, 0, -1], [0, 1, -1, 1, 0, -1], [1, -1, 0, 1, 0, -1], [0, 0, 0, 1, 0, -1], [1, -1, 1, -1, 1, -1], [0, 0, 1, -1, 1, -1], [0, 1, -1, 0, 1, -1], [0, 0, 0, 0, 1, -1], [0, 0, 0, 0, 0, 0]

and here are the 13 necklaces with 6 total beads:

(2, 3, 1), (2, 1, 1, 1, 1), (2, 2, 2), (2, 4), (3, 3), (4, 1, 1), (1, 1, 1, 1, 1, 1), (3, 1, 1, 1), (2, 2, 1, 1), (1, 5), (2, 1, 3), (6), (2, 1, 2, 1)

There are 13 of either, but I don't see how to put them in a natural 1-to-1 correspondence. And I'd be very surprised if it were just a coincidence, because the sequence matches up to 351, at which point my rather brute-force program started taking way too long.

share|improve this question
    
I think you are counting only half of them. In your example for $N=6$ the $1$ always comes before the $-1$. You can interchange the $1$'s and $-1$'s and obtain new solutions. This still leaves your question unanswered. –  Julián Aguirre Mar 28 '11 at 12:55
    
Ah, but the ones you get by doing that are equivalent by simple shifts to other ones on the list. For example, [-1,0,0,0,0,1] is equivalent to [0,0,0,0,1,-1], which appears second to last in the list. –  Keenan Pepper Mar 28 '11 at 20:47
add comment

1 Answer

up vote 5 down vote accepted

The correspondence seems to go like this: Keep track of the accumulated sums of your functions, and see how many steps you have to go from one point where the sum is zero until the next time the sum hits zero.

For example, your first function is [1, 0, 0, 0, 0, -1], and its partial sums are [0 (=empty sum), 1 (=1), 1 (=1+0), 1 (=1+0+0), 1, 1, 0], so from the first zero you have to wait six steps until the sum hits zero again. Hence this function corresponds to the necklace (6).

Your next function [0, 1, 0, 0, 0, -1] has sums [0, 0, 1, 1, 1, 1, 0]. From the starting zero you get another zero already after 1 step, and then the next zero appears 5 steps later. The necklace is (1,5) (or (5,1) if you wish).

In order, I get from your functions the necklaces (6) (15) (24) (114) (33) (123) (213) (1113) (222) (1122) (1212) (11112) (111111).

share|improve this answer
    
Excellent, that's the correspondence I'm looking for. I was getting so confused because my sets had some number of mirror pairs, and the sets of necklaces had some different number of mirror pairs. But this mapping doesn't map mirror pairs onto mirror pairs, so everything makes sense. –  Keenan Pepper Mar 28 '11 at 20:51
    
To clarify for anyone who might be confused: This correspondence is only well-defined if you rotate the periodic functions such that the first nonzero value is a +1, not a -1. Fortunately, the program I wrote happened to spit them out this way, but if you just have some random representations of the periodic functions, it won't work. For example, [-1,1,0,0,0,0] and [1,-1,0,0,0,0] both map to (21111). –  Keenan Pepper Mar 29 '11 at 19:20
    
Alternatively, you could require that the first nonzero value be a -1, in which case you get a different correspondence. The two constructions are "isomorphic" but not "canonically", because you have to choose arbitrarily between the two equally good mappings. –  Keenan Pepper Mar 29 '11 at 19:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.