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

  • 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).2011-06-15
  • 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 `M2011-06-15
  • 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$.2011-06-15
  • 0
    @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.2011-06-15
  • 0
    @Arturo Magidin : colision :-)2011-06-15
  • 0
    @All The aim is to find out different in which N can be expressed satisfying above conditions. You can think of it as multi-set or collections, but that is not important. I want to calculate all such possible multi-sets or collections for give N.2011-06-15
  • 0
    In the examples, you say that the numbers have to add up to $N$. If this is part of the conditions, you should state it in the paragraph with the conditions, before the paragraph with the examples.2011-06-15
  • 0
    After rereading the question (and the answers) I correct my tentative definition: where I said 'at most one' I should say 'exactly one'2011-06-15

3 Answers 3