Perhaps an even more interesting question would be, what if the set S of forbidden spacings is infinite? In the case where S is finite, then the dynamic programming method shows that F grows linearly with N when N becomes large (if nonzero). But if S is infinite, for example S is the set of all positive squares, then the asymptotics of F(N,S) for large N become nonobvious, and the computational complexity also nonobvious. (Well, it wasn't obvious even for finite S, but at least a decent upper bound on that complexity was easy to see.) ------------------------- Now returning to the finite-S question, a totally different kind of attack is motivated by considering polynomials. Regard a set {A,B,C...} of nonnegative integers as being specified by the polynomial P(x)=x^A+x^B+x^C+... Now the condition that the polynomial P(x) be free of forbidden spacings from the set S, can be written in a number of ways. One is to note that P(x) * P(1/x) generates the set of spacings in P(x), along with their counts, e.g. a monomial A*x^B would mean "spacing B occurs A times." And P(x)*Q(x) where Q(x) is the generator polynomial for the set S, tells us forbidden locations for the next-larger element to add to the set F. If you wanted the distance D>0 to be forbidden, you could, e.g. demand that integral P(z)*P(1/z)*z^(-D-1) dz = 0 where the path of integration is a small circle surrounding 0. If you wanted the distances D in set S forbidden, demand Sum(D in S) |integral(round small circle) P(z)*P(1/z)*z^(-D-1) dz|^2 = 0. So then we have what looks more like a question in analysis rather than combinatorics. Is this polynomial trick of any use? I do not know. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)