Combinatorics Puzzle: How many arrangements...?

Good question!

If it starts with 0 or 9, then the digits must be in order.

0 must be followed by 1, then by 2, then by 3 etc.

9 must be followed by 8, then by 7, then by 6 etc.

So there is only 1 that starts with 0 and 1 that starts with 9.

There are others, of course, such as 5432167809.

I looked at 200,000 random arrangements, and only found 30 that satisfied the condition. That would indicate that the number of possible strings is approximately 10! x 30 / 200000, which is in the neighborhood of 500. I haven't figured out how to get an exact count, or how to generate them.

Once you pick the first number, the next must be one more or one less. There are also very few choices for the third. So many of the 10! permutations don't need to be check, if you are doing an exhaustive search.

E.g., if it begins 10 then those must be followed by 23456789.

Similarly, if it begins 89 then those must be followed by 76543210.

If it begins 12 then 0 can be anyplace but the other digits must be in the order 3456789, giving 8 possible strings depending on where 0 goes.

If it begins 87 then 9 can go anywhere, but the others must be in order 6543210.

Obviously, it gets more and more complicated and the counting becomes difficult.

Hope this helps.

Edit. Well, I may have found that answer, but I used a program, not logic. If found that there are 512, in line with what was expected by the sample. Here is the count, sorted by the first two characters "AB." It jibes with what reasoning there was above. However, it should be symmetric, but there are some discrepancies. I'll investigate and try to figure out why 43 had 57 instead of 56, and why 67 had 27, not 28. Very odd. Edit--For some reason there was an erroneous string starting with 43, and a missing string starting with 67. I've corrected the list, which I believe is correct, but I guess I need to do some more testing and verification. Odd that the program would have two glitches like that.

The program generated all 10! permutations and tested them. It didn't take TOO long, but long enough that I don't want to rerun it. Note that the numbers in the table below are all (but for the 2 discrepancies), binomial coefficients 8Ck. That should be a good clue to a logical approach. If you try to build strings, you get a feeling that the number of possible strings should increase as the initial number does, and then come back down, which it does.

AB Count

01 1

10 1

12 8

21 8

23 28

32 28

34 56

43 56

45 70

54 70

56 56

65 56

67 28

76 28

78 8

87 8

89 1

98 1

Total 512

The string must end with 89, 09, 90, or 10. There are 128 strings with each of those.

There is a symmetry in the strings which is fairly obvious. Replace each digit n with 9-n, and you have the complementary string which also satisfies the conditions. Another way to look at those is this: Rank the strings in order and number them from 1 to 512. Add string n and 513-n, and the result is 9999999999.

Edit 3. OK, I got it. First assume that 4 comes before 5. Then 6 7 8 and 9 must follow in that sequence. that gives us the string 456789 with 7 spaces before and after those digits to place 0 1 2 and 3. We will sum the number of ways we can place those into those spaces. Some spaces can be left blank. We will rely on the Stars and Bars technique, Theorem 2. See the source.

We will look at all orders in which 3 2 1 and 0 can be placed, and then calculate using the theorem cited. So, the ways 3210 can be places are:

a) 3210. There is complete freedom on which of the spaces they are placed. The number of option is 10C4 = 210. (There are n=7 places for the k=4 numbers, so (n+k-1)Ck is the number of placements. This is like putting 4 balls in 7 buckets. Since the sequence 3210 is specified, they are just like the balls, which are indistinguishable. We don't need to worry about the numbers 3210 themselves, just how many we are putting into each slot. This is the crucial technique, so I'm going into it in some detail (just this once). BTW, I've looked at my 512 sequences, and verified that 210 have the specified order.

b) 2310. The 2 and 3 must come before the 4, so that leave 2 numbers to place into 7 possible slots. The number of placements is 8C2 = 28.

c) 2130. The 213 must come before the 4, so that leaves 1 number to place into 7 slots. Obviously 7C1 = 7

d) 2103, 1203, 1023, 0123. All must come before the 4, so there is only one way to do each of those, for a total of 4

e) 1230. The 123 must come before the 4, so that leave 1 number to place into 7 slots. Like c), that makes for 7 possibilities.

The total is 210 + 28 + 7 + 4 + 7 = 256.

Now take the complementary sequences (replacing k with 9-k). I referred to those earlier. Those sequences all have 5 coming before 4, so they are different from the 256 described above.

If you like, you could go through the exact same logic, 5 comes before 4 so they must be followed by 3 2 1 0. 543210 gives you 7 places to place 6 7 8 and 9, etc. I really don't see the need to go through that, but anyone who wants to is more than welcome.

So there are 256 with 4 before 5, 256 with 5 before 4, and 256+256 = 512 all together.

Not sure what you mean. If you can repeat the digits, then we'd have to know many spots we'd need to fill.

If you don't repeat the digits, are we talking about numbers that use up all the digits. In that case, I seems

pretty easy:

0123456789 and

9876543210 would work, but I don't think anything else can work.

You're pretty much stuck going in one direction because reversing would take you to a digit

that you'd already used. And If you start anywhere other than 0 or 9, either get to 9 or 0 before you are

done.