Revisiting Narayana's Approach to the Chung-Feller Theorem

Document Type : Original Paper


Department of mathematics, Shahid Chamran University of Ahvaz, Ahvaz, Iran


Using cyclic permutations, Narayana investigated the relation between the area under north-east paths from the origin to the point (n,n) and the number of the flaws of the paths. His result implies a proof to the Chung-Feller Theorem. In this paper by revising the Narayana's approach, we offer short proofs to the theorems of Narayana and Chung-Feller.


Main Subjects

[1] Chung, K. L. and Feller, W. (1949). On fluctuations in coin-tossing. Proc. Nat. Acad. Sci. U. S. A., 35, 605-608.
[2] Chen, Y. M. (2008). The Chung-Feller theorem revisited. Disc. Math., 308, 1328-1329.
[3] Hodges, J. (1955). Galton’s rank-order test. Biometrika, 42(1/2), 261-262.
[4] Krattenthaler, C. (2015). Lattice path enumeration. Handbook of Enumerative Combinatorics, M. Bona, Discrete Math. and Its Appl. CRC Press, Boca Raton London-New York. 589-678.
[5] MacMahon, P. (1909). Memoir on the theory of the partitions of numbers. Part IV. Phil. Trans. R. Soc. A 209, 153-175.
[6] Montagh, B. (1991). A simple proof and a generalization of an old result of Chung and Feller, Disc. Math., 87, 105-108.
[7] Narayana, T.V. (1967). Cyclic permutation of lattice paths and the Chung-Feller theorem, Skand. Aktuarietidsk, 23-30.