On an inclusion-exclusion formula based on the reflection principle

DOI10.1016/0012-365X(87)90197-XMaRDI QIDQ1821783zbMATH OpenFDO

Authors Toshihiro Watanabe, S. G. Mohanty

Publication date 1987

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(87)90197-X

zbMATH Keywords

ballot problemcounting probleminclusion-exclusion formulareflection principlesymmetric groupYoung tableau

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Review text

The n-candidate ballot problem corresponding to the standard Young tableau has been solved recently by \textit{D. Zeilberger} [Discrete Math. 44, 325-326 (1983; Zbl 0508.05008)] by using the reflection principle. In this paper, a refinement of Zeilberger's approach is provided in which the reflection principle is formulated through the symmetric group and an inclusion-exclusion formula for the counting problem is developed. This approach reveals the nature in which successive applications of the reflection principle work.

Recommendations

• A new method for solving a class of ballot problems
• The Ballot Problem Revisited
• scientific article; zbMATH DE number 464791
• scientific article; zbMATH DE number 3900762
• Four Proofs of the Ballot Theorem

Cites work

• A k-Sample Extension of the One-sided Two-Sample Smirnov Test Statistic
• A combinatorial problem
• A probabilistic proof of a formula for the number of Young tableaux of a given shape
• Andre's reflection proof generalized to the many-candidate ballot problem
• Coincidence probabilities
• scientific article; zbMATH DE number 3165539 (Why is no real title available?)
• scientific article; zbMATH DE number 3874302 (Why is no real title available?)
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 2003146 (Why is no real title available?)
• scientific article; zbMATH DE number 3075369 (Why is no real title available?)
• Some Aspects of the Random Sequence
• The Degree Formula for the Skew-Representations of the Symmetric Group
• The Hook Graphs of the Symmetric Group

Cited in

(11)

• Enumeration of lattice paths and generating functions for skew plane partitions
• On the product of a Schur function and a skew Schur function
• An improvement of the inclusion-exclusion principle
• Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval
• On the Littlewood-Richardson rule in terms of lattice path combinatorics
• Lost (and Found) in Translation: André's Actual Method and Its Application to the Generalized Ballot Problem
• Random Walk in a Weyl Chamber
• scientific article; zbMATH DE number 464791 (Why is no real title available?)
• Simplifying Inclusion–Exclusion Formulas
• Random walks in Weyl chambers and the decomposition of tensor powers
• A history and a survey of lattice path enumeration

This page was built for publication: On an inclusion-exclusion formula based on the reflection principle

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