----------------------excerpt from a message from Mireille Bousquet-Melou Anyway, I wanted to draw your attention on a paper by Ira Gessel, Symmetric functions and P-recursiveness, JCTA 53 (1990) 257-285, where a formula is given for the number of permutations avoiding 1234 (I mean, abcd...). You don't seem to be aware of this formula (p. 281, u_3(n)). I played with it and the software GFUN, and thus obtained experimentally the recurrence you conjecture, but I am pretty sure that one of the A=B methods would prove this recurrence. --------------end excerpt-------------------------- From ira@berry.cs.brandeis.edu Tue Dec 10 17:07:06 1996 Received: from berry.cs.brandeis.edu (berry.cs.brandeis.edu [129.64.2.5]) by euclid.math.temple.edu (8.7.4/8.6.12) with ESMTP id RAA08735; Tue, 10 Dec 1996 17:07:03 -0500 (EST) Posted-Date: Tue, 10 Dec 1996 17:07:03 -0500 (EST) Received-Date: Tue, 10 Dec 1996 17:07:03 -0500 (EST) Received: from goose.cs.brandeis.edu (goose.cs.brandeis.edu [129.64.2.31]) by berry.cs.brandeis.edu (8.8.3/8.8.3) with ESMTP id RAA21901; Tue, 10 Dec 1996 17:06:46 -0500 (EST) Received: (from ira@localhost) by goose.cs.brandeis.edu (8.8.3/8.8.3) id RAA22228; Tue, 10 Dec 1996 17:06:46 -0500 (EST) Date: Tue, 10 Dec 1996 17:06:46 -0500 (EST) Message-Id: <199612102206.RAA22228@goose.cs.brandeis.edu> From: Ira Gessel To: noonan@euclid.math.temple.edu, zeilberg@euclid.math.temple.edu Subject: forbidden patterns Status: RO %Since this note has a lot of mathematics %in it, I've written it in plain TeX \magnification1200 Dear John and Doron, I haven't yet had time to read carefully your very interesting paper ``The enumeration of permutations with a prescribed number of forbidden patterns," but when I saw the table of values of $P^{(2)}(n,I)$ (Table 3), I couldn't resist the challenge of finding a formula for them. Here's what I came up with. I didn't attempt to prove it, but the proof should be ``routine." The obvious guess is that the generating function for each column is closely related to the Catalan generating function. This turns out to be true: if we substitute $x/(1+x)^2$ for $x$ and multiply by the right power of $1+x$ we get a polynomial in $x$ for each column. In fact, if we make this substitution in the 2-variable generating function for the whole table, we get a rational function. More precisely, let $$F(z,y)=\sum_{i=1}^\infty\sum_{n=0}^{\infty}P^{(2)}(n+i,i)z^n y^i,$$ and let $$G(x,y)=F\left({x\over (1-x)^2}, y\right).$$ Then $$\displaylines{\qquad(1-y)(1-y-xy)G(x,y)=x^2y^2+x^3(3y+2y^2+{y^3\over 1-y})\hfill\cr \hfill+x^4(6y-3y^2)+x^5(4y-3y^2)+x^6(y-y^2),\qquad\cr}$$ which can also be written (if I haven't made a mistake) $$\displaylines {\qquad G(x,y)=1-x+2x^2-x^3-2x^4-x^5- {x(2+3x+3x^2+x^3)\over 1-y}\hfill\cr \hfill-{x^2\over(1-y)^2}+{y-1+3x+2x^2+4x^3+3x^4+x^5\over 1-y-xy}.\qquad\cr}$$ It should be straightforward to get an explicit formula for the coefficients of $G(x,y)$, and therefore an explicit formula for the coefficients of $F(z,y)$, since if $z=x/(1+x)^2$ then $x=zC(z)^2$, where $C(z)=\bigl(1-\sqrt{1-4z}\bigr)/(2z)$ is the Catalan generating function and we have an explicit formula for the coefficients of powers of $C(z)$. I haven't actually worked out the formula, though. I suspect that the same approach will work for Table 4, though I haven't tried it. (I'm less optimistic about Table 5, though it might be worth a try.) \smallskip One more comment: in my paper ``Symmetric functions and P-recursiveness," JCT Series A 53 (1990), 257--285, I give an explicit formula (page 281) for the number of permutations of $\{1,2,\ldots,n\}$ with no increasing subsequence of length 4 (no ``$abcd$'s"): $$2\sum_{k=0}^n {3k^2+2k+1-n-2kn\over (k+1)^2(k+2)(n-k+1)}{2k\choose k}{n\choose k}^2.$$ (It's possible that a slightly simpler formula for these numbers could be found by some simple manipulation of this formula---I don't think anyone has ever tried very hard---though I don't think it will get much simpler). Using this formula, it should be ``routine" to prove the conjectured recurrence for $a^{(0)}_{1234}$ on page 17 of your paper. I also give a generating function that can be used to get an explicit formula for the number of permutations of $\{1,2,\ldots,n\}$ with no increasing subsequence of length $r$ for any $r$, though as $r$ increases the formula gets more complicated. Unfortunately the method in this paper works only for increasing subsequences, though I've always wondered whether there might be some Schensted-like approach that can be applied to other patterns. \medskip Incidentally, have you seen the recent work of Mikl\'os B\'ona (a student of Richard Stanley's)? He proved the conjectured formula on page 14 of your paper for $a^{(1)}_{312}$ (and also observed that it could be written in the simpler form $2n-3\choose n$), and also showed that the number of permutations with exactly $r$ ``$cab$ subsequences" is P-recursive for each $r$. Best regards, Ira \bye