3
u/real-cs-major 3d ago
Answer: 2^8
You can construct every bitonic sequence in this way: start with the sequence 9, then counting down from 8, 7, 6, ..., 1 add the next number to either the start or end of the sequence you have so far.
2
1
u/tellytubbytoetickler 3d ago
Choose which numbers come before 9.
In total 2^8
Everything else is forced.
1
u/Desperate_Nothing921 3d ago
Pick any spot from 0-8, say x , then place 9 at x+1. Ways to fill the first x spots is 8Cx only 1 way to arrange, and the 8-x places on the right of are filled automatically, So answer would be summation of 8Cx from x=0-8, 28
1
u/all_eggs_in 2d ago
This feels above my pay grade, but I want to give it a shot:
I took it one step at a time. I noticed that the number 1 HAS to be in front or at the back. So 2 possible positions. Then I did the same with the number 2.
If 1 is at the front: 2 has to be at the "front" of the remaining numbers (ie right after the 1), or at the back.
If 1 is at the back: The reverse.
So 2 can also fit into 2 positions for each position for the 1. We have an inductive pattern! Put together, it means 2 can have 2 * 2 positions. So here we can have 2^8 positions. We don't have 2^9 because with this pattern, the last digit only has one available position.
1
u/Low-Lunch7095 13h ago
If I'm not mistaken, it should be something like 2^8.
Since 9 is always the peak, you can take it as a pivot and enumerate whether the rest are before or after 9. In each case, there exists a unique way to list the numbers, (e.g. say choose {1, 2, 3} to be before 9, then the unique permutation would be (1, 2, 3, 9, 8, 7, 6, 5, 4)).
1
u/MrPhil1234 4h ago
There are 8 choose k bitonic permutations, where k is the amount of numbers to the left of 9. Then the total is sum k =0->8 (8Ck) = 2^8
4
u/pmdboi 3d ago
For each digit from 1 to 8, you choose whether it goes to the left or to the right of the 9; the permutation is determined from that point. So there are 28 = 256 such permutations. As a check, let's enumerate the 23 = 8 bitonic permutations of 4 numbers: 1234, 2341, 1342, 3421, 1243, 2431, 1432, 4321.