THE NUMBER OF PERMUTATIONS WITH EXACTLY-R 132-SUBSEQUENCES IS P-RECURSIVE IN THE SIZE

Proving a first nontrivial instance of a conjecture of Noonan and Zeil berger we show that the number S-r(n) of permutations of length n cont aining exactly r subsequences of type 132 is a P-recursive function of n. We show that this remains true even if we impose some restrictions on the permutations. We also show the stronger statement that the ord inary generating function G(r)(x) of S-r(n) is algebraic, in fact, it is rational in the variables x and root 1 - 4x. We use this informatio n to show that the degree of the polynomial recursion satisfied by S-r (n) is r. (C) 1997 Academic Press.