# Number of periodic integer functions with a certain property

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.

• 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