The tennis ball problem (Q696915): Difference between revisions

In how many ways can \(n\) numbers be chosen from the set \(\{1,2,\dots, ns\}\) so that the \(k\)th number chosen does not exceed \(ks\)? And what is the total sum, over all these choices, of the numbers chosen? These problems were solved for \(s=2\) in [\textit{C. L. Mallows} and \textit{L. Shapiro}, Balls on the lawn, J. Integer Seq. 2 (1999; Zbl 0923.05004)], where the numbers are labels on tennis balls to be thrown out the window onto the lawn. The article under review solves these two problems for general \(s\), employing ``the notion of generating trees to obtain a solution in terms of generating functions'' (quoted from the abstract). The number of choices is shown to be equal to the number of \(s\)-ary trees with \(n+1\) nodes and the total sum is given as a formula in terms of this number and the sum of \(n+2\) other numbers. Asymptotic results are given and a related problem is solved for a special case.