Let the random variable Zn,k denote the number of increasing subsequences of length k in a random permutation from Sn, the symmetric group of permutations of {1, …, n}. In a recent paper [Random Structures Algorithms 29 (2006) 277–295] we showed that the weak law of large numbers holds for Zn,kn if kn=o(n2/5); that is,
¶
\[\lim_{n\to\infty}\frac{Z_{n,k_{n}}}{EZ_{n,k_{n}}}=1\qquad \mbox{in probability}.\]
¶
The method of proof employed there used the second moment method and demonstrated that this method cannot work if the condition kn=o(n2/5) does not hold. It follows from results concerning the longest increasing subsequence of a random permutation that the law of large numbers cannot hold for Zn,kn if kn≥cn1/2, with c>2. Presumably there is a critical exponent l0 such that the law of large numbers holds if kn=O(nl), with l0, and does not hold if $\limsup_{n\to\infty}\frac{k_{n}}{n^{l}}>0$ , for some l>l0. Several phase transitions concerning increasing subsequences occur at l=½, and these would suggest that l0=½. However, in this paper, we show that the law of large numbers fails for Zn,kn if $\limsup_{n\to\infty}\frac{k_{n}}{n^{4/9}}=\infty$ . Thus, the critical exponent, if it exists, must satisfy $l_{0}\in[\frac{2}{5},\frac{4}{9}]$ .