StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If you are interested only in the number the answer is combination with repetition of total + 1 elements 2nd class: Let me explain this: let us consider <code>total</code> number of 1s. They have <code>total + 1</code> gaps inbetween counting the gap before the first 1 and after the last one. You are trying to choose 3 numbers that sum up to total: we will do that by placing to separators in the gaps I just explained. The first number will be the sum of ones before the first separators, the second - the number of ones between the separators, the third - the remaining ones. Note that because we allow for the numbers to be zero we allow the separators to be placed in the same gap and also to be before the first 1 and after the last 1. This is exactly equivalent to "combination with repetition of total + 1 elements 2nd class" as I already said and is classical combinatorial problem. You can read about those kind of combinations <a href="http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition" rel="nofollow">here</a> but basically the answer will be ((total + 1) * (total + 2)) / 2. Btw I would suggest to retag this problem with at least algorithm tag.</p> <p><strong>EDIT</strong>: Following the request of further explanation, I will just illustrate all my thoughts with example (actually on the same example you gave in the question): we need to split 2 in three groups. 2 leads us to the number of ones we have to write: _1_1_. Here I have written the so-called-by-me gaps with '_'. Now, I will denote the two separators with '|'. Again the separators are used to determine what amount of 1s are used for the first, second and third number in the sum partition. On the left I write the combination using my notation and on the right the corresponding combination in your notation.</p> <pre><code>||_1_1_ -> 0, 0, 2 |_1|_1_ -> 0, 1, 1 |_1_1|_ -> 0, 2, 0 _1||_1_ -> 1, 0, 1 _1|_1|_ -> 1, 1, 0 _1_1||_ -> 2, 0, 0 </code></pre> <p>Now, hopefully you understand better what are separators and how they are used to determine what are the three numbers used in a combination. If you increase <code>total</code> the logic stays the same, but you will need to write more if you need to illustrate the case.</p> <p>Probably now you also understand why the gaps are <code>total + 1</code> and how each of the two separators can happen to be in each of these two gaps. all this leads us to the promised combination with repetition of <code>total + 1</code> elements of 2nd class.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload