Sounding the horn for people who know something about math

May 13, 2006 10:22 PM

Suppose there's a web form with 50 checkboxes (representing options or interests), and that checking one has no effect on any of the others. A user could select any two boxes, or a half dozen, or a different half dozen, or all 50. The only constraint on the form submission is that the user must check at least two boxes. How many possible combinations are there?

Also, what is the underlying principle here and what is it called? (That is, how could I figure out this problem on my own later, if the situation changed or if a similar situation came up?)

posted by Tuwa to grab bag (17 comments total)

2^50 - 1276

Which is 2^50 - 50*49/2 - 50 - 1

All possible options - 50 choose 2 - 50 choose 1 - 1
posted by jhscott at 10:30 PM on May 13, 2006

Sorry, combinatorics, combinations and permutations, counting.
posted by jhscott at 10:31 PM on May 13, 2006

I think jhscott is wrong. If you must check "at least two", then the options that are out are (1) only one box checked, and (2) no boxes checked.

There are 50 of option (1) and 1 of option (2). So the answer is 2^50 - 51 = 1.12589991 x 10^15, or about 1126 trillion.

The best approach to this sort of problem is to figure out which is easier: counting up all the possibilities (two boxes, three boxes, four boxes, ...), or subtracting impossibilities from the total universe of options. In this case, the latter is much much easier.
posted by raf at 10:38 PM on May 13, 2006

The number of ways of choosing 2 distinct objects (irrespective of order) from a collection of 50 is "50 chose 2", and is 1225. See Wikipedia for details.
posted by samw at 10:38 PM on May 13, 2006

(And to get the 2^50: there are 50 boxes, each with two options, which are independent. So there are 2 x 2 x 2 x 2 x ... possible settings of the boxes.)
posted by raf at 10:39 PM on May 13, 2006

...and google tells me that that's 1.13 quadrillion.
posted by raf at 10:40 PM on May 13, 2006

There are 2⁵⁰ ways to turn on or off 50 switches (think of it as a 50 digit binary number). The problem says that the user must select at least 2, that means not 1 or 0. There are 50 ways to turn on a single switch, and only one way to turn on no switchs.
By my reckoning, the answer is 2⁵⁰ - 50 - 1.
Or, in other words: 1125899906842573.

On preview, I type too slow. But I am posting this anway because it proves I am ever so smart.
posted by AndrewStephens at 10:41 PM on May 13, 2006

Ah, I misunderstood the question. If you want to know how many possible valid inputs there are given your constraints, Raf is correct.
posted by samw at 10:43 PM on May 13, 2006

Wow, that was quick. I was off reading up on combinatorics and marvelling at how quickly it all went over my head, then on returning here to post followup questions I see that there have been another half-dozen explanations which I understand much more than the text at wikipedia.

Thanks, everyone.
posted by Tuwa at 10:53 PM on May 13, 2006

... I get the feeling the math articles at wikipedia are written for insiders. My favorite bit from the combinatorics article: However, given that we are looking at a counting function, the presence of the \sqrt 5 in the result may be considered unaesthetic.

I have no idea what that means, but I love the idea of math as an art (by extension, it would make my last math professor Jackson Pollock with a Sammy Sosa arm).
posted by Tuwa at 11:12 PM on May 13, 2006

I get the feeling the math articles at wikipedia are written for insiders.

If by insiders you mean people who know the pre-requisite math, well that goes with the territory.

My favorite bit from the combinatorics article: "However, given that we are looking at a counting function, the presence of the sqrt 5 in the result may be considered unaesthetic."

A counting function is supposed to provide you with an exact number, but if it incorporates an irrational number such as a sqrt(5), then by definition it cannot give you an exact result.
posted by randomstriker at 12:27 AM on May 14, 2006

but if it incorporates an irrational number such as a sqrt(5), then by definition it cannot give you an exact result.

Thats not true. A simple counterexample is (sqrt(5))^n). Let n=2 and the answer is 5. The comment said it was unaesthetic not that it was wrong. Binet's function gives exact answers.
posted by vacapinta at 12:51 AM on May 14, 2006

If by insiders you mean people who know the pre-requisite math, well that goes with the territory.

Ah, of course you're right. Don't mind me; I have a knack for overlooking the obvious.

Thanks for the additional explanations, randomstriker, vacapinta.
posted by Tuwa at 6:49 AM on May 14, 2006

vacapinta, an exact result is obtained only for certain values of n. I stand by my original comment.
posted by randomstriker at 12:28 PM on May 14, 2006

to get all the possibilities of combinations with at least two, the easiest way is to find all of the combinations of any number of checkboxes and subtract the possibilities with only one checked. i.e.:

50⁵⁰-50¹ = 8,881,784,197x10⁸⁴-50
posted by destro at 4:50 PM on May 14, 2006

sorry for the sloppy scientific notation. that should be:
8.881784197x10⁸⁴-50
posted by destro at 4:51 PM on May 14, 2006

Doh, sorry, typing without thinking. My answer was for "more than 2". :-(
posted by jhscott at 5:22 PM on May 14, 2006