StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<pre><code>{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } </code></pre> <p>Here you are choosing four numbers from ten and they can be any order. Thus the solution is </p> <pre><code>(10 choose 4) * 4! = 5040. </code></pre> <p>Now we consider the case of</p> <pre><code>{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 } </code></pre> <p>There are a few combinations here. We can have zero 1s, one 1 or two 1s. In the first case there are </p> <pre><code>(8 choose 4) * 4! </code></pre> <p>possible combinations. In the second case there are</p> <pre><code>(8 choose 3) * 4! </code></pre> <p>possible combinations. In the third case there are </p> <pre><code>(8 choose 2) * 4! / 2! </code></pre> <p>possible combinations. This last one requires explanation. There are eight possible non 1 digits to choose from and we are choosing two. The two remaining digits are 1s (by assumption that we are in the case where are our 4-string contains two 1s). We can put these four digits in any order however the 1s are interchangeable so we divide by the number of possible orderings of the 1s (2!).</p> <p>Thus the answer is </p> <pre><code>(8 choose 4) * 4! + (8 choose 3) * 4! + (8 choose 2) * 4! / 2! = 3360. </code></pre> <p>For the case of</p> <pre><code>{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 } </code></pre> <p>there are again a few combinations. We can have zero 1s and zero 2s, one 1 and zero 2s, two 1s and zero 2s, two 1s and one 2, two 1s and two 2s, zero 1s and one 2, zero 1s and two 2s, one 1 and two 2s, and one 1 and one 2. These can be worked out as above and the final answer is</p> <pre><code>(6 choose 4) * 4! + 2 * (6 choose 3) * 4! + 2 * (6 choose 2) * 4! / 2! + (6 choose 2) * 4! + 2 * (6 choose 1) * 4! / 2! + (6 choose 0) * 4! / (2! * 2!) = 2190. </code></pre> <p>This a fairly simplistic approach to problems of this sort. There are others (for example, <a href="http://en.wikipedia.org/wiki/Inclusion-exclusion_principle" rel="nofollow noreferrer">inclusion/exclusion</a>) that are more sophisticated but the current approach is the easiest to understand if you're seeing problems of this sort for the first time.</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