How many combinations are there in "X" coin flips?

I believe the answer is 2^x. Am I correct? If so, check the difference between 2^x and x^2 once you get past 10 or so.

plot of 2^x vs x^2

asked 03 Jul '12, 12:08

Dan%20Weiss's gravatar image

Dan Weiss
9314

accept rate: 0%

edited 03 Jul '12, 12:24

Retagbot's gravatar image

Retagbot ♦
1518171


8 Answers:

2^X is correct. This is an exponential. It grows incredibly fast with X

link

answered 03 Jul '12, 13:04

Sebastian%20Thrun's gravatar image

Sebastian Thrun
21.6k183855

1

Thanks for your responses. Speaking statistically, I was .9 certain. Now it's 1.0

(03 Jul '12, 15:06)

Dan Weiss

Dan%20Weiss's gravatar image

Coin flips obey a binomial distribution. The number of different ways of getting h heads in n independent flips is n! / (h! * (n-h)!), where ! is the factorial operator. The probability of getting exactly h heads is this binomial coefficient times p^h * (1-p)^(n-h), where p is the probability of heads.

The number of arrangements (or permutations) of n draws from a population is n!. (Here the population consists of Heads and Tails, drawn "with replacement.") However, we can't distinguish between sequences in which the Heads are swapped one for another, nor those in which Tails are swapped one for another. This is why the binomial coefficient is normalized by h! and (n-h)!. The coefficient is also called the number of combinations of h heads in n flips.

For large n, n! goes up as O(n^n), according to Stirling's formula. If we keep the number of heads a small constant, the binomial coefficient approaches something like n^h and the probability of getting exactly h heads approaches zero. Not surprising.

If we assume a fair coin, h = n/2 and the number of combinations is n! / 2((n/2)!), which goes up as n^n / (n/2)^(n/2), or O(n^n) as n gets very large. This is much, much faster than 2^n.

However, the probability of any specific number of heads goes to zero in the limit because it must be normalized by the total probability of all possible "heads counts" -- the full binomial distribution. In the limit we get a shifted Gaussian distribution, or something very similar. With continuous distributions, it only makes sense to speak of the area under slices of the curve or ranges of X, not at specific infinitely exact values of X.

So, like most things in statistics, it depends. Or it's complex. Or further clarification or research is needed. But I think the straightforward answer to the original question is that the number of combinations goes up as n^n.

link

answered 03 Jul '12, 18:34

Kenneth%20I.%20Laws-1's gravatar image

Kenneth I. L...
28.2k1984187

Answering via my son's account, as we both take this course and his session is persisted with the browser, even so I log in with my credentials with the main page (seems to be a defect while integrating main course site with the "discussion" which is http://stackexchange.com/ product)

One way to think of this is by using the induction:

X = 1 - there are two combinations only, H and T

X = 2 - $%coin_{1}$% is H while $%coin_{2}$% is H or T and $%coin_{1}$% is T while $%coin_{2}$% is H or T $%\Rightarrow $% 4 combinations.

...

assuming $%X = n-1$% and the number of combinations is $%2^{n-1}$% then for $%X = n$% we have $%coin_{n}$% is H while the rest of the $%n-1$% coins give $%2^{n-1}$% combinations and $%coin_{n}$% is T while the rest of the $%n-1$% coins give $%2^{n-1}$% combinations $%\Rightarrow $% $%2^{n-1}+2^{n-1}=2^{n}$% (or $%2^{X}$%) combinations.

Another way to think of this is using the Newton's binomial (it's a bit more complicated, but very powerful though) http://en.wikipedia.org/wiki/Binomial_coefficient
$$(a + b)^{n}=\sum_{k=0}^{n}\binom{n}{k}\cdot a^{n-k}\cdot b^{k}$$
If $%a=1$% and $%b=1$% then
$$2^{n}=\sum_{k=0}^{n}\binom{n}{k}$$
The right side of this equality is the sum of all the possible combinations of e.g. H's out of $%n$% (this is also true for T's because $%\binom{n}{k}=\binom{n}{n-k}$%).

link

answered 03 Jul '12, 20:04

Tudor%20Ciurca's gravatar image

Tudor Ciurca
343

edited 03 Jul '12, 20:08

Great explanation. The inline math notation is excellent. Is there a reference implementing this on the forum?

(03 Jul '12, 22:57)

Richard

Richard's gravatar image

There was a reference some time ago, with an other course ... all you need to know is Latex (here is an online editor http://www.codecogs.com/latex/eqneditor.php) and add the formulas within the following tags:

  • double $ to open and double $ to close ($$) - formula will appear in a new line

  • one $ and one % to open and one $ and one % to close ($%) - formula will appear inline.

(04 Jul '12, 04:36)

Tudor Ciurca

Tudor%20Ciurca's gravatar image

You may want to be careful about word choice here - combination has a formal definition in mathematics. What you probably meant is the number of distinct outcomes. In that case, the formula is correct.

link

answered 03 Jul '12, 23:08

Suk%20Chan%20Lee's gravatar image

Suk Chan Lee
4468

Ah, you see clearly (whereas I got caught up in the math). Yes, the number of possible outcomes is 2^n. That's different from the number of combinations, and more relevant to way we've been looking at heads/tails sequences.

(04 Jul '12, 02:53)

Kenneth I. L...

Kenneth%20I.%20Laws-1's gravatar image

Yes, "outcomes" was what I was interested in. Learning the correct "lingo" is part of the process.

(04 Jul '12, 18:17)

Dan Weiss

Dan%20Weiss's gravatar image

One way to convince yourself about 2^x is to think about going from one stage to the next. For example, imagine you are looking at 12 coin flips and finding all the possible combinations. Then you look at 13 flips and find all the possible combinations. Is it believable that the number of possible combinations will double as you go from 12 flips to 13 flips? Why should that be true? If you can justify that, then you have a good reason to believe that 2^x is correct.

link

answered 03 Jul '12, 12:20

Nina%20Koch's gravatar image

Nina Koch
6101111

2^n holds true if and only if there are exactly two possible outcomes.

If you're dealing with a double-headed coin, the results will always be HHH..., or 1^n, which equals 1.

If you add a third possibility (heads, tails, gets stuck in the ceiling), then the number of combinations is 3^n. Four possibilities is 4^n, etc., etc.

link

answered 03 Jul '12, 22:14

Clinton%20Morell's gravatar image

Clinton Morell
1.9k3438

consider the result of n coin flips recorded as a n-bit binary number (1 for heads, 0 for tails in the kth bit position for the kth toss). So the number of distinct combinations is just the total number of states for a n-bit binary number which is 2^n.

link

answered 04 Jul '12, 20:25

al%20gee's gravatar image

al gee
2.0k113

Then what is the formula for computing the number of possible outcomes if you flip multiple coins for a multiple number of times? For example, if you have 3 coins and you want to flip each coins three times, you want to know exactly how many possible outcome there are, what is the formula for that?

If the possible outcomes for each coin flip = 2^x
Then shouldn't it be a factorial of the three coins flips?

(2^x) * (2^x) * (2^x) = 2^ x+x+x

(2^3) * (2^3) * (2^3) = 2^9

Is this correct? I am unsure because I am using what I just learn from Visualizing Algebra to derive at this conclusion.

link

answered 17 Apr '13, 10:00

Nam%20Nguyen-2's gravatar image

Nam Nguyen-2
1.0k18

Depends on your setup, or more specifically what do you define as your outcome. If you're only interested in the sequence of flips and the order that the different coins are flipped doesn't matter (i.e., $%\{coin1, coin2, coin3\}$% is the same as $%\{coin3, coin2, coin1\}$% and so on), flipping a single coin $%9$% times has the same outcomes as flipping each of the $%3$% coins $%3$% times each.

This would be equivalent to using indistinguishable coins or putting a restriction that the coins should be used in an specific sequence, e.g., $%coin1$%, then $%coin2$%, then $%coin3$%.

But let's say the coins are distinguishable from one another, i.e., you can tell $%coin1$% from $%coin2$% from $%coin3$% and that this is important to you. You would have to consider all different ways you could pick the coins (all permutations), so in this case the number of outcomes would be $%(2^3 \times 2^3 \times 2^3 \times 3 \times 2 \times 1)$% or $%(2^9 \times 3!)$%.

(17 Apr '13, 11:19)

Marcio Gualt...

Marcio%20Gualtieri's gravatar image

Thanks Marcio. Let me get this straight, let assume that we have 1 coin and we flip it three times. And assume that

order doesn't matter;

does this mean that (h,t,t) is the same as (t,t,h)? In this situation we count it as 1 outcome and not 2 different outcomes? Because it doesn't matter which order the h appears as long as it appears once;

If that is the case then we shouldn't count (t,h,t) as a separate outcome as well? Then the total number of possible outcomes is 4?

Flip1....Flip2.....Flip 3
h............h..............h
h............h...............t
h............t...............h
h............t...............t
t.............h..............h
t.............h..............t
t............t................h
t............t................t

Then in the case that the order at which an event appear does matter, then we have 8 possible outcomes?

(17 Apr '13, 12:57)

Nam Nguyen-2

Nam%20Nguyen-2's gravatar image

No problem. In this particular setup your outcome would be the number of Heads, so you would have only three outcomes: 1 Heads, 2 Heads or 3 Heads. I think I wasn't very clear when I said: "$%\{coin1, coin2, coin3\}$% is the same as $%\{coin2, coin2, coin1\}$% and so on". I meant that every single order is the same, since for this particular setup, the coins would be indistinguishable from one another. But, once again, that's up to the person formulating the problem. There is no magic formula for every case.

(17 Apr '13, 13:16)

Marcio Gualt...

Marcio%20Gualtieri's gravatar image

Marcio, to follow up with our discussion, I would like to know if the Permutation and Combination methods are not really methods to calculate how many possible outcomes but rather the number of possible outcomes that we want to know.

Let me explain what I mean. Before seeing your post to my query, I created a thread and ask this question

Assume that we have a fair die. And we roll the die 3 times and we want to know the probability that we roll at least a 1. We know that there are 216 possible outcomes by way of the exponential function 6^x.

But is there a similar pattern or formula for us to determine the answer to the question above or similar questions without having to write produce the Truth Table?

So are the Permutation and Combination method use to answer this kind of question?

(17 Apr '13, 13:17)

Nam Nguyen-2

Nam%20Nguyen-2's gravatar image

If you look at my answer to your question, you will see that I have used both combinations and permutations to solve the problem, but every problem is different. You could say that combinations and permutations derive from specific setups, but most problems are some sort of a "mix" of the two. You have to think through each case.

(17 Apr '13, 13:21)

Marcio Gualt...

Marcio%20Gualtieri's gravatar image
Your answer
Question text:

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags

×3,505
×20

Asked: 03 Jul '12, 12:08

Seen: 4,641 times

Last updated: 18 Apr '13, 03:25