Puzzle Time - Sequencing the digits

[jon-nyc]

In how many ways can you write the digits 0 through 9 in a row, such that each digit other than the leftmost is within one of some digit already placed to the left of it?

Here's an example of one way to do it: 3 4 5 2 6 1 0 7 8 9.

[jon-nyc]

I think I have the insight to make this simple.

I haven’t solved it all the way though because I suck at combinatorics and haven’t looked it up yet.

[jon-nyc]

Ok the combinatorics are easy so I have a solution.

[jon-nyc]

Just a numeric answer here. But if you attempt this show your work.

***=NSFW content***

click to show

512

[Horace]

This one seemed tedious and I have other things to think about. Maybe next time.

[jon-nyc]

Without a clarifying insight, sure, but that’s true with all of these pretty much.

[Horace]

@jon-nyc said in Puzzle Time - Sequencing the digits:

Without a clarifying insight, sure, but that’s true with all of these pretty much.

I was referring to the tedium of working one's way to the insight.

[jon-nyc]

I'll post my answer under a spoiler. I doubt Klaus is playing on vacation and Ax hasn't chimed in yet.

***=NSFW content***

click to show

Any first number you choose will have a certain number of higher digits and lower digits, each side (respectively) must be placed in order. In other words, if you start with four, 5 must come before 6 before 7, etc. Even if some lower numbers are interspersed in there.

You can represent these as binary operations, 1 for the next higher number and 0 for the next lower number.

Then the problem becomes 'how many ways can I make a nine-bit word out of n 1s and 9-n 0s?

That is a simple combinatorics problem (even if I had to look it up) akin to the problem of "how many ways can I pull 4 red balls and 5 blue".

Also note that due to symmetry you only need to do half the numbers and double it.

you get this expression:

2* (9!/9! + 9!/8!*1! + 9!/7!*2! + 9!/6!*3! + 9!/5!*4!)

Each of those are calculable by hand.

[jon-nyc]

I like my answer better

SOLUTION: It seems that the sequences we want start with an arbitrary digit, but thereafter each digit must be either the lowest digit above those already placed, or the highest digit below them. If you construct the sequence from left to right, you don't know in advance when your number of choices will drop from 2 to 1. If you did know, you'd be fine; for example, if you knew you would run out of options after the seventh digit (as in the example), you'd know that the total number of sequences is 10 x 2 x 2 x 2 x 2 x 2 x 2 x 1 x 1 x 1.

If you're a fan of binomial coefficients, you might have noticed that the number of allowed sequences beginning with the digit k is "9 choose k," because it's the number of ways of deciding which of the remaining 9 positions to devote to the digits k-1, k-2, ..., 1, and 0. Thus, the total number of admissible sequences is the sum from k=0 to 9 of 9 choose k, which is 29 (because this counts all the ways of choosing a subset of the remaining 9 positions).

Indeed, choosing the "downward" positions is equivalent to choosing an allowed sequence. But there's an easier way to see that the answer is 29, A.K.A. 512. Construct your sequence from right to left instead of left to right!

The rightmost digit must be 0 or 9; its left neighbor will be the highest or lowest remaining digit. This continues all the way until the (forced) leftmost digit, so the number of ways to construct the sequence is 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 512.

[Klaus]

@jon-nyc said in Puzzle Time - Sequencing the digits:

I doubt Klaus is playing on vacation

I'm back. I'm not good with puzzles, but I love programming, so here we go:

http://tpcg.io/_DC4FYC

Press on "Execute" to confirm the 512