Counting nondecreasing integer sequences that Lie below a barrier (Q1028841): Difference between revisions

Summary: Given a barrier \(0 \leq b_0 \leq b_1 \leq \dots\), let \(f(n)\) be the number of nondecreasing integer sequences \(0 \leq a_0 \leq a_1 \leq \dots \leq a_n\) for which \(a_j \leq b_j\) for all \(0 \leq j \leq n\). Known formulæ\ for \(f(n)\) include an \(n \times n\) determinant whose entries are binomial coefficients [\textit{G. Kreweras}, ``Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers'', Cahiers du B.U.R.O., 6 (1965)] and, in the special case of \(b_j = rj+s\), a short explicit formula (Proctor, 1988, p.320) [\textit{R.A. Proctor}, ``Odd symplectic groups'', Invent. Math. 92, No.\,2, 307--332 (1988; Zbl 0621.22009)]. A relatively easy bivariate recursion, decomposing all sequences according to \(n\) and \(a_n\), leads to a bivariate generating function, then a univariate generating function, then a linear recursion for \(\{ f(n) \}\). Moreover, the coefficients of the bivariate generating function have a probabilistic interpretation, leading to an analytic inequality which is an identity for certain values of its argument.