# Number of possible sets for given N

How many possible valid collections are there for a given positive integer N given the following conditions:

All the sums from 1 to N should be possible to be made by selecting some of the integers. Also this has to be done in way such that if any integer from 1 to N can be made in more than one way by combining other selected integers then that set of integers is not valid.

For example, with N = 7, The valid collections are:{1,1,1,1,1,1,1},{1,1,1,4},{1,2,2,2},{1,2,4} Invalid collections are: {1,1,1,2,2} because the sum adds up to 7 but 2 can be made by {1,1} and {2}, 3 can be made by {1,1,1} and {1,2}, 4 can be made by {1,1,2} and {2,2} and similarly 5, 6 and 7 can also be made in multiple ways using the same set. {1,1,3,6} because all from 1 to 7 can be uniquely made but the sum is not 7 (its 11).

-
1: very confusing wording. 2: sets cannot have repeating elements. You mean "collections" or "tuples" (I am not sure about the correct mathematical term actually). – trutheality Jun 15 '11 at 18:47
To clarify: we want to count the number of (say) 'proper partitions of N'. A 'proper partition' is a (standard) partition of N that includes at most one (standard) partition for all M<N . – leonbloy Jun 15 '11 at 18:54
@trutheality: you can use "multisets". But here it is better to say that you have a "partition of $N$" with the property that it contains a unique partition of $k$ for each $k$, $1\leq k\leq N$. – Arturo Magidin Jun 15 '11 at 18:54
@trutheality: One term for "set" with repetitions is multiset. Or one can order the component objects in some arbitrary way (in this problem there is a natural order), and identify a multiset with a non-decreasing sequence. – André Nicolas Jun 15 '11 at 18:55
@Arturo Magidin : colision :-) – leonbloy Jun 15 '11 at 18:55

These are perfect partitions given in OEIS. a(n-1) = sum of all a(i-1) such that i divides n and i < n.

-

The term I would use is "multiset". Note that your multiset must contain 1 (as this is the only way to get a sum of 1). Suppose there are $r$ different values $a_1 = 1, \ldots, a_r$ in the multiset, with $k_j$ copies of $a_j$. Then we must have $a_j = (k_{j-1}+1) a_{j-1}$ for $j = 2, \ldots, r$, and $N = (k_r + 1) a_r - 1$. Working backwards, if $A(N)$ is the number of valid multisets summing to $N$, for each factorization $N+1 = ab$ where $a$ and $b$ are positive integers with $b > 1$ you can take $a_r = a$, $k_r = b - 1$, together with any valid multiset summing to $a-1$. Thus $A(N) = \sum_{b | N+1, b > 1} A((N+1)/b - 1)$ for $N \ge 1$, with $A(0) = 1$. We then have, if I programmed it right, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3 for $N$ from 1 to 20. This matches OEIS sequence A002033, "Number of perfect partitions of n".

-
I got the same result. It seems this shows that the result in OEIS that Ross quoted has the indices off by $1$? – joriki Jun 15 '11 at 19:45
@joriki: I think the OEIS entry starts with 1 partition of 0 – Ross Millikan Jun 15 '11 at 19:56
@joriki: the OEIS sequence starts from zero. – trutheality Jun 15 '11 at 19:59
@Ross: It does. I don't see how that's relevant, though. That doesn't change the fact that $a(3)=a(4/2-1)+a(4/4-1)=a(1)+a(0)=1+1=2$ and $a(3)\neq a(1)=1$, which is what the result you quoted would give. – joriki Jun 15 '11 at 20:02
@Ross: To make the two results coincide, all the indices would have to be shifted by $1$. They don't get shifted by $1$ just because a value for $a(0)$ is prepended to the sequence. – joriki Jun 15 '11 at 20:15

Suppose your collection contains a finite set of distinct numbers $\{n_1 ... n_k\}$ and that the collection contains the number $n_i$ $t_i$ times (you can also suppose that the $n_i$ are sorted) Then your condition is that for every number $x$ between 0 and $N$, $x$ can be written as $x = \Sigma u_i n_i$ with $0 \leq u_i \leq t_i$ in exactly one way.

This is possible if and only if $n_1 = 1$, forall $i$, $n_i = \Sigma_{j\lt i} t_i n_i$, and $N = \Sigma t_i n_i$.

You can prove this by doing an induction on $k$, starting at $k=N=0$ for the base case. The base case is easy. The induction case is not difficult :

If you have a valid collection containing $k$ distinct terms that can make all numbers up to $N_k$, then the only way to extend it into a bigger collection is by adding $n_{k+1} = N_k+1$. If you pick a smaller number, then $n_{k+1}$ can be written in two ways, if you pick a bigger number, then you can not make $N_k+1$. And then, if you have a valid collection made of $k+1$ terms, then the sub-collection containing the first $k$ distinct terms is also valid and has to write every number up to $n_{k+1}-1$ for the same kind of reasons.

Thus, a valid collection of $k$ distinct terms that makes every number up to $N$ is determined by the sequence $(n_1=1, \ldots n_k, n_{k+1}=N+1)$ where $n_i$ divides $n_{i+1}$ : $$n_i = \Sigma_{j \lt i} t_j n_j = n_{i-1} + t_{i-1} n_{i-1} = (t_{i-1} + 1) n_{i-1}$$ So this shows why they are successives multiples of each other and how to recover the $t_i$ from the sequence.

The 4 collections you gave as an example correspond respectively to the sequences $(1,8), (1,2,8), (1,4,8), (1,2,4,8)$.

The number of valid sequences depends on the exponents in the prime decomposition of $N+1$ : if $N+1$ is a prime power $p^a$, then there are exactly $2^{a-1}$ valid sequences, since you have to choose wether you pick $p^i$ or not for $0 \lt i \lt a$.

If $N+1$ has several prime divisors, I don't think there is a nice formula giving the number of valid collections from the multiset of exponents in the prime factorisation of $N+1$.

-
If the prime factorization of $N+1$ is $\prod_{i=1}^n p_i^{m_i}$, then $A(N) = f(m_1,\ldots,m_n)$ is the number of paths in ${\mathbb Z}^n$ from $(0,\ldots,0)$ to $(m_1,\ldots,m_n)$ where each step is a nonzero vector with nonnegative integer entries. In particular for $n=2$, $f(m_1, m_2) = \sum_{j=\max(m_1,m_2)-1}^{m_1+m_2} {m_1 \choose {j+1-m_2}} {m_2 \choose {j + 1 - m_1}}$, which I think is $2^{m_1 - 1} {m_1 \choose {m_1 - m_2}} {}_2F_1(-m_2,-m_2; m_1 + 1 - m_2; 2)$\$ – Robert Israel Jun 16 '11 at 4:40