User martin rubey - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T21:48:09Z http://mathoverflow.net/feeds/user/3032 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/127820/approximating-rational-generating-functions/127826#127826 Answer by Martin Rubey for Approximating rational generating functions Martin Rubey 2013-04-17T11:45:01Z 2013-04-17T11:45:01Z <p>This is called Padé approximation. There are several computer packages that can do that, in particular GFUN (Salvy and Zimmermann) for maple, Guess (Kauers) for mathematica, in FriCAS it's built-in (the function is called guessPade). You can access the latter also from sage, although very likely there is something built-in too.</p> http://mathoverflow.net/questions/126577/divisibility-relation-for-spanning-trees-of-a-graph/126600#126600 Answer by Martin Rubey for Divisibility Relation for Spanning Trees of a Graph Martin Rubey 2013-04-05T10:18:02Z 2013-04-05T10:18:02Z <p>The answer is actually as nice as could be. The number of spanning trees of $G_n$ is</p> <p>$$\frac{1}{3^n}2^{n 2^{n-1}}\prod_{k=0}^{n-1} \big(1-(-2)^{k-n}\big)^{\binom{n}{k}}$$</p> <p>This follows directly from the theorems in the comment above. The divisibility (what a beautiful word!) properties then follow from the formula.</p> http://mathoverflow.net/questions/124633/generalizations-of-greenes-theorem-for-the-robinson-schensted-correspondence/124651#124651 Answer by Martin Rubey for Generalization's of Greene's Theorem for the Robinson-Schensted correspondence Martin Rubey 2013-03-15T20:19:39Z 2013-03-16T21:38:59Z <p>For RSK the answer is "well known". You can find the statements neatly arranged in an article by Christian Krattenthaler <a href="http://arxiv.org/abs/math/0510676" rel="nofollow">http://arxiv.org/abs/math/0510676</a>.</p> <p>I think the right framework for this question is Sergey Fomin's theory of dual graded graphs. However, I don't think there are many other insertion algorithms where the Greene-Kleitman invariant is known. One is the insertion algorithm for shifted tableaux, and another, easy one is the pair (BinTree, BinWord).</p> <p>In fact, whenever you have such a Greene-Kleitman invariant and whenever this invariant behaves well with respect to "promotion", you are in a good position to get a result parallel to <a href="http://arxiv.org/abs/math/0604140" rel="nofollow">http://arxiv.org/abs/math/0604140</a>. For the pair (BinTree, BinWord) this is indeed the case (and interesting), but I never managed to write it up due to time constraints...</p> <p>For Edelman-Greene the story is slightly different I think. If I recall correctly you can say at least a little bit about the shape of the word by staring long enough at the article by Christian Stump and Luis Serrano <a href="http://arxiv.org/abs/1009.4690" rel="nofollow">http://arxiv.org/abs/1009.4690</a> or myself <a href="http://arxiv.org/abs/1009.3919" rel="nofollow">http://arxiv.org/abs/1009.3919</a>.</p> <p>EDIT:</p> <p>The Kleitman Greene invariants for some insertion algorithms (<strong>for the standard case</strong>, i.e., where the words are permutations) are described in Sergey Fomin's paper <a href="ftp://192.43.228.178/pub/EMIS/journals/JACO/Volume4_1/j3330612tm0w1m47.fulltext.pdf" rel="nofollow">"Schensted algorithms for dual graded graphs"</a>:</p> <p>1) Theorem 4.4.4: Young-Fibonacci insertion (due to Tom Roby and Sergey Fomin, perhaps the invariant for Janvier Nzeutchap's algorithm is different).</p> <p>2) Just below Proposition 4.5.2: Shifted insertion (attributed to Worley and Bruce Sagan, see Richard Stanley's answer for the description in the semistandard case due to Luis Serrano)</p> <p>3) Proposition 4.6.2: (BinTree, BinWord)-insertion (independently due to Xavier Viennot)</p> <p>I'd be interested in learning about Kleitman-Greene invariants for other insertion algorithms. In particular, is it known for domino insertion (as described by <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r15" rel="nofollow">Marc van Leeuwen</a>, see also <a href="http://arxiv.org/abs/math/0308265" rel="nofollow">this paper</a> by Thomas Lam)</p> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics A list of symmetric statistics Martin Rubey 2012-07-03T23:08:37Z 2012-07-08T14:04:45Z <p>I would like to have a list of pairs (or tuples) of combinatorial statistics that are (known or conjectured) to have symmetric distribution. Ideally, something like this has already been compiled, otherwise, maybe <a href="http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics" rel="nofollow">this</a> is the place to do so.</p> <p>Some examples:</p> <ul> <li><p>on Dyck paths: area and bounce, returns to the axis and length of the last descent</p></li> <li><p>on permutations: major index and number of inversions</p></li> <li><p>on perfect matchings, set partitions and permutations: crossings and nestings, the maximal crossing number and the maximal nesting number</p></li> </ul> <p>Maybe it's best to have one family of objects per answer. Edit: originally, I had only <em>joint</em> symmetric distribution in mind. However, lists of equidistributed tuples are also very good to have. Please indicate in your answer what your tuple satisfies! </p> <p>Definitions:</p> <p>Statistics $stat_1,stat_2,\dots,stat_n$ on a set $X$ are <em>equidistributed</em> if $$\sum_{x\in X}q^{stat_1(x)} = \sum_{x\in X}q^{stat_2(x)} = \dots \sum_{x\in X}q^{stat_n(x)}.$$</p> <p>A tuple of statistics $(stat_1,stat_2,\dots,stat_n)$ on a set $X$ has a <em>symmetric</em> distribution if its generating function $$F_{stat_1,stat_2}(q,t) := \sum_{x\in X}x_1^{stat_1(x)}x_2^{stat_2(x)}\dots x_n^{stat_n(x)}$$ is symmetric in $x_1,x_2,\dots,x_n$.</p> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101670#101670 Answer by Martin Rubey for A list of symmetric statistics Martin Rubey 2012-07-08T13:56:28Z 2012-07-08T13:56:28Z <p>Symmetric statistics on perfect matchings:</p> <ul> <li>(number of crossings, number of nestings)</li> <li>(maximal cardinality of a crossing, maximal cardinality of a nesting)</li> </ul> http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101669#101669 Answer by Martin Rubey for A list of symmetric statistics Martin Rubey 2012-07-08T13:55:50Z 2012-07-08T13:55:50Z <p>Symmetric statistics on set partitions:</p> <ul> <li>(number of crossings, number of nestings)</li> <li>(maximal cardinality of a crossing, maximal cardinality of a nesting)</li> </ul> http://mathoverflow.net/questions/95965/has-there-been-any-application-of-tensor-species Has there been any application of tensor species? Martin Rubey 2012-05-04T08:38:57Z 2012-05-04T15:41:29Z <p>Joyal's <a href="http://en.wikipedia.org/wiki/Combinatorial_species" rel="nofollow">combinatorial species</a>, endofunctors in the category of finite sets with bijections $\mathbf B$ have found numerous applications. One generalisation is given by so-called "tensor species" (also "tensorial species", or, "linear species" - not to be confused with the species on totally ordered sets in the book by Bergeron, Labelle and Leroux) which are defined as functors from $\mathbf B$ into the category of finite dimensional vector spaces (say, over the complex numbers) with linear transformations $\mathbf{Vect}$.</p> <p>I wonder whether there have been any "practical" applications of tensor species? I know of a very short list of articles dealing with them (eg. by <a href="http://www.pnas.org/content/88/21/9892.full.pdf" rel="nofollow">Méndez</a>) but hardly any spelled out examples. I wonder whether I overlooked something.</p> <p>Note that for any combinatorial species $F$ we cann regard $F[{1,2,\dots,n}]$ as a finite set with an action of the symmetric group. Similarly, if $F$ is a tensor species, we can regard $F[{1,2,\dots,n}]$ as a linear representation of the symmetric group. Thus, I am mostly interested in examples that use the combinatorial operations for greater clarity of a construction.</p> http://mathoverflow.net/questions/11249/bn-1-1-mod-n b^(n-1)=-1 mod n Martin Rubey 2010-01-09T20:47:23Z 2011-10-31T04:09:58Z <p>By Fermat's little theorem we know that</p> <p>$$b^{p-1}=1 \mod p$$</p> <p>if p is prime and $\gcd(b,p)=1$. On the other hand, I was wondering whether</p> <p>$$b^{n-1}=-1 \mod n$$</p> <p>can occur at all?</p> <p>Update: sorry, I meant n odd. Please excuse.</p> http://mathoverflow.net/questions/68206/closure-properties-of-q-differential-equations closure properties of q-differential equations Martin Rubey 2011-06-19T09:47:03Z 2011-06-19T09:47:03Z <p>I am interested in q-differential equations of the form</p> <p>$p(f(z), f(qz),\dots,f(q^kz))=0$</p> <p>where $p$ is a polynomial and $k$ an nonnegative integer. I wonder about the closure properties of the class of (formal) powers series satisfying such an equation. A bit is known when $p$ is required to be linear, see Section 3 of "A Mathematica package for q-holonomic sequences and power series" by Manuel Kauers and Christoph Koutschan.</p> <p>In particular, if $f$ and $g$ satisfy a $q$-ADE, do $f+g$, $f\cdot g$ and $f\circ h$ for suitably simple $h$, too? And if so, what is the $k$ in the resulting equations?</p> http://mathoverflow.net/questions/65363/equidistribution-of-returns-and-height-of-first-peak-of-dyck-paths Equidistribution of returns and height of first peak of Dyck paths Martin Rubey 2011-05-18T19:53:17Z 2011-05-18T20:57:32Z <p>I believe that it is "well known" that the following two statistics on Dyck paths have symmetric joint distribution:</p> <ol> <li>number of returns to the axis $RET(D)$</li> <li>height of the first peak (or length of the last descent) $HFP(D)$</li> </ol> <p>That is: $\sum_{D} x^{RET(D)}y^{HFP(D)} = \sum_{D} x^{HFP(D)}y^{RET(D)}$</p> <p>However, I could not find a reference for that. Might it be due to Kreweras?</p> http://mathoverflow.net/questions/55455/summation-of-an-expression/56068#56068 Answer by Martin Rubey for Summation of an expression Martin Rubey 2011-02-20T15:34:39Z 2011-02-20T15:34:39Z <p>It should be possible to derive the asymptotics of the expression automatically:</p> <p>1) let the computer guess and prove a recurrence for the expression, which is P-recursive in $n$.</p> <p>2) use Doron Zeilberger's package <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/asy.html" rel="nofollow">asyrec</a> for Maple to obtain the asymptotics (but not the constant term, unfortunately)</p> <p>3) try to guess the constant term...</p> <p>I did only part one, for your convenience I post the complete code. (in FriCAS, Bruno Salvy's gfun for Maple and Manuel Kauers' guess for Mathematica should work just as well. In fact, FriCAS is not particularly well suited because it does not yet support multivariate guessing...)</p> <p>Setup:</p> <pre> )expose RECOP f := operator 'f; ops := [N^l for l in 0..2]; vars := [f(n+l) for l in 0..2]; </pre> <p>Guess the recurrences for each $k$ separately (and transform the results into operator notation for easier postprocessing:</p> <pre> g(n,k) == reduce(+, [j^k/factorial(j-1) for j in 1..n], 0) r := [eval(getEq first guessPRec([g(n,k) for n in 0..100], maxShift==2), vars, ops)::UP(N, POLY INT)::UP(N, FR POLY INT) for k in 1..15] </pre> <p>The result is (showing only $k=1..4$)</p> <pre> 2 2 2 [(n + 1) N - (n + 3n + 3)N + n + 2, 3 2 3 2 2 (n + 1) N - (n + 4n + 7n + 5)N + (n + 2) , 4 2 4 3 2 3 (n + 1) N - (n + 5n + 12n + 16n + 9)N + (n + 2) , 5 2 5 4 3 2 4 (n + 1) N - (n + 6n + 18n + 34n + 37n + 17)N + (n + 2) , </pre> <p>So the coefficients of $N^2$ (i.e., $f(n+2)$) and $N^0$ (i.e., $f(n)$) are obvious. The coefficient of $N$ turns out to have a rational generating function:</p> <pre> guessPade([coefficient(t, 1) for t in r], indexName=='k) </pre> <p>resulting in</p> <pre> 2 2 k (n + 1)(n + 2) x - (n + 3n + 3) [[x ]--------------------------------] 2 (n + 1)(n + 2)x - (2n + 3)x + 1 </pre> http://mathoverflow.net/questions/55616/fixed-points-and-the-cycle-index fixed points and the cycle index Martin Rubey 2011-02-16T13:37:12Z 2011-02-16T14:09:14Z <p>Let $C_n$ be the cyclic group of order $n$ acting on a finite set $X$ and let $Z(C_n, X; p_1,p_2,\dots)$ be the cycle index of the corresponding permutation group.</p> <p>I wonder whether the knowledge of the cycle index alone is enough to determine the number of fixed points of the action of a given element $g\in C_n$ on $X$?</p> http://mathoverflow.net/questions/54221/does-the-j-invariant-satisfy-a-rational-differential-equation/54312#54312 Answer by Martin Rubey for does the j-invariant satisfy a rational differential equation? Martin Rubey 2011-02-04T13:45:35Z 2011-02-04T13:45:35Z <p>(this is too long for a comment)</p> <p>Here is the explicit equation of order three for the $q$-expansion of $j$ multiplied by $q$. Keep in mind that this does not prove that there is no order one differential equation, so it is not an answer to the question.</p> <pre> n [x ]f(x): 3 4 4 3 5 2 , 2 5 (2x f(x) - 6912x f(x) + 5971968x f(x) )f (x) - 2x f(x) + 3 4 4 3 6912x f(x) - 5971968x f(x) * ,,, f (x) + 3 4 4 3 5 2 ,, 2 (- 3x f(x) + 10368x f(x) - 8957952x f(x) )f (x) + 2 4 3 3 4 2 , 5 (6x f(x) - 20736x f(x) + 17915904x f(x) )f (x) - 6x f(x) + 2 4 3 3 20736x f(x) - 17915904x f(x) * ,, f (x) + 3 2 4 5 , 4 (x f(x) - 1968x f(x) + 2654208x )f (x) + 2 3 3 2 4 , 3 (- 4x f(x) + 7872x f(x) - 10616832x f(x))f (x) + 4 2 3 3 2 , 2 (5x f(x) - 8352x f(x) + 12939264x f(x) )f (x) + 5 4 2 3 , 5 4 (- 2f(x) + 960x f(x) - 4644864x f(x) )f (x) + 1488f(x) - 331776x f(x) = 0 , 2 3 4 f(x)= 1 + 744x + 196884x + 21493760x + O(x )] </pre> http://mathoverflow.net/questions/52899/examples-of-two-different-descriptions-of-a-set-that-are-not-obviously-equivalent/53032#53032 Answer by Martin Rubey for Examples of two different descriptions of a set that are not obviously equivalent? Martin Rubey 2011-01-24T08:02:53Z 2011-01-24T08:02:53Z <p>For Question 2, you may want to look at</p> <p><a href="http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAJ0146" rel="nofollow">http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAJ0146</a></p> <p>(and the reference given in the abstract).</p> http://mathoverflow.net/questions/51132/algorithm-for-summing-certain-sums-involving-the-floor-function/51153#51153 Answer by Martin Rubey for Algorithm for summing certain sums involving the floor function Martin Rubey 2011-01-04T19:53:39Z 2011-01-04T19:53:39Z <p>It seems to me that at least for $k_0=0$ these sums always satisfy a linear recurrence. Maybe one can guess the general form of this recurrence. For example (using FriCAS):</p> <pre> (1) -> )expose RECOP (1) -> floorsum(p, q, k, n) == reduce(+, [floor(i*p/q)^k for i in 0..n]) (2) -> guessEq(p, q, k) == (N := 50; while empty?(e := guessPRec([floorsum(13, 17, k, n) for n in 0..N], safety==100, maxDegree==0)) repeat N := N+1; getEq first e = 0) (3) -> guessEq(13,17,0) (3) - f(n + 1) + f(n) + 1= 0 (4) -> guessEq(13,17,1) (4) - f(n + 18) + f(n + 17) + f(n + 1) - f(n) + 13= 0 (5) -> guessEq(13,17,2) (5) - f(n + 35) + f(n + 34) + 2f(n + 18) - 2f(n + 17) - f(n + 1) + f(n) + 338= 0 (6) -> guessEq(13,17,3) (6) - f(n + 52) + f(n + 51) + 3f(n + 35) - 3f(n + 34) - 3f(n + 18) + 3f(n + 17) + f(n + 1) - f(n) + 13182 = 0 (7) -> guessEq(13,17,4) (7) - f(n + 69) + f(n + 68) + 4f(n + 52) - 4f(n + 51) - 6f(n + 35) + 6f(n + 34) + 4f(n + 18) - 4f(n + 17) - f(n + 1) + f(n) + 685464 = 0 (9) -> guessEq(13,17,5) (9) - f(n + 86) + f(n + 85) + 5f(n + 69) - 5f(n + 68) - 10f(n + 52) + 10f(n + 51) + 10f(n + 35) - 10f(n + 34) - 5f(n + 18) + 5f(n + 17) + f(n + 1) - f(n) + 44555160 = 0 (12) -> guessPRec [1,13,338,13182,685464,44555160] (12) [[f(n): - f(n + 1) + (13n + 13)f(n)= 0,f(0)= 1]] (13) -> guessPRec [1,18,35,52,69,86] (13) [17n + 1] </pre> http://mathoverflow.net/questions/49233/name-of-an-operation-on-graphs/49322#49322 Answer by Martin Rubey for Name of an operation on graphs Martin Rubey 2010-12-13T22:35:49Z 2010-12-14T10:25:06Z <p>In Spectra of graphs: theory and application, Dragoš M. Cvetković, Michael Doob, Horst Sachs, pg. 52, Section 2.1 "The polynomial of a Graph", it's called product and denoted $G_1\cdot G_2$.</p> <p>I would hesitate to call it composition, lest it is confused with the lexicographic product, which is, however, denoted $G_1[G_2]$ in the reference above.</p> <p>Edit: maybe, to distinguish it from other products, call it "matrix product of graphs"?</p> http://mathoverflow.net/questions/47611/exact-formulas-for-the-partition-function/47706#47706 Answer by Martin Rubey for Exact formulas for the partition function? Martin Rubey 2010-11-29T18:31:37Z 2010-11-30T08:26:18Z <p>I'm not sure whether this should be a comment or an answer: it is curiously missing from all the links above that the generating function for integer partitions satisfies a reasonably nice (order four, homogeneous of degree four) algebraic differential equation:</p> <p><code>\begin{multline*} 4F^3 F'' + 5x F^3 F''' + x^2 F^3 F^{(\rm iv)} - 16F^2 F'^2 - 15x F^2 F' F'' + 20x^2 F^2 F' F'''\\ - 39x^2 F^2 F''^2 + 10x F F'^3 + 12x^2 F F'^2 F'' + 6x^2 F'^4 = 0 \end{multline*}</code></p> <p>There is actually also an order three differential equation, but it's not as nice.</p> <p>According to Don Zagier [The 1-2-3 of modular forms, Section 5.1, Proposition 15] already Ramanujan knew that every modular and every quasi-modular form on $\Gamma_1$ satisﬁes a third order algebraic diﬀerential equation. The equation above is found given the first 39 terms by </p> <pre> guessADE([partition n for n in 0..39], homogeneous==4) </pre> <p>from FriCAS in less than 0.01 seconds.</p> http://mathoverflow.net/questions/47044/what-are-some-early-examples-of-creation-of-lists-catalogues-of-particularly/47068#47068 Answer by Martin Rubey for What are some early examples of creation of lists / catalogues of (particularly) combinatorial objects? Martin Rubey 2010-11-23T08:06:54Z 2010-11-23T08:06:54Z <pre> @book {MR0357292, AUTHOR = {Sloane, N. J. A.}, TITLE = {A handbook of integer sequences}, PUBLISHER = {Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London}, YEAR = {1973}, PAGES = {xiii+206}, MRCLASS = {10A40 (05AXX 65A05)}, MRNUMBER = {0357292 (50 \#9760)}, } </pre> <p>It is a predecessor of the <a href="http://oeis.org/" rel="nofollow">online encyclopedia of integer sequences</a>, of course. As intermediate step, there is the sequel</p> <pre> @book {MR1327059, AUTHOR = {Sloane, N. J. A. and Plouffe, Simon}, TITLE = {The encyclopedia of integer sequences}, NOTE = {With a separately available computer disk}, PUBLISHER = {Academic Press Inc.}, ADDRESS = {San Diego, CA}, YEAR = {1995}, PAGES = {xiv+587}, ISBN = {0-12-558630-2}, MRCLASS = {11-00 (05A10 11B83 11Y55)}, MRNUMBER = {1327059 (96a:11001)}, MRREVIEWER = {P{\'e}ter Kiss}, } </pre> http://mathoverflow.net/questions/45145/can-the-newtons-identities-and-dodgsons-condensations-be-proved-by-gessel-vienn/45158#45158 Answer by Martin Rubey for can the Newton's identities and Dodgson's condensations be proved by Gessel-Viennot's lemma? Martin Rubey 2010-11-07T11:19:47Z 2010-11-07T11:19:47Z <p>I think that <a href="http://arxiv.org/abs/1010.3860" rel="nofollow">Viewing determinants as nonintersecting lattice paths yields classical determinantal identities bijectively</a> by Markus Fulmek is your friend.</p> http://mathoverflow.net/questions/40348/proving-that-a-poset-is-a-lattice Proving that a poset is a lattice Martin Rubey 2010-09-28T17:19:24Z 2010-10-10T06:04:13Z <p>I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably simple, but it seems not so easy to find out whether one element is smaller than the other, let alone find the meet (or join) of two elements. However, it is (relatively) easy to see that the poset has a minimum and a maximum.</p> <p>I wonder whether there are standard techniques for proving that a poset is a lattice, that do not need knowledge about how the meet of two elements looks like. (In fact, any example would be very helpful.)</p> <p>Some more hints: </p> <ol> <li><p>I don't see a way to embed the poset in a larger lattice...</p></li> <li><p>the poset is (in general) not self-dual, but the dual poset is itself a member of the set of posets I am looking at.</p></li> <li><p>to get an idea, <a href="http://service.ifam.uni-hannover.de/~rubey/poset.pdf" rel="nofollow">here</a> is a picture of one example (produced by sage-combinat and dot2tex)</p></li> </ol> http://mathoverflow.net/questions/40600/a-poset-with-small-cycles a poset with small "cycles" Martin Rubey 2010-09-30T11:02:45Z 2010-09-30T14:18:06Z <p>(a followup to <a href="http://mathoverflow.net/questions/40348/proving-that-a-poset-is-a-lattice" rel="nofollow">this recent question</a>)</p> <p>I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that...):</p> <p>Suppose that $z$ is covered by $x$ and $y$. Then there is a common upper bound $w$ of $x$ and $y$ such that either</p> <ul> <li>$w$ covers both $x$ and $y$, or</li> <li>$w$ covers either $x$ or $y$ (say $y$), and the other element is separated from $w$ by exactly one more element (say $a$).</li> </ul> <p>(There is <a href="http://service.ifam.uni-hannover.de/~rubey/poset.pdf" rel="nofollow">an example poset</a>, computed using sage-combinat and dot2tex)</p> <p>Using ASCII art, all relations are covering:</p> <pre> w w / \ / \ x y or a | \ / | | z x y \ / z </pre> <p>Does this property have some name? Could it be helpful for proving that the poset is a lattice?</p> <p>Although it's rather trivial, let us note that there are non-lattices having this property:</p> <pre> 1 / \ 2 3 |\ /| |/ \| 4 5 \ / 6 </pre> <p>Hm, could it be that such a poset (i.e., with restricted cycle lengths) and with no occurrences of</p> <pre> a b a d |\ /| and |\ /| |/ \| b \/ | c d | /\ | c e </pre> <p>is a lattice...? No, this is not the case:</p> <pre> 1 /|\ / | \ / | \ 2 3 4 |\ / \ /| |/ \ / \| 5 6 7 \ / \ / 8 9 \ / 0 </pre> http://mathoverflow.net/questions/37787/proving-a-hypergeometric-function-identity/37791#37791 Answer by Martin Rubey for Proving a hypergeometric function identity Martin Rubey 2010-09-05T13:20:49Z 2010-09-05T13:20:49Z <p>As Robin pointed out already, it is sufficient to note that both sides satisfy a linear differential equation, since the hypergeometric functions, sine and cosine do so, and power series satisfying linear differential equations are closed under addition and multiplication.</p> <p>You only have to find bounds for order and coefficient degree, and check appropriately many Taylor coefficients. gfun for maple and generatingFunctions for mathematica do it for you...</p> http://mathoverflow.net/questions/37253/trying-to-sum-a-series-related-to-catalan-numbers-perhaps/37255#37255 Answer by Martin Rubey for Trying to sum a series (related to catalan numbers perhaps) Martin Rubey 2010-08-31T12:04:23Z 2010-08-31T12:04:23Z <p>edit: the preceding answer suggests that my browser didn't display the dots, i.e. you really meant the series, not the sequence... Sorry, the below doesn't answer the question.</p> <hr> <p>Does the following look right? (might this be homework?)</p> <pre> (1) -> f n == reduce(+, [binomial(2*i, i)*2^i/3^(2*i) for i in 0..n]) Type: Void (2) -> guess([f n for n in 0..20], maxLevel==2) Compiling function f with type NonNegativeInteger -> Fraction( Integer) s - 1 21 8p + 12 ++-++ 20 4 | | --------- | | 9p + 18 n - 1 p = 0 20 --+ 20 (2) [ > ------------------- + 1] --+ 9 s = 0 21 Type: List(Expression(Integer)) (3) -> guessPRec [f n for n in 0..20] (3) [ [f(n): (9n + 18)f(n + 2) + (- 17n - 30)f(n + 1) + (8n + 12)f(n)= 0, 13 f(0)= 1, f(1)= --] 9 ] Type: List(Expression(Integer)) </pre> <p>In general, it's often a good idea to generalise, i.e., introduce more parameters:</p> <pre> (4) -> f n == reduce(+, [binomial(2*i, i)*x^i/y^(2*i) for i in 0..n]) Compiled code for f has been cleared. 1 old definition(s) deleted for function or rule f Type: Void (5) -> guess([f n for n in 0..20], maxLevel==2) Compiling function f with type NonNegativeInteger -> Fraction( Polynomial(Integer)) s - 1 21 (4p + 6)x ++-++ 20 2x | | ----------- | | 2 n - 1 p = 0 (p + 2)y --+ 20 20 (5) [ > ---------------------- + 1] --+ 2 s = 0 y 21 Type: List(Expression(Integer)) (6) -> guessPRec [f n for n in 0..20] (6) [ [ f(n): 2 2 (n + 2)y f(n + 2) + ((- n - 2)y + (- 4n - 6)x)f(n + 1) + (4n + 6)x f(n) = 0 , 2 y + 2x f(0)= 1, f(1)= -------] 2 y ] Type: List(Expression(Integer)) </pre> http://mathoverflow.net/questions/36207/finding-a-recursion-for-a-sum-of-legendre-polynomials/36268#36268 Answer by Martin Rubey for Finding a recursion for a sum of Legendre polynomials Martin Rubey 2010-08-21T09:47:23Z 2010-08-21T19:29:20Z <p>(this is a variation on Darij's answer)</p> <p>Note that "holonomic" generating functions $f(x)$, i.e. generating functions satisfying a linear differential equation with polynomial coefficients (in $x$) enjoy rich closure properties.<br> For a (very brief) summary, see <a href="http://arxiv.org/pdf/math/0702086.pdf" rel="nofollow">Table 1 of a paper on guessing</a> (sorry, I couldn't find a better reference, but there should be one...). Moreover, all these closure properties can be made "effective": if we know the order and the degree of the coefficients of the diffential equation for $f(x)$ and for $g(x)$, we can (easily) compute bounds for order and coefficient degree of the differential equation for $f+g$, $f\cdot g$, etc.</p> <p>Moreover, it turns out that the (Taylor) coefficient sequence of a holonomic generating function satisfies a linear recurrence with polynomial coefficients, i.e., is P-recursive, and the P-recursive sequences are precisely the coefficient sequences of holonomic generating functions.</p> <p>Thus, to find such a recurrence (or differential equation), it is often easiest to use <a href="http://algo.inria.fr/libraries/papers/gfun.html" rel="nofollow">gfun for Maple</a> by Bruno Salvy and Paul Zimmermann, or the Mathematica equivalent by Mallinger (I think). Unfortunately, the FriCAS package described in <a href="http://arxiv.org/pdf/math/0702086.pdf" rel="nofollow">1</a> only does the guessing part, i.e., you would need to compute the bounds yourself and then check. In the case at hand the results are below.</p> <p>However, you also asked, whether the solution is hypergeometric. To check this, you simply feed the recurrence you found below into Petkovsek's program <a href="http://www.fmf.uni-lj.si/~petkovsek/software.html" rel="nofollow">Hyper</a>, it will tell you whether there is a hypergeometric solution. (most probably no, because if the degree of the coefficient polynomials of the hypergeometric solution are not huge, guessPRec and guessHolo would have found it.)</p> <p>In case you are dealing with orthogonal polynomials, the <a href="http://www.cs.vu.nl/~rene/Onderzoek/AW.html" rel="nofollow">Askey Wilson scheme</a> by Koekoek and Swarttouw is a great reference to find the basic information.</p> <pre> (1) -> guessHolo(cons(x, [(legendreP(n, x)-(1-1/n)*legendreP(n-2, x)) for n in 2..30]), variableName==t) (1) [ [ n [t ]f(t): 4 2 2 5 3 4 2 ,, ((- 2t - 2t )x + (t + 6t + t)x - 2t - 2t )f (t) + 3 2 4 2 3 , ((- 3t - 7t)x + (3t + 15t + 2)x - 8t - 2t)f (t) + 2 2 3 2 ((t - 3)x + (t + 3t)x - 4t + 2)f(t) = 0 , 2 2 3 2 3 4 3 2 3 3t x - 2t 15t x - 13t x 35t x - 39t x + 6t 4 f(t)= x + ---------- + -------------- + --------------------- + O(t )] 2 6 8 ] Type: List(Expression(Integer)) (2) -> guessPRec cons(x, [(legendreP(n, x)-(1-1/n)*legendreP(n-2, x)) for n in 2..30]) (2) [ [ f(n): 4 3 2 2 4 3 2 ((4n + 28n + 67n + 63n + 18)x - 4n - 28n - 68n - 68n - 24) * f(n + 2) + 4 3 2 3 (- 8n - 52n - 118n - 107n - 30)x + 4 3 2 (8n + 52n + 120n + 114n + 36)x * f(n + 1) + 4 3 2 2 4 3 2 ((4n + 24n + 51n + 46n + 15)x - 4n - 24n - 52n - 48n - 16)f(n) = 0 , 2 3x - 2 f(0)= x, f(1)= -------] 2 ] Type: List(Expression(Integer)) </pre> http://mathoverflow.net/questions/34826/inversion-of-a-convolution "inversion" of a convolution Martin Rubey 2010-08-07T10:11:21Z 2010-08-09T12:03:45Z <p>I have the following relation:</p> <p>$$\sum_{d|n} (1+1/x)^{d-1} F_{n/d}(x^d)=L_n(x)$$</p> <p>where the right hand side is (for every $n$) a polynomial in $x$, which I have an expression for, but it's not extremely beautiful. The family of polynomials $F_k(x)$ is unknown, and is what I'm looking for.</p> <p>Since this is close to Dirichlet convolution, I have not quite given up hope that there is something similar to Möbius inversion, that would give me $F_k(x)$ explicitely. Is this possible? Related instances of such a problem may also be interesting.</p> <p>A possibly weaker, but still sufficient solution would be an expression in terms of $L_k$ and $R_k$ of the expression</p> <p>$$\sum_{d|n} R_d(x) F_{n/d}(x^d)$$</p> <p>where $R_k(x)$ is another family of polynomials, which is also unknown.</p> http://mathoverflow.net/questions/34826/inversion-of-a-convolution/34979#34979 Answer by Martin Rubey for "inversion" of a convolution Martin Rubey 2010-08-09T08:12:57Z 2010-08-09T12:03:45Z <p>At least computing $F_k(x)$ turned out not to be that hard after all. Slightly more generally, consider</p> <p>$$\sum_{d|k} Z_d(x) F_{n/d}(x^d) = L_n(x),$$ with $Z_1(x)=1$.</p> <p>Then we have $$F_n(x)=\sum_{1=d_0|d_1|\dots|d_k|n}L_{n/d_k}(x^{d_k}) (-1)^k\prod_{i=0}^{k-1} Z_{d_{i+1}/d_i}(x^{d_i}),$$</p> <p>where in the sum $d_0 &lt; d_1 &lt; \dots &lt; d_k \leq n$. In other words, we are summing over all chains starting at $1$, below $n$. The formula is easily shown by induction.</p> http://mathoverflow.net/questions/32020/finding-recurrence-relation-for-a-sequence-of-polynomials/34589#34589 Answer by Martin Rubey for Finding recurrence relation for a sequence of polynomials Martin Rubey 2010-08-05T07:57:17Z 2010-08-05T07:57:17Z <p>Using <a href="http://fricas.sourceforge.net/" rel="nofollow">FriCAS</a>, one can indeed guess a q-recurrence, given the first 50 terms or so. It is not nice, though. The command issued is</p> <p><code>guessHolo(q)(cons(1, [qRiordan n for n in 1..60]), debug==true, safety==10)</code></p> <p>for the q-differential equation (a linear combination with polynomial coefficients of $f(x), f(qx),\dots,f(q^5 x)$, degree in $x$ is 6), or</p> <p><code>guessPRec(q)(cons(1, [qRiordan n for n in 1..48]), debug==true, safety==2)</code></p> <p>for the q-recurrence.</p> http://mathoverflow.net/questions/32131/algebraic-dirichlet-series-and-beyond Algebraic Dirichlet series and beyond Martin Rubey 2010-07-16T08:24:47Z 2010-07-16T09:35:38Z <p>I wonder what the "right" notion of "algebraic Dirichlet series" might be. Here I'm thinking of formal Dirichlet series $D(s)=\sum_{n\geq 1} a_n/n^s$, say with $a_n$ being rational numbers. </p> <p>I'm trying to figure out an analogon for the rich class of algebraic formal power series $A(z)=\sum_{n\geq 0} a_n z^n$, that satisfy a polynomial relation $p(z, A(z))=0$, for some polynomial $p$ with integer coefficients.</p> <p>The main question is, what should be the replacement of $z$? A good candidate seems to be $\zeta(s)$, i.e., maybe "algebraic" should mean "satisfying a polynomial equation $p(\zeta(s), D(s))$=0".</p> <p>More generally, what would an interesting notion of "differentially algebraic Dirichlet series", i.e., is there a good candidate for a replacement of the derivative, that plays nicely together with the replacement for $z$. It would be particularly nice if this derivative would send $z^k$ to a linear combination of smaller powers of $z$.</p> <p>Of course, most important are that such dependencies actually occur, so some nice examples beyond those on <a href="http://en.wikipedia.org/wiki/Dirichlet_series" rel="nofollow">wikipedia:Dirichlet series</a> would be very, very helpful.</p> http://mathoverflow.net/questions/28788/nontrivial-theorems-with-trivial-proofs/28919#28919 Answer by Martin Rubey for nontrivial theorems with trivial proofs Martin Rubey 2010-06-21T06:06:26Z 2010-06-21T06:06:26Z <p>Proofs of identities in line with the book A=B (Petkovsek, Wilf &amp; Zeilberger) are trivial - they amount to simple computation. However, the theorems are certainly non-trivial. It is possibly hard to find the right "Ansatz", and you need a computer to find the certificate, but checking the certificate is trivial.</p> http://mathoverflow.net/questions/26912/closed-form-for-motzkin-and-related-numbers "Closed" form for Motzkin and related numbers Martin Rubey 2010-06-03T11:41:23Z 2010-06-03T12:36:50Z <p>I wonder whether it is impossible to write the nth <a href="http://www.research.att.com/~njas/sequences/A001006" rel="nofollow">Motzkin number</a> as a sum of a fixed number of, say, hypergeometric terms. To illustrate what I mean: $n!+(2n)!$ is not a hypergeometric term, but it is written as a sum of two hypergeometric terms.</p> <p>I'd also appreciate other examples, especially if they come from counting weighted Motzkin paths.</p> http://mathoverflow.net/questions/131809/a-double-grading-of-catalan-numbers Comment by Martin Rubey Martin Rubey 2013-05-25T19:36:37Z 2013-05-25T19:36:37Z @Christian: I had a look at the zeta map but do not see your observation, I guess I'm misunderstanding something. In Jim Haglund's book there is an illustration on pg 50, but there the length of the initial rise of $\pi$ is 3 while the number of returns of $\zeta(\pi)$ is 2. Could you clarify? (Eg., does it work only in the special situation of Vince Vatter's question, and after &quot;shortening&quot; the Dyck path by omitting the first and the last step?) Thanks! http://mathoverflow.net/questions/129854/semi-standard-young-diagrams-and-families Comment by Martin Rubey Martin Rubey 2013-05-06T16:10:57Z 2013-05-06T16:10:57Z I do not understand the statement of the conjecture. How do you obtain the daughters precisely? http://mathoverflow.net/questions/129629/sum-over-hypergeometric-function-1f2 Comment by Martin Rubey Martin Rubey 2013-05-04T14:02:20Z 2013-05-04T14:02:20Z A=B by Petkkovsek, Wilf, Zeilberger? http://mathoverflow.net/questions/127974/products-of-matrices-of-a-certain-form Comment by Martin Rubey Martin Rubey 2013-04-18T16:05:02Z 2013-04-18T16:05:02Z These are special T&#246;plitz matrices. Maybe you should look at their inverses: it has -1/(x-1) on the main diagonal, 1/(x-1) on the superdiagonal and x/(x-1) in the lower left corner. All the other entries are zero. http://mathoverflow.net/questions/127100/asymptotics-of-the-number-of-non-isomorphic-equivalence-relations-and-the-number Comment by Martin Rubey Martin Rubey 2013-04-12T07:11:09Z 2013-04-12T07:11:09Z Yes............ http://mathoverflow.net/questions/127100/asymptotics-of-the-number-of-non-isomorphic-equivalence-relations-and-the-number Comment by Martin Rubey Martin Rubey 2013-04-10T16:47:18Z 2013-04-10T16:47:18Z The formula should be in Graphical Enumeration by Harary and Palmer, but I'm not sure. You can find a (sketch of a) derivation in Section 2.2 of Combinatorial Species and Tree like structures by Bergeron, Labelle and Leroux. http://mathoverflow.net/questions/126577/divisibility-relation-for-spanning-trees-of-a-graph Comment by Martin Rubey Martin Rubey 2013-04-05T07:04:29Z 2013-04-05T07:04:29Z I think you should try the Q-spectrum. See Thm 2.3 (4), Thm 2.18 and bottom of page 75, Lem 2.20 of &quot;Counting Spanning Trees&quot;, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9128" rel="nofollow">citeseerx.ist.psu.edu/viewdoc/&hellip;</a> http://mathoverflow.net/questions/126396/methods-for-solving-two-variable-recurrence Comment by Martin Rubey Martin Rubey 2013-04-03T15:45:18Z 2013-04-03T15:45:18Z Did you try generatingfunctionology? http://mathoverflow.net/questions/125846/3d-generalizations-of-permutations-rsk-correspondence-contingency-tables-etc Comment by Martin Rubey Martin Rubey 2013-03-28T19:20:31Z 2013-03-28T19:20:31Z I think that this might be what you have in mind: <a href="http://arxiv.org/abs/0805.2860" rel="nofollow">arxiv.org/abs/0805.2860</a>. In case it is, I am very interested in it myself... http://mathoverflow.net/questions/124633/generalizations-of-greenes-theorem-for-the-robinson-schensted-correspondence/124651#124651 Comment by Martin Rubey Martin Rubey 2013-03-16T15:49:46Z 2013-03-16T15:49:46Z I would be very interested in why this answer was downvoted. Could you please leave a comment? Thanks. http://mathoverflow.net/questions/124633/generalizations-of-greenes-theorem-for-the-robinson-schensted-correspondence/124651#124651 Comment by Martin Rubey Martin Rubey 2013-03-16T15:39:57Z 2013-03-16T15:39:57Z Sorry, I don't understand? http://mathoverflow.net/questions/123721/permutation-character-of-the-symmetric-group-on-subsets-of-certain-size Comment by Martin Rubey Martin Rubey 2013-03-06T19:55:48Z 2013-03-06T19:55:48Z I think it makes sense to do this with combinatorial species: the cycle index series (aka Frobenius character) of the species of sets of cardinality $k$ is $h_k$, so the species of subsets of cardinality $k$ of an $n$-element set has cycle index series $h_{n-k}\cdot h_k=h_{n-k,k}$ which equals the sum in display. http://mathoverflow.net/questions/109372/interpolating-a-sum-of-binomial-coefficients-using-a-sin-function Comment by Martin Rubey Martin Rubey 2012-10-11T13:30:58Z 2012-10-11T13:30:58Z Yes it does. All I'm saying is that $f$ and $g$ can be first understood as infinite series without changing the value. In a second step we replace $n$ in the summands by a continues variable $x$, which again doesn't change the value for integer $x$. This explains how mathematica arrives at the nice closed forms. http://mathoverflow.net/questions/109372/interpolating-a-sum-of-binomial-coefficients-using-a-sin-function Comment by Martin Rubey Martin Rubey 2012-10-11T13:03:12Z 2012-10-11T13:03:12Z For $k&gt;n$ the first binomial in $f(n)$ vanishes, for $k&gt;n-1$ the first binomial in $g(n)$ vanishes. So you can ignore the upper limit, i.e. replace it with infinity. http://mathoverflow.net/questions/101265/a-list-of-symmetric-statistics/101283#101283 Comment by Martin Rubey Martin Rubey 2012-07-04T06:00:06Z 2012-07-04T06:00:06Z Ooops, area and dinv <i>is</i> symmetric, bounce and dinv is not, sorry.