A polynomial generalization of some associated sequences related to set partitions
- PDF / 484,133 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 180 Views
A polynomial generalization of some associated sequences related to set partitions Toufik Mansour1 · Mark Shattuck2
© Akadémiai Kiadó, Budapest, Hungary 2017
Abstract In this paper, we consider a common polynomial generalization, denoted by a,b,c,d wm (n, k) = wm (n, k), of several types of associated sequences. When a = 0 and b = 1, one gets a generalized associated Lah sequence, while if c = 0, d = 1, one gets a polynomial array that enumerates a restricted class of weighted ordered partitions of size n having k blocks. The particular cases when a = d = 0 and b = c = 1 or when a = c = 0 and b = d = 1 correspond to the associated Stirling numbers of the first and second kind, respectively. We derive several combinatorial properties satisfied by wm (n, k) and consider further the case a = 0, b = 1. Our results not only generalize prior formulas found for the associated Stirling and Lah numbers but also yield some apparently new identities for these sequences. Finally, explicit exponential generating function formulas for wm (n, k) are derived in the cases when a = 0 or b = 0. Keywords Associated Stirling numbers · Polynomial generalization · Associated Lah numbers · Combinatorial identities Mathematics Subject Classification Primary 11B73; Secondary 05A19 · 05A18
1 Introduction In combinatorics, sequences enumerating a class of discrete structures are often described as associated when a certain substucture is required to have cardinality greater than a fixed
B
Mark Shattuck [email protected] Toufik Mansour [email protected]
1
Department of Mathematics, University of Haifa, 3498838 Haifa, Israel
2
Institute for Computational Science & Faculty of Mathematics and Statistics, Ton Duc Thang University, Ho Chi Minh City, Vietnam
123
T. Mansour, M. Shattuck
number. For example, associated Stirling numbers of the first and second kind (see, e.g., [4,6,8,11,16,18]) count permutations or set partitions, respectively, in which the cycle lengths or block sizes must exceed a fixed number. Let nk ≥m be the number of permutations of [n] = {1, 2, . . . , n} having k cycles each of length at least m and let nk ≥m be the number of partitions of [n] having k blocks with the analogous restriction. When m = 1, the sequences nk ≥m n and k ≥m reduce to the classical Stirling numbers of the first and second kind, respectively. When m = 2, they enumerate the class of permutations having no fixed points or the subset of partitions of [n] having no singleton blocks and are known as the derangement and Ward [3] n numbers, n respectively (see entries A008306 and A134991 in OEIS [17]). The sequences of the k ≥m and k ≥m have arisen again recently in conjunction with incomplete versions n poly-Cauchy [9] and poly-Bernoulli [10] numbers. The associated Lah numbers k ≥m [2] count sets of k disjoint lists each of length at least m whose union is[n] and reduce to the classical Lah numbers [12] when m = 1. When m = 2, the sequence nk ≥m corresponds to entry A076126 in [17]. a,b,c,d Here, we consi
Data Loading...
