Timeline for Efficiently computing $\prod_{i=1}^{n} A_i$
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 6 at 0:15 | history | edited | LSpice | CC BY-SA 4.0 |
Title is too tall; deleted "thanks"
|
| Sep 5 at 21:57 | vote | accept | user369335 | ||
| Sep 5 at 20:33 | comment | added | Dan Piponi | Combinatorially, this is all about computing the sum over all subsets S of {1,...,n} of the product of the kth powers of the elements of S, with the constraint that S may not contain two adjacent integers. You can see why by drawing a trellis diagram for the matrices. (The Fibonacci numbers arise when you count the ways you can choose subsets with no adjacent elements which is why they pop up.) | |
| Sep 5 at 16:31 | answer | added | Peter Taylor | timeline score: 9 | |
| Sep 5 at 8:31 | comment | added | Gro-Tsen | @PeterTaylor Indeed, but I am merely remarking that since the number of involutions on $n$ objects is a particular case that is very well studied and since simple no closed form value for that seems known, it is very unlikely that one will be available here. But it's not even clear what user369335 wants: computing quickly and efficiently is very different from (and somewhat orthogonal to) finding a closed form. | |
| Sep 4 at 23:31 | comment | added | Peter Taylor | @Gro-Tsen, each of the entries satisfies a second-order D-finite recurrence with coefficients of degree $k$, so for some meanings of "general formula" it's not so hopeless. We have $$A_1 A_2 \cdots A_n = A_1 A_2 \cdots A_{n-1} \begin{pmatrix} (\frac{n}{n-1})^k & 0 \\ 0 & 1 \end{pmatrix} + A_1 A_2 \cdots A_{n-2} \begin{pmatrix} n^k & 0 \\ 0 & (n-1)^k \end{pmatrix}$$ | |
| Sep 4 at 21:43 | comment | added | Gro-Tsen | The lower-right entry seems to be Fibonacci for $k=0$, number of involutions for $k=1$, $n!$ for $k=2$, A167449 for $k=3$ (where no formula is given), and unknown in the OEIS for $k=4$. This does not bode well for a general formula! | |
| Sep 4 at 21:41 | history | edited | user369335 | CC BY-SA 4.0 |
added 300 characters in body
|
| Sep 4 at 21:29 | comment | added | user369335 | The closed-form in general maybe hopeless, but it is possible for a specific $k$, take $k=0$ as an example. | |
| Sep 4 at 21:26 | history | edited | user369335 | CC BY-SA 4.0 |
added 1 character in body
|
| Sep 4 at 21:17 | comment | added | Joe Silverman | For $k=2$, the lower right entry of the product seems to be $n!$. What makes you think there should be a simple closed form in general? What sort of experiments have you tried? | |
| Sep 4 at 21:08 | history | asked | user369335 | CC BY-SA 4.0 |