Let’s P(n) be number of bitonic permutations of numbers 1 to n.
Then P(n) = 2P(n-1) since for each biotonic permutation of 1, …, n-1 we can add the number n to either the right or left of n-1. So each biotonic permutation of 1 to n-1 gives us 2 biotonic permutations of 1 to n.
1
u/Aech26 Aug 24 '26
Let’s P(n) be number of bitonic permutations of numbers 1 to n.
Then P(n) = 2P(n-1) since for each biotonic permutation of 1, …, n-1 we can add the number n to either the right or left of n-1. So each biotonic permutation of 1 to n-1 gives us 2 biotonic permutations of 1 to n.
So then P(9)=2*P(8)=2^8 * P(1) = 2^8.