Enumerative Combinatorics



Super-Catalan problems: Andrew N. Fan, Toufik Mansour and Sabrina X. M. Pang, 4 November 2005. As we know several people tried to get many structures for fine numbers (see Sequence A000957 in The On-Line Encyclopedia of Integer Sequences, while others on Catalan numbers (see Sequence A000108 in The On-Line Encyclopedia of Integer Sequences. Stanley gave more than 149 (Up to 29 July 2007) Catalan structures while Deutsch and Shapiro (see Discrete Mathematics 241, 2001, 241-265) also discovered many settings for the Fine numbers. The structures for Fine numbers and Catalan numbers are intimately related from the list of Fine number occurrences in Discrete Mathematics 241, 2001, 241-265, which motivated us to find out more and more super-Catalan structures by the tight link between Catalan numbers and super-Catalan numbers, whose first several terms are 1,1,3,11,45,197,… (see Sequence A001003 in The On-Line Encyclopedia of Integer Sequences. The purpose of this paper is to give a unified presentation of many new super-Catalan structures. We start the project with the idea of giving a restricted bi-color to the existed Catalan structures, and have included a selection of results in a short paper (will appear).

K-Catalan structures: Silvia Heubach, Nelson Y. Li, Toufik Mansour, 29 July 2007. One of the frequently occurring sequences in combinatorics are the Catalan numbers, defined as $C_n=\frac{1}{n+1}{2n \choose n}$, which count numerous combinatorial structures. For a list of these, see Stanley's Homepage. Probably the most important generalization of the Catalan numbers are the k-ary numbers, defined by $C_n^k=\frac{1}{kn+1}{kn+1 \choose n}=\frac{1}{(k-1)n+1}{kn \choose n}$ for any positive integers k,n. Clearly, C_n^2=C_n. The main purpose of this draft is to serve as a repository for k-Catalan structures. It is a dynamical list and will be continually up-dated. We invite the combinatorics community to submit additional structures by sending email to Toufik Mansour.

Wilf classes and involutions: Mark Dukes, Vit Jelínek, Toufik Mansour and Astrid Reifegerste, 10 August 2007. The complete list of the Wilf classes of S6 can be found in Patterns of Length Six , and the complete list of the Wilf classes of S7 can be found in Patterns of Length Seven.

Wilf classes and partitions: Vit Jelínek and Toufik Mansour, 6 Sept 2007. The complete list of the Wilf classes of P5 (partitions of [5]) can be found in Patterns of Length Five, the complete list of the Wilf classes of P6 can be found in Patterns of Length Six, and the complete list of the Wilf classes of P7 can be found in Patterns of Length Seven.

Wilf classes on k-ary words, compositions, and parking functions: Vit Jelínek and Toufik Mansour, 10 April 2008. The complete list of the Wilf classes of words patterns of length 4,5,6 in the set of k-ary words can be found in Word Patterns, the complete list of the Wilf classes of words patterns of length 4,5 in the set of compositions can be found in Composition Patterns, and the complete list of the Wilf classes words pattern of length 3,4,5 in the set of parking functions can be found in Parking function patterns.

Wilf classes of partial matching patterns and perfect matchings: Vit Jelínek and Toufik Mansour, 10 March 2010. The list of the Wilf classes of words patterns of length 6 and 7 in the set of prefect matchings can be found in Partial Matching Patterns.

Wilf classes of noncrossing set partitions: Vit Jelínek, Toufik Mansour and Mark Shattuck, 24 August 2011. The list of the Wilf classes of set partition patterns of length 4, 5 and 6 in the set of noncrossing set partitions can be found in set partition patterns.

Passing through a stack k times with reversals: Toufik Mansour, Howard Skogman and Rebecca Smith, 06 March 2019. Click to find the generating function M2U(x).

Equivalence of the descents statistic on some (4,4)-avoiding classes of permutaions: Toufik Mansour and Mark Shattuck, 20 December 2021. Click here to find the Maple files on each section of the paper: Section 2, Section 3, Section 4, Section 5.1, Section 5.2, Section 5.3, Section 5.4.

On a question of Li concerning an uncounted class of circular permutations: Toufik Mansour and Mark Shattuck, 03 April 2022. Click Maple to find the number of the circular permutations of [n] that avoid the vincular pattern 2341.

Inversion sequences avoiding 021 and another pattern of length four: Toufik Mansour and Gokhan Yildirim, 19 November 2022. Here, we find an explicit formula for the generating function for the number of inversion sequences that avoid 021 and another pattern of length or length 5.
--Pattern of length four: (1) We produced the data file of all Generating trees of T'(021,pattern of length 4) up to level d (mostly d=7-8). (2) We translated each set of rules (after we guessed the general set of rules) for each class, and we solved the corresponding system of equations to find the explicit formula for the generating function F_{021,pattern of length 4}(x). See the following files pattern 0000, and pattern p4 ≠0000.
--Pattern of length five: (1) We produced the data file of all Generating trees of T'(021,pattern of length 5) up to level d (mostly d=7-8). (2) We translated each set of rules (after we guessed the general set of rules) for each class, and we solved the corresponding system of equations to find the explicit formula for the generating function F_{021,pattern of length 5}(x). See the following files pattern 00000, pattern 00001, and pattern p5 ≠00000,00001. (3) We summarized all our results for the case of pattern of length 5 in tables, one for the generating trees and another for generating functions in the following file Counting InvSeq(021,pattern of length 5).

Inversion sequences avoiding a set of length-3 patterns: Toufik Mansour, 2 October 2023. Let w_d be the number of distinct I-Wilf-equivalence classes of sets of d length-3 patterns.. We show that w_5=219, w_6=167, w_7=105, w_8=61, w_9=35, w_10=21, w_11=10, w_12=4, and w_13=1. See File.