Timeline for How to solve a given combinatorial problem?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18 at 13:50 | history | edited | ploosu2 | CC BY-SA 4.0 |
closed formula hypothesis
|
| May 17 at 8:56 | comment | added | ploosu2 | @LaVuna47 Yes and if $k$ is very large and $n$ small, we can use fast matrix exponentiation (although if the exact answer is needed, the rational numbers will get very large denominatory, and if an approx suffices, then we're already very close to the steady state so just use that). But out of curiosity, I went and found the "closed formula". Well, the coefficients are still solved recursively in $n$ steps. | |
| May 17 at 8:52 | history | edited | ploosu2 | CC BY-SA 4.0 |
doing the diagonalization to get formula
|
| May 16 at 18:54 | comment | added | LaVuna47 | The answer is $ n * f(1, k) $ | |
| May 16 at 18:53 | vote | accept | LaVuna47 | ||
| May 16 at 18:49 | comment | added | LaVuna47 | I guess we don't need to derive such a good-looking formula. The key idea here is that we can fix some box and solve it independently of other boxes so to speak. Following recursive formula works just fine in desired $O(n*k)$ using dynamic programming: $ f(b, k) = (b + (n-b) * (n-1)) * f(b, k-1) + b * (n-1) * f(b-1, k-1) + (n-b) * f(b+1, k-1)$ | |
| May 16 at 13:53 | comment | added | ploosu2 | The formula looks like it might also "come from" inclusion exclusion, since the second term is negative. But it's different from the rest since it doesn't have the power $k$. If we somehow move the contributions to the next term and so on... | |
| May 16 at 13:48 | history | edited | ploosu2 | CC BY-SA 4.0 |
formula for n=7
|
| May 16 at 13:38 | history | edited | ploosu2 | CC BY-SA 4.0 |
added 279 characters in body
|
| S May 16 at 13:20 | history | edited | ploosu2 | CC BY-SA 4.0 |
closed formulas for n=4,5 and better notation
|
| May 16 at 13:15 | review | Suggested edits | |||
| S May 16 at 13:20 | |||||
| May 16 at 12:47 | comment | added | ploosu2 | The eigenvalues of the matrix $Q_n$ seem to be $\frac{b}{n}$ for $b=0,1,\dots, n$. Maybe with diagonalizing we can even get a simple closed formula... | |
| May 16 at 12:40 | history | edited | ploosu2 | CC BY-SA 4.0 |
added 4 characters in body
|
| May 16 at 12:33 | history | answered | ploosu2 | CC BY-SA 4.0 |