0
$\begingroup$

My question is as follows: let there be $n$ different numbers $a_i$ in a set $A$, where each $a_i$ is a number between 0 and 1. How many different sets of values can I have that fulfill the condition $$\sum_{i=1}^{n} a_i=1$$ if the values of each $a_i$ may take on any of $k$ different values in the domain [0,1]? Does there exist a general formula to calculate this quantity? I have tried looking at formulas for numbers of combinations but run into trouble when trying to include the sum constraint.

(e.g. if allowed values of $a_i$ are $0, 0.25, 0.5, 0.75, 1$, then $k=5$).

Apologies in advance if I have used mathematical vocabulary inappropriately. Any advice on this matter would be much appreciated.

EDIT: values may be repeated

EDIT 2: Order does matter, e.g. {0.5, 0.5, 0} is distinct from {0.5,0,0.5}

$\endgroup$
  • $\begingroup$ In your example, suppose that $n=3$ and $k=5$. Is $0.5+0.5+0$ to be considered a different solution from $0.5+0+0>5$? $\endgroup$ – André Nicolas Jun 30 '15 at 4:30
  • $\begingroup$ In your second expression how is 0.5 > 5 ? $\endgroup$ – NewDogOldTricks Jun 30 '15 at 5:20
  • 1
    $\begingroup$ Sorry, typo, I meant $0.5+0+0.5$. In other words, does order matter? The intended $0.5$ turned into $0>5$, through the magic of the shift key. $\endgroup$ – André Nicolas Jun 30 '15 at 5:23
  • $\begingroup$ Ah yes, good question. Order does matter. $\endgroup$ – NewDogOldTricks Jun 30 '15 at 5:24
  • $\begingroup$ If you were looking for integer values for $a_i$, then the concept of "Integer Partitioning" would apply. However with $a_i$<1, I don't think there would be a closed form for the different number of ways. $\endgroup$ – NoChance Jun 30 '15 at 5:28
0
$\begingroup$

If you want lots of sets the values must be rational (maybe times one irrational). In your example, it would be equivalent to ask about subsets of $\{0,1,2,3,4\}$ that sum to $4$. In your case $4$ can be achieved $5$ ways: $1+1+1+1,1+1+2,1+3,2+2,4$. If you allow different orders it becomes $8$. If you allow $0$ there are infinitely many, as you can have as many zeros as you like. Not allowing $0$ these are the compositions of $n$. There are $2^{n-1}$ of them, which you can see by a stars and bars argument. Put $n$ stars in a row. There are $n-1$ places between them were you can choose to put a bar or not. Each set of bars gives a composition.

$\endgroup$
  • $\begingroup$ (1) yes, 0 is allowed. (2) values may be repeated. Would this change what you said above? $\endgroup$ – NewDogOldTricks Jun 30 '15 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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