User martin rubey - MathOverflow

Answer by Martin Rubey for Approximating rational generating functions

2013-04-17T11:45:01Z

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.

Answer by Martin Rubey for Divisibility Relation for Spanning Trees of a Graph

2013-04-05T10:18:02Z

The answer is actually as nice as could be. The number of spanning trees of $G_n$ is

$$ \frac{1}{3^n}2^{n 2^{n-1}}\prod_{k=0}^{n-1} \big(1-(-2)^{k-n}\big)^{\binom{n}{k}} $$

This follows directly from the theorems in the comment above. The divisibility (what a beautiful word!) properties then follow from the formula.

Answer by Martin Rubey for Generalization's of Greene's Theorem for the Robinson-Schensted correspondence

2013-03-15T20:19:39Z

For RSK the answer is "well known". You can find the statements neatly arranged in an article by Christian Krattenthaler http://arxiv.org/abs/math/0510676.

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).

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 http://arxiv.org/abs/math/0604140. For the pair (BinTree, BinWord) this is indeed the case (and interesting), but I never managed to write it up due to time constraints...

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 http://arxiv.org/abs/1009.4690 or myself http://arxiv.org/abs/1009.3919.

EDIT:

The Kleitman Greene invariants for some insertion algorithms (for the standard case, i.e., where the words are permutations) are described in Sergey Fomin's paper "Schensted algorithms for dual graded graphs":

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).

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)

3) Proposition 4.6.2: (BinTree, BinWord)-insertion (independently due to Xavier Viennot)

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 Marc van Leeuwen, see also this paper by Thomas Lam)

A list of symmetric statistics

2012-07-03T23:08:37Z

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 this is the place to do so.

Some examples:

on Dyck paths: area and bounce, returns to the axis and length of the last descent
on permutations: major index and number of inversions
on perfect matchings, set partitions and permutations: crossings and nestings, the maximal crossing number and the maximal nesting number

Maybe it's best to have one family of objects per answer. Edit: originally, I had only joint symmetric distribution in mind. However, lists of equidistributed tuples are also very good to have. Please indicate in your answer what your tuple satisfies!

Definitions:

Statistics $stat_1,stat_2,\dots,stat_n$ on a set $X$ are equidistributed 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)}.$$

A tuple of statistics $(stat_1,stat_2,\dots,stat_n)$ on a set $X$ has a symmetric 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$.

Answer by Martin Rubey for A list of symmetric statistics

2012-07-08T13:56:28Z

Symmetric statistics on perfect matchings:

(number of crossings, number of nestings)
(maximal cardinality of a crossing, maximal cardinality of a nesting)

Answer by Martin Rubey for A list of symmetric statistics

2012-07-08T13:55:50Z

Symmetric statistics on set partitions:

(number of crossings, number of nestings)
(maximal cardinality of a crossing, maximal cardinality of a nesting)

Has there been any application of tensor species?

2012-05-04T08:38:57Z

Joyal's combinatorial species, 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}$.

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 Méndez) but hardly any spelled out examples. I wonder whether I overlooked something.

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.

b^(n-1)=-1 mod n

2010-01-09T20:47:23Z

By Fermat's little theorem we know that

$$b^{p-1}=1 \mod p$$

if p is prime and $\gcd(b,p)=1$. On the other hand, I was wondering whether

$$b^{n-1}=-1 \mod n$$

can occur at all?

Update: sorry, I meant n odd. Please excuse.

closure properties of q-differential equations

2011-06-19T09:47:03Z

I am interested in q-differential equations of the form

$p(f(z), f(qz),\dots,f(q^kz))=0$

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.

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?

Equidistribution of returns and height of first peak of Dyck paths

2011-05-18T19:53:17Z

I believe that it is "well known" that the following two statistics on Dyck paths have symmetric joint distribution:

number of returns to the axis $RET(D)$
height of the first peak (or length of the last descent) $HFP(D)$

That is: $\sum_{D} x^{RET(D)}y^{HFP(D)} = \sum_{D} x^{HFP(D)}y^{RET(D)}$

However, I could not find a reference for that. Might it be due to Kreweras?

Answer by Martin Rubey for Summation of an expression

2011-02-20T15:34:39Z

It should be possible to derive the asymptotics of the expression automatically:

1) let the computer guess and prove a recurrence for the expression, which is P-recursive in $n$.

2) use Doron Zeilberger's package asyrec for Maple to obtain the asymptotics (but not the constant term, unfortunately)

3) try to guess the constant term...

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...)

Setup:

)expose RECOP
f := operator 'f; ops := [N^l for l in 0..2]; vars := [f(n+l) for l in 0..2];

Guess the recurrences for each $k$ separately (and transform the results into operator notation for easier postprocessing:

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]

The result is (showing only $k=1..4$)

           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) ,

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:

guessPade([coefficient(t, 1) for t in r], indexName=='k)

resulting in

                   2      2
   k (n + 1)(n + 2) x - (n  + 3n + 3)
[[x ]--------------------------------]
                    2
     (n + 1)(n + 2)x  - (2n + 3)x + 1

fixed points and the cycle index

2011-02-16T13:37:12Z

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.

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$?

Answer by Martin Rubey for does the j-invariant satisfy a rational differential equation?

2011-02-04T13:45:35Z

(this is too long for a comment)

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.

       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 )]

Answer by Martin Rubey for Examples of two different descriptions of a set that are not obviously equivalent?

2011-01-24T08:02:53Z

For Question 2, you may want to look at

http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAJ0146

(and the reference given in the abstract).

Answer by Martin Rubey for Algorithm for summing certain sums involving the floor function

2011-01-04T19:53:39Z

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):

(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]

Answer by Martin Rubey for Name of an operation on graphs

2010-12-13T22:35:49Z

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$.

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.

Edit: maybe, to distinguish it from other products, call it "matrix product of graphs"?

Answer by Martin Rubey for Exact formulas for the partition function?

2010-11-29T18:31:37Z

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:

\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*}

There is actually also an order three differential equation, but it's not as nice.

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

guessADE([partition n for n in 0..39], homogeneous==4)

from FriCAS in less than 0.01 seconds.

Answer by Martin Rubey for What are some early examples of creation of lists / catalogues of (particularly) combinatorial objects?

2010-11-23T08:06:54Z

@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)},
}

It is a predecessor of the online encyclopedia of integer sequences, of course. As intermediate step, there is the sequel

@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},
}

Answer by Martin Rubey for can the Newton's identities and Dodgson's condensations be proved by Gessel-Viennot's lemma?

2010-11-07T11:19:47Z

I think that Viewing determinants as nonintersecting lattice paths yields classical determinantal identities bijectively by Markus Fulmek is your friend.

Proving that a poset is a lattice

2010-09-28T17:19:24Z

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.

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.)

Some more hints:

I don't see a way to embed the poset in a larger lattice...
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.
to get an idea, here is a picture of one example (produced by sage-combinat and dot2tex)

a poset with small "cycles"

2010-09-30T11:02:45Z

(a followup to this recent question)

I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that...):

Suppose that $z$ is covered by $x$ and $y$. Then there is a common upper bound $w$ of $x$ and $y$ such that either

$w$ covers both $x$ and $y$, or
$w$ covers either $x$ or $y$ (say $y$), and the other element is separated from $w$ by exactly one more element (say $a$).

(There is an example poset, computed using sage-combinat and dot2tex)

Using ASCII art, all relations are covering:

    w                 w 
   / \               / \
  x   y      or     a   |
   \ /              |   |
    z               x   y
                     \ /
                      z

Does this property have some name? Could it be helpful for proving that the poset is a lattice?

Although it's rather trivial, let us note that there are non-lattices having this property:

    1
   / \
  2   3
  |\ /|
  |/ \|
  4   5
   \ /
    6

Hm, could it be that such a poset (i.e., with restricted cycle lengths) and with no occurrences of

  a   b            a    d
  |\ /|     and    |\  /|
  |/ \|            b \/ |
  c   d            | /\ |
                   c    e

is a lattice...? No, this is not the case:

      1
     /|\
    / | \
   /  |  \
  2   3   4
  |\ / \ /|
  |/ \ / \|
  5   6   7
   \ / \ /
    8   9
     \ /
      0

Answer by Martin Rubey for Proving a hypergeometric function identity

2010-09-05T13:20:49Z

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.

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...

Answer by Martin Rubey for Trying to sum a series (related to catalan numbers perhaps)

2010-08-31T12:04:23Z

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.

Does the following look right? (might this be homework?)

(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))

In general, it's often a good idea to generalise, i.e., introduce more parameters:

(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))

Answer by Martin Rubey for Finding a recursion for a sum of Legendre polynomials

2010-08-21T09:47:23Z

(this is a variation on Darij's answer)

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.
For a (very brief) summary, see Table 1 of a paper on guessing (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.

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.

Thus, to find such a recurrence (or differential equation), it is often easiest to use gfun for Maple by Bruno Salvy and Paul Zimmermann, or the Mathematica equivalent by Mallinger (I think). Unfortunately, the FriCAS package described in 1 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.

However, you also asked, whether the solution is hypergeometric. To check this, you simply feed the recurrence you found below into Petkovsek's program Hyper, 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.)

In case you are dealing with orthogonal polynomials, the Askey Wilson scheme by Koekoek and Swarttouw is a great reference to find the basic information.

(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))

"inversion" of a convolution

2010-08-07T10:11:21Z

I have the following relation:

$$ \sum_{d|n} (1+1/x)^{d-1} F_{n/d}(x^d)=L_n(x) $$

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.

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.

A possibly weaker, but still sufficient solution would be an expression in terms of $L_k$ and $R_k$ of the expression

$$ \sum_{d|n} R_d(x) F_{n/d}(x^d) $$

where $R_k(x)$ is another family of polynomials, which is also unknown.

Answer by Martin Rubey for "inversion" of a convolution

2010-08-09T08:12:57Z

At least computing $F_k(x)$ turned out not to be that hard after all. Slightly more generally, consider

$$ \sum_{d|k} Z_d(x) F_{n/d}(x^d) = L_n(x), $$ with $Z_1(x)=1$.

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}), $$

where in the sum $d_0 < d_1 < \dots < 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.

Answer by Martin Rubey for Finding recurrence relation for a sequence of polynomials

2010-08-05T07:57:17Z

Using FriCAS, one can indeed guess a q-recurrence, given the first 50 terms or so. It is not nice, though. The command issued is

guessHolo(q)(cons(1, [qRiordan n for n in 1..60]), debug==true, safety==10)

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

guessPRec(q)(cons(1, [qRiordan n for n in 1..48]), debug==true, safety==2)

for the q-recurrence.

Algebraic Dirichlet series and beyond

2010-07-16T08:24:47Z

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.

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.

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".

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$.

Of course, most important are that such dependencies actually occur, so some nice examples beyond those on wikipedia:Dirichlet series would be very, very helpful.

Answer by Martin Rubey for nontrivial theorems with trivial proofs

2010-06-21T06:06:26Z

Proofs of identities in line with the book A=B (Petkovsek, Wilf & 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.

"Closed" form for Motzkin and related numbers

2010-06-03T11:41:23Z

I wonder whether it is impossible to write the nth Motzkin number 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.

I'd also appreciate other examples, especially if they come from counting weighted Motzkin paths.

Comment by Martin Rubey

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 "shortening" the Dyck path by omitting the first and the last step?) Thanks!

Comment by Martin Rubey

2013-05-06T16:10:57Z

I do not understand the statement of the conjecture. How do you obtain the daughters precisely?

Comment by Martin Rubey

2013-05-04T14:02:20Z

A=B by Petkkovsek, Wilf, Zeilberger?

Comment by Martin Rubey

2013-04-18T16:05:02Z

These are special Tö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.

Comment by Martin Rubey

2013-04-12T07:11:09Z

Yes............

Comment by Martin Rubey

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.

Comment by Martin Rubey

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 "Counting Spanning Trees", citeseerx.ist.psu.edu/viewdoc/…

Comment by Martin Rubey

2013-04-03T15:45:18Z

Did you try generatingfunctionology?

Comment by Martin Rubey

2013-03-28T19:20:31Z

I think that this might be what you have in mind: arxiv.org/abs/0805.2860. In case it is, I am very interested in it myself...

Comment by Martin Rubey

2013-03-16T15:49:46Z

I would be very interested in why this answer was downvoted. Could you please leave a comment? Thanks.

Comment by Martin Rubey

2013-03-16T15:39:57Z

Sorry, I don't understand?

Comment by Martin Rubey

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.

Comment by Martin Rubey

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.

Comment by Martin Rubey

2012-10-11T13:03:12Z

For $k>n$ the first binomial in $f(n)$ vanishes, for $k>n-1$ the first binomial in $g(n)$ vanishes. So you can ignore the upper limit, i.e. replace it with infinity.

Comment by Martin Rubey

2012-07-04T06:00:06Z

Ooops, area and dinv is symmetric, bounce and dinv is not, sorry.