7
$\begingroup$

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

  • 0
    After rereading the question (and the answers) I correct my tentative definition: where I said 'at most one' I should say 'e$x$actly one'2011-06-15

3 Answers 3

7

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

5

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

  • 0
    @joriki: the OEIS page has both versions, which do contradict. I have put the other one in my response, as it appears to be correct2011-06-15
4

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

  • 0
    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)$$2011-06-16