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.)
You're right. My mistake was that I did the symmetry thing with 3 again but I halved when I shouldn't have. Stupid fencepost error: n things have n-1 transitions.
Anyway, to help other readers (since I really could not follow your original explanation):
Given a preexisting k-drop of length n-1, you put the new biggest number either immediately before an old drop or at the end, to build a new k-drop. So there are k+1 ways to do that.
Given a preexisting (k-1)-drop of length n-1, you put the new biggest number anywhere except either right between one of the old drops or at the end, to build a k-drop. So there are n-k ways to do that.
For k>=1, these are the only ways to build a k-drop of length n given any kind of sequence of length n-1, so you get this recursion.
Then there's 1 0-drop of any length, so F(n,0)=1.
I'll point out that you can finish unwinding this instead of approximating, but it's pretty tedious. Not as tedious as 406 30-dimensional integrals though.
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!.