The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

0

The subproblems can be broken down as follows. f0 :- Number of available 0s. f1 :- Number of available 1s. ld :- The last digit of the string generated till now. dp[f1][f0+f1][0] = dp[f1][f0+f1-1][0] + dp[f1-1][f0+f1-1][1] dp[f1][f0+f1][1] = dp[f1-2][f0+f1-2][0] + dp[f1-1][f0+f1-1][1] which basically boils down to, Say at any step the string is S0 ...

2

Let's solve your example question first. Say, we want to know the number of combinations of size 2 possible from $A, B, C$. This would be equal to for each element in $A$, pair it with each element in $B$. This gives us $|N_A||N_B|$ combinations of size 2. for each element in $A$, pair it with each element in $C$. This gives us $|N_A||N_C|$ combinations of ...

4

This is only a sketch of solution (there might be some off-by-ones) Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and ...

1

You could look at the answers to this question on SO: https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions (in particular the part about Mahonian numbers) Additionally, it seems that dynamic programming with memoisation runs in $\mathcal{O}(N\cdot k)$ [NB: I didn't actually check this, it's in one of the ...

Top 50 recent answers are included