Same problem but I will ask how many valid ways to build $$$M$$$ cubes after $$$N$$$ moves mod $$$10^9 + 7$$$ and $$$N \le 10^5$$$.I know how to solve it when $$$N \le 10^3$$$ , that is through DP but how when $$$10^5$$$ ? Is it related with Catalan numbers??
Isn't it number of permutations of $$$\frac{n+m}2$$$ of +1's and $$$\frac{n-m}2$$$ -1's where current sum doesn't go $$$<0$$$?
you are right , how to calculate that? oh cool I have just found out how to calculate I will just calculate for each index $$$x$$$ which is even and $$$x/2 \ge both:{(n+m)/2} , {(n-m)/2}$$$ : $$$C(x) * {N(max(n-(x+1),0),(n+m-x}/2))$$$ and sum them up , then total number of permutations — sum is my answer
Turned out not so trivial as it seemed at first sight. Have you proved your formula/checked against bruteforce count?
Because I have different formula by using Bertrand's ballot theorem:
Ok so my solution :
I am trying to find number of invalid rearrangements and then will deduct it from total rearrangements.So let's get into how to find count of invalid rearrangements :
A rearrangement is invalid if at some index prefix sum becomes $$$< 0$$$ in other words exact $$$-1$$$ for the first time , so we will count for invalid rearrangements for each index in which its' prefix sum becomes -1 for the first time and then obviously sum them up , so now how to calculate for each index : let's index is $$$x$$$ then upto index $$$x-1$$$ we can apply the formula of Catalan numbers as end result is 0 and equal count of $$$1$$$ and $$$-1$$$.And obviously in index $$$x$$$ we put a $$$-1$$$ if it's still available and then however we arrange the rest of the numbers doesn't matter.So I think this solution should be correct.You have any counter statement?
Idea to exclude invalid permutations is reasonable, but I'm not sure how to logically evaluate your way to count it.
Check against some random example n=20 m=12 ans=3705
you can calculate using same logic as for calculating catalan numbers. I guess it will be something like $$$\binom{n}{\frac{n-m}{2}} - \binom{n}{\frac{n-m}{2} - 1}$$$.
can you please explain how you derived it?
as was mentioned in comments earlier you need to calculate number of permutations $$$\frac{n+m}{2}$$$ 1 and $$$\frac{n - m}{2}$$$ -1 where doesn't exist prefix with negative sum. How many permutations of 1 and -1 exist? $$$\binom{n}{\frac{n - m}{2}}$$$. But some of them are bad.
Now we need to count bad permutations. Any bad permutation will have prefix with sum -1 (because should exist prefix with negative sum, and every number is either 1 or -1). Let's replace every -1 with 1 and every 1 to -1 in this prefix. What happened? Number of -1 decreased by 1. So number of bad permutations is same as number of permutations with $$$\frac{n+m}{2} - 1$$$ 1 and $$$\frac{n - m}{2}$$$ -1, which is $$$\binom{n}{\frac{n - m}{2} - 1}$$$.
Now we have answer: $$$\binom{n}{\frac{n - m}{2}} - \binom{n}{\frac{n - m}{2} - 1}$$$
thanks
This can be interpreted as number of valid parentheses of length $$$n-m$$$, which equals to $$$\frac{(n-m)}{2}^{th}$$$ Catalan number