Help me figure out this number-of-combinations problem

February 13, 2016 1:11 AM

Supposing you have a set of N number of questions to choose from for creating a test. Your test must have a minimum of 1 question but can have all N. How many unique tests could you create? Am I correct to assume the formula is 64! (factorial)? 64 x 63 x 62 x 61...
posted by postergeist to Science & Nature (6 answers total)

Best answer: If you can have between 1 and N questions in a test, then there are 2^N tests. The power set enumerates all subsets of a set of elements (questions, etc.).
posted by a lungful of dragon at 1:48 AM on February 13, 2016 [1 favorite]

Response by poster: Just looked up power set. That's the one! Thanks!
posted by postergeist at 1:56 AM on February 13, 2016

Note: If you have to have at least one question, then there are 2^n - 1 possible tests, since you have to exclude the test with 0 questions on it (the empty set). (Also, this is assuming that the order of the questions doesn't matter; if order matters, then it gets more complicated...)
posted by bassooner at 2:08 AM on February 13, 2016 [4 favorites]

N! would be the number of unique tests you could create if (a) you are required to use all N questions and (b) altering the order of the questions is enough to have a test considered unique.

If uniqueness is assessed only on the selection of questions, independent of their ordering, then you can create 2^N - 1 unique tests.

If uniqueness is assessed on both question selection and ordering, then you can create

N tests with 1 question
+ N(N-1) tests with 2 questions
+ N(N-1)(N-2) tests with 3 questions
+ N(N-1)(N-2)(N-3) tests with 4 questions
+ ...
+ N! tests with N questions

a result about which you will find more than you could possibly need to know in The On-Line Encyclopedia of Integer Sequences (the number you're after is actually 1 less than that given in the Encyclopedia, because the single case of zero questions is excluded).
posted by flabdablet at 5:49 AM on February 13, 2016

...and of course the 1-less version has an OEIS entry of its very own, which includes the useful shortcut formula

a(n) = floor(e * n! - 1)

posted by flabdablet at 6:03 AM on February 13, 2016

Note: If you have to have at least one question, then there are 2^n - 1 possible tests, since you have to exclude the test with 0 questions on it (the empty set).

Yes, sorry, my answer is wrong. The above is correct.
posted by a lungful of dragon at 11:52 AM on February 13, 2016