The tennis ball problem

DOI10.1006/JCTA.2002.3273MaRDI QIDQ696915zbMATH OpenOpenAlexFDO

Authors Donatella Merlini, Renzo Sprugnoli, Maria Cecilia Verri

Publication date 12 September 2002

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/2d484c68c4d7a59a960e80106fb72da406f5fc74

zbMATH Keywords

\(s\)-ary treesgenerating functionsgenerating treeson-line combinations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Review text

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.

Recommendations

• On the tennis ball problem
• scientific article; zbMATH DE number 1300641
• A Motzkin variation on the tennis ball problem.
• A solution to the tennis ball problem
• scientific article; zbMATH DE number 2114476

Cites work

• Generating trees and forbidden subsequences
• Generating trees and proper Riordan arrays
• Generating trees and the Catalan and Schröder numbers
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 1300641 (Why is no real title available?)
• scientific article; zbMATH DE number 733222 (Why is no real title available?)
• scientific article; zbMATH DE number 1156613 (Why is no real title available?)
• scientific article; zbMATH DE number 1391241 (Why is no real title available?)
• On context-free languages and push-down automata
• Riordan arrays and combinatorial sums
• The number of Baxter permutations

Cited in

(22)

• Lattice and Schröder paths with periodic boundaries
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Bijections and the Riordan group
• Finitely labeled generating trees and restricted permutations
• Proper generating trees and their internal path length
• A solution to the tennis ball problem
• The research and progress of the enumeration of lattice paths
• On the tennis ball problem
• On Removing a Ball without Disturbing the Others
• scientific article; zbMATH DE number 1300641 (Why is no real title available?)
• scientific article; zbMATH DE number 1156613 (Why is no real title available?)
• Set-valued tableaux and generalized Catalan numbers
• The Egg-Drop Numbers
• scientific article; zbMATH DE number 2114476 (Why is no real title available?)
• A Motzkin variation on the tennis ball problem.
• Root geometry of polynomial sequences. I: Type (0, 1)
• scientific article; zbMATH DE number 7471114 (Why is no real title available?)
• 312-Avoiding reduced valid hook configurations and duck words
• A finite operator approach to the tennis ball problem
• Infinite iterative processes: the tennis ball problem
• Identities induced by Riordan arrays
• Proof of a lattice paths conjecture connected to the tennis ball problem

This page was built for publication: The tennis ball problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q696915)