4
$\begingroup$

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.

  • 0
    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.2011-03-28

1 Answers 1

5

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

  • 0
    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.2011-03-29