Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
2  
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
1  
@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
show 3 more comments

3 Answers

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

share|improve this answer
add comment

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

share|improve this answer
    
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
show 1 more comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.