Combinatorics of non-ambiguous trees. (English) Zbl 1300.05127
Summary: This article investigates combinatorial properties of non-ambiguous trees. These objects we define may be seen either as binary trees drawn on a grid with some constraints, or as a subset of the tree-like tableaux previously defined by J.-C. Aval et al. [Electron. J. Comb. 20, No. 4, Research Paper P34, 24 p. (2013; Zbl 1295.05004)]. The enumeration of non-ambiguous trees satisfying some additional constraints allows us to give elegant combinatorial proofs of identities due to L. Carlitz [Proc. Am. Math. Soc. 14, 1–9 (1963; Zbl 0113.03403)], and to R. Ehrenborg and E. Steingrímsson [Adv. Appl. Math. 24, No. 3, 284–299 (2000; Zbl 0957.05006)]. We also provide a hook formula to count the number of non-ambiguous trees with a given underlying tree. Finally, we use non-ambiguous trees to describe a very natural bijection between parallelogram polyominoes and binary trees.
MSC:
| 05C30 | Enumeration in graph theory |
| 05C05 | Trees |
| 06A07 | Combinatorics of partially ordered sets |
| 05B50 | Polyominoes |
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
Keywords:
posets; parallelogram polyominoes; tree-like tableaux; Bessel function; permutations excedancesOnline Encyclopedia of Integer Sequences:
Number of permutations of {1,2,...,n} having excedance set {1,2,...,k} for some k=0...n-1 (for k=0 we have the empty set). The excedance set of a permutation p in S_n is the set of indices i such that p(i)>i.References:
| [1] | Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Natl. Bur. Stand. Appl. Math. Ser., vol. 55 (1964), U.S. Government Printing Office: U.S. Government Printing Office Washington, D.C. · Zbl 0171.38503 |
| [2] | Aval, J.-C.; Boussicault, A.; Nadeau, P., Tree-like tableaux, (DMTCS Proceedings 23rd International Conference on Formal Power Series and Algebraic Combinatorics. DMTCS Proceedings 23rd International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2011, Islande. DMTCS Proceedings 23rd International Conference on Formal Power Series and Algebraic Combinatorics. DMTCS Proceedings 23rd International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2011, Islande, Discrete Math. Theor. Comput. Sci. (2011)), 63-74 · Zbl 1355.05044 |
| [3] | Aval, J.-C.; Boussicault, A.; Nadeau, P., Tree-like tableaux, Electron. J. Combin., 20, 4, P34 (2013) · Zbl 1295.05004 |
| [4] | Bousquet-Mélou, M.; Viennot, X. G., Empilements de segments et q-énumération de polyominos convexes dirigés, J. Combin. Theory Ser. A, 60, 2, 196-224 (1992) · Zbl 0753.05023 |
| [5] | Burstein, A., On some properties of permutation tableaux, Ann. Comb., 11, 3-4, 355-368 (2007) · Zbl 1141.05002 |
| [6] | Carlitz, L., A sequence of integers related to the Bessel functions, Proc. Amer. Math. Soc., 14, 1-9 (1963) · Zbl 0113.03403 |
| [7] | Carlitz, L.; Scoville, R.; Vaughan, T., Enumeration of pairs of permutations and sequences, Bull. Amer. Math. Soc., 80, 881-884 (1974) · Zbl 0291.05007 |
| [8] | Delest, M.; Dubernard, J.-P.; Dutour, I., Parallelogram polyominoes and corners, Symbolic Computation in Combinatorics \(\Delta_1\). Symbolic Computation in Combinatorics \(\Delta_1\), Ithaca, NY, 1993. Symbolic Computation in Combinatorics \(\Delta_1\). Symbolic Computation in Combinatorics \(\Delta_1\), Ithaca, NY, 1993, J. Symbolic Comput., 20, 5-6, 503-515 (1995) · Zbl 0848.68053 |
| [9] | Delest, M.-P.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci., 34, 1-2, 169-206 (1984) · Zbl 0985.68516 |
| [10] | Ehrenborg, R.; Steingrímsson, E., The excedance set of a permutation, Adv. in Appl. Math., 24, 3, 284-299 (2000) · Zbl 0957.05006 |
| [11] | Knuth, D. E., The Art of Computer Programming, vol. 3: Sorting and Searching (1998), Addison-Wesley Longman Publishing Co., Inc.: Addison-Wesley Longman Publishing Co., Inc. Redwood City, CA, USA · Zbl 0895.65001 |
| [12] | Loday, J.-L.; Ronco, M., Hopf algebra of the planar binary trees, Adv. Math., 139, 2, 293-309 (1998) · Zbl 0926.16032 |
| [13] | Nadeau, P., The structure of alternative tableaux, J. Combin. Theory Ser. A, 118, 5, 1638-1660 (2011) · Zbl 1235.05014 |
| [14] | Petkovšek, M.; Wilf, H. S.; Zeilberger, D., \(A = B (1996)\), A K Peters · Zbl 0848.05002 |
| [15] | The Sage-Combinat community, Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics (2012) |
| [16] | Sloane, N. J.A., The On-Line Encyclopedia of Integer Sequences · Zbl 1044.11108 |
| [17] | Stein, W. A., Sage Mathematics Software (2012), The Sage Development Team |
| [18] | Steingrímsson, E.; Williams, L. K., Permutation tableaux and permutation patterns, J. Combin. Theory Ser. A, 114, 2, 211-234 (2007) · Zbl 1116.05003 |
| [19] | Viennot, X., Alternative tableaux, permutations and partially asymmetric exclusion process (April 2007), talk at Isaac Newton Institute for Mathematical Sciences |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
