Bag of Marbles
 

I have a bag containing twenty marbles, numbered 1 through 20.
Tbe bag has a hole in it, from which one marble falls at a time,
until all twenty marbles have fallen out, subject only to the condition
that the set of marbles that have fallen out at any time are always
numbered in a sequence with no gaps. For example, the first four
marbles to fall out might be 7,8,6,9, but not 7,8,5,9.

The question, of course, is:
In how many different ways can I lose all my marbles?

Can I assume from your explanation that sequence 7,8,9,5,6 would be invalid?

That's correct, 7,8,9,5,6 would be invalid since there would be
a gap (6) when the 5 fell out.

[spoiler]2^19.

The next marble must be either the top or the bottom of the range.

If "k" comes out first, the next 19 marbles will include k-1 that come at the bottom of the range. These bottom marbles can occur (k-1)C19 ways. So the total number of ways is 0C19 + 1C19 + .... 18C19 + 19C19. This sum is 2^19. Among the ways to see this is to observe that it is the binomial expansion of (1+1)^19.
[/spoiler]

[QUOTE=wblipp;115805][spoiler]2^19.

The next marble must be either the top or the bottom of the range.

If "k" comes out first, the next 19 marbles will include k-1 that come at the bottom of the range. These bottom marbles can occur (k-1)C19 ways. So the total number of ways is 0C19 + 1C19 + .... 18C19 + 19C19. This sum is 2^19. Among the ways to see this is to observe that it is the binomial expansion of (1+1)^19.
[/spoiler][/QUOTE]

Right idea, but you neglected to consider [spoiler]the special case of the first marble which is unconstrained.

The correct answer is 20 * 2^18[/spoiler].

[QUOTE=Mr. P-1;115808]Right idea, but you neglected to consider [spoiler]the special case of the first marble which is unconstrained.[/spoiler][/QUOTE]

I don't think so. The first marble can be any one of the twenty marbles. This was considered in my solution [spoiler]by the twenty terms in the sum. The first term, 0C19, is the total numbers of ways given the first ball is #1 (1 way). The second term, 1C19, is the total number of ways given the first ball is #2 (19 ways). etc.[/spoiler]

As further argument in favor of my answer, I note that it's easy to enumerate the ways for 3 marbles. There are four arrangements:

1 2 3
2 1 3
2 3 1
3 2 1

William

My answer is correct only if the sequence is permitted to 'wrap' from 20 to 1 and vice versa. Since a reasonable reading of the problem doesn't permit 'wrapping', my answer is wrong. I failed to consider the edge cases in which 1 or 20 has already been reached.

On re-reading your solution, it looks correct, though (scrabbling for a face-saving excuse here) I don't think you explained it very well.

If we allow wrapping then given the first marble, there are
two distinct ways of choosing each of the next 18.
I am trying to use this as a simple derivation of William's result
without immediate success.

David

Think I've done it:
[spoiler]
Consider the 20 rotations of a particular ordering with wrapping.
The only rotations which do not invoke wrapping are those which
end with 1 or 20. So we have 20*2^18*(2/20).

[/spoiler]

No that won't do. Not all rotations of a legitimate
ordering are legitimate themselves:sad:

But we do get a legitimate ordering by adding 1 to the
number of each marble in a legitimate ordering (20+1 = 1).
I think my original argument applies to these 20 different
orderings.

Nice catch and nice resolution.

[spoiler]
Consider the general case of k marbles numbered 1 through k. Let S(k, n) be the number of ways to lose k marbles with the n-th marble being "1" and S(k) be the total number of ways to lose k marbles, then

S(k) = S(k, 1) + S(k, 2) + ... + S(k, k)

Note S(k + 1, n) = S(k, n), hence for k >= n, S(k,n) = S(n,n) (for k<n, S(k,n) = 0)

Note S(n, n) = S(1,1) + S(2, 2) + ... + S(n-1,n-1)

So S(k+1) = S(k) + S(k+1, k+1) = 2*S(k)

Since S(1) = 1, this means S(20) = 2^20
[/spoiler]

hrm. meh, somewhere I wasn't careful enough and I like wblipp's answer too much to go fix mine.