Timeline for Elegant recursion for A301897
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 20, 2023 at 7:54 | comment | added | Notamathematician | @MartinRubey, try $b(2^m(2k+1))=-b(2^{m+1}k)+\sum\limits_{j=0}^{m+m\operatorname{mod}3+1}b(2^j k)$ for $m\geqslant 0, k\geqslant 0$ with $b(0)=1$. | |
| Jun 29, 2023 at 7:40 | comment | added | Martin Rubey | It may be worth observing that the generalized Sawin sequences $q_{i+1}\leq q_i + q_i \bmod k + 1$ give the Catalan numbers for $k=1$ and the Schröder numbers for $k=2$. For $k\geq 4$ the sequence grows faster than the number of permutations. Finally, for $k=3$ I found a (conjectural) triple statistics on permutations that gives the number of entries divisible by $3$, the number of entries equal to $1$ and the number of entries with remainder $2$ mod $3$. However, I was unable to find the corresponding bijection yet. | |
| Jun 24, 2023 at 23:05 | history | became hot network question | |||
| Jun 24, 2023 at 13:15 | vote | accept | Notamathematician | ||
| Jun 24, 2023 at 1:01 | answer | added | Terry Tao | timeline score: 37 | |
| Jun 23, 2023 at 20:48 | comment | added | Martin Rubey | Last update for today: we can restrict ourselves to "connected" derangements and Sawin sequences without zeros and without repeats. I am not sure whether this makes it any easier, however. | |
| Jun 23, 2023 at 18:35 | comment | added | Notamathematician | @WillSawin, nice! I would also like to know what is the definition of this combinatorial interpretation in this case? I'm having a little trouble understanding exactly how it works. | |
| Jun 23, 2023 at 17:19 | comment | added | Will Sawin | Yes, as long as the $g$ and $h$ are nonnegative. | |
| Jun 23, 2023 at 16:16 | comment | added | Notamathematician | @WillSawin, is there a similar combinatorial interpretation for $R(n,0)$ where $R(n,q)=\sum\limits_{j=0}^{f(q)}g(q,j)R(n-1,j)$ with $R(0,q)=h(q)$? | |
| Jun 23, 2023 at 16:14 | comment | added | Martin Rubey | It is a bit surprising to me, but it seems that the generating function for "connected" such permutations satisfies a slightly simpler cubic: $x C(x)^3 - (3x+1) C(x)^2 + (x+3) C(x) - 2 = 0$. | |
| Jun 23, 2023 at 15:21 | comment | added | Terry Tao | @WillSawin For comparison, a Dyck path of length n is essentially a sequence $q_1,\dots,q_n$ of nonnegative integers with $q_0=q_n=0$ and $q_{i+1} \leq q_i+1$, and the number of these paths is the $n^{th}$ Catalan number. So this does hint that a bijective proof is possible, though the mod 3 constraint certainly complicates the combinatorics. | |
| Jun 23, 2023 at 15:09 | comment | added | Martin Rubey | You can use findstat to find statistics that refine @WillSawin's observation. For example, it seems that the number of 0's in a Sawin-sequence is equidistributed with findstat.org/StatisticsDatabase/St000056. There might be better statistics, however. | |
| Jun 23, 2023 at 15:07 | comment | added | Terry Tao | As observed in the OEIS, the generating function $A(x)$ for $a$ solves a cubic equation $x^2A(x)^3 + (4x^2-3x+1) A(x)^2 + (5x^2-3x) A(x) + 2 x^2 = 0$. It appears that there is a system of three linear equations relating the three generating functions $F_i(x,y) := \sum_{n=0}^\infty \sum_{q \geq 0: q = i \hbox{ mod } 3} R(n,q) x^n y^q$, $i=0,1,2$ to each other; solving for this and then evaluating $F_0(x,0)$ should in principle recover the above cubic equation if your conjecture is correct (possibly after solving an integral or differential equation). It's a lengthy calculation though. | |
| Jun 23, 2023 at 12:12 | comment | added | Will Sawin | $R(n,0)$ is the number of sequences $q_1,\dots, q_n$ of nonnegative integers with $q_1=0$ and $q_{i+1} \leq q_i+ q_i \bmod 3 +1$. Maybe this could be used to give a bijective proof or one could find a different formula to enumerate such sequences and compare. | |
| Jun 23, 2023 at 12:06 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 4 characters in body
|
| Jun 23, 2023 at 11:45 | comment | added | Jeroen van der Meer | Nice question. How did you come up with this conjecture? | |
| Jun 23, 2023 at 11:42 | comment | added | Notamathematician | @TomCopeland, thank you for comment! Done. | |
| Jun 23, 2023 at 11:41 | history | edited | Notamathematician | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Jun 22, 2023 at 4:47 | history | asked | Notamathematician | CC BY-SA 4.0 |