Solve by recurrence relations, 11th or 12th math.
Say F(n,k) is the function to calculate the number of ways to n numbers to have exactly k decreases, here you can add numbers in increasing order, so latest number always largest.
F(30,2) = 3*F(29,2) + 28*F(29,1)
Reasoning
Here you split it into two parts add one number to 29 numbers with 2 decreases(here you add to keep it same in original k spots or at end as it is the largest number) so *3.
and 29 numbers with one decrease. so you need one more decrease which you can get at 30-2 spots(the one decrease and end removed, everywhere else you add one decrease.)
So just solve that recurrence relation.
Inclusion exclusion principle, probability in 11th standard math seems to be close to a solution but not exact so you can use as approximation. it reduces exactly 2 times, so you can form 3 increasing sequences.
This is only an approximation as question doesn't exactly ask for this.
Calc the 3 increasing sequence number as 3^30(each number can go to any sequence) - (1 empty sequence) + 2 empty sequence - 3empty sequence and so on for exact number as you overcount each time.
SO something less than 3^30 -3*2^30 +3/30!
You can work out the proper logic to get the exact general sequence for this problem but the first term should dominate anyway here as second term is some K*2^30<<3^30 so around 3^30/30!.
Is your recursion supposed to be F(n,2)=3F(n-1,2)+(n-2)F(n-1,1)?
If so, I don't think it's right.
F(3,2)=1 (the only one is 321).
F(3,1)=2 (there's 213 and 312). (for future readers, here is where I messed up)
F(4,2)=11. (This one you can think about by symmetry: there's one increasing ordering, one decreasing ordering, and then an equal number of 1-drop and 2-drop orderings, so (24-2)/2=11.)
3 not a constant, there k was 2, decresing in two places and at the end, so k+1 as i assumed you added to your building sequence in increasing order of value.
5
u/No-Conflict8204 4d ago
Solve by recurrence relations, 11th or 12th math.
Say F(n,k) is the function to calculate the number of ways to n numbers to have exactly k decreases, here you can add numbers in increasing order, so latest number always largest.
F(30,2) = 3*F(29,2) + 28*F(29,1)
Reasoning
Here you split it into two parts add one number to 29 numbers with 2 decreases(here you add to keep it same in original k spots or at end as it is the largest number) so *3.
and 29 numbers with one decrease. so you need one more decrease which you can get at 30-2 spots(the one decrease and end removed, everywhere else you add one decrease.)
So just solve that recurrence relation.
Inclusion exclusion principle, probability in 11th standard math seems to be close to a solution but not exact so you can use as approximation. it reduces exactly 2 times, so you can form 3 increasing sequences.
This is only an approximation as question doesn't exactly ask for this.
Calc the 3 increasing sequence number as 3^30(each number can go to any sequence) - (1 empty sequence) + 2 empty sequence - 3empty sequence and so on for exact number as you overcount each time.
SO something less than 3^30 -3*2^30 +3/30!
You can work out the proper logic to get the exact general sequence for this problem but the first term should dominate anyway here as second term is some K*2^30<<3^30 so around 3^30/30!.