Sorry for reposting, but i didn't get any answers.. hard problem to answer?

Question

difficult q?
how many ways are there to choose a, b, c....g from {2, 3, 4, 5, 6, 7, 8} such that 1bdf Please don't brute force this, because that's not a good solution.

I do have a method to calculate the answer which is only partially a brute force method. I agree that brute force is fine but I was hoping for some neat bijection.

Answer 1

This definitely isn't easy... I think I see why you didn't get an answer the first time you submitted this question. :)

I played around with this problem using pawns on a chessboard to visualize it better - in other words, I turned your question into finding how many ways there are to arrange pawns in a zigzag pattern on an nxn chessboard. The small chessboards are easy to count, so that seemed like a good way to get started: On a 3x3 board, there are 2 solutions; on a 4x4 board there are 5 solutions.

When I worked out the solutions for a 5x5 board, I started to notice a pattern, and this pattern looks like it carries forward. Basically, it appears the number of solutions for an nxn board can be derived from the solutions for an (n-1)x(n-1) board. This statement will make more sense when I write down the solutions in this way:

2 x 2 board: 1 solution

3 x 3: 1 + 1 = 2

4 x 4: 1 + 2 + 2 = 5

5 x 5: 2 + 4 + 5 + 5 = 16

6 x 6: 5 + 10 + 14 + 16 + 16 = 61

So, there is a pattern here. To get the number of solutions for a 7 x 7 board, start with the last number on the left side (i.e. 16) and work from right to left by adding each number one at a time (32, 46, 56, 61). Finally, repeat the last number. The solutions for the 7 x 7 board becomes:

7 x 7: 16 + 32 + 46 + 56 + 61 + 61 = 272.

If this is correct, the solutions for an 8x8 board (i.e. the question if you add an 8th variable to your question) would be:

8 x 8: 61 + 122 + 178 + 224 + 256 + 272 + 272 = 1385

The clincher... note the numbers in bandf list - same numbers!

Answer 2

I don't have a complete answer but I did find mention of this sequence in the online encyclopedia of integer sequences...

a(n) = number of alternating permutations on n letters.

n a(n)
0 1
1 1
2 1
3 2
4 5
5 16
6 61
7 272 <----
8 1385
9 7936
10 50521
11 353792
12 2702765
13 22368256
14 199360981
15 1903757312
16 19391512145
17 209865342976
18 2404879675441
19 29088885112832
20 370371188237525
21 4951498053124096
22 69348874393137901

I think this is the same as your sequence, so with 7 additional letters, I think the answer is 272. The sequence is related to Euler numbers and there is some mention of binomials, etc. that get beyond me. I was trying to find a closed form solution, or even a recursive expression that would help you out...

The answer does appear to be 272, but you'll have to research more on the pattern.

Answer 3

I don't think you have given us enough information.

What I see is that you have seven variables and seven values, and you want to know the number of ways that values can be chosen so that they are strictly in order. If that's the question, the answer is one.

I don't understand your notation. Is a both greater than 1 and greater than b. b is less than c c is greater than d. d is less than e, e is greater than f. f is less than g.

So we have what I'll call lesser numbers, b, d, f and greater numbers a, c, e, and g.

I can count at least 144, but I know there are even more than that

b, d, f have the values 2, 3, 4 ( 6 possible permutations )
a, c, e, g have the values (5, 6, 7, 8) 24 permuatations.

8 and 7 must be in the greater values, 1, and 2 the lesser values

Basically, you can figure out the sets than can be in any order, and count them via permuations, and then count unusual ones, like the case were a=3.

good luck... Sorry, don't have an easy answer for you.

Answer 4

Assuming repetitions are not allowed (i.e. no a=8, c=8...), there are 272 valid solutions.

And I disagree: brute force is by far the best solution here.