Discrete Mathematics & Theoretical Computer Science, Vol 13, No 3 (2011)

Font Size:  Small  Medium  Large

The largest singletons in weighted set partitions and its applications

Yidong Sun, Yanjie Xu

Abstract


Recently, Deutsch and Elizalde studied the largest fixed points of permutations. Motivated by their work, we consider the analogous problems in weighted set partitions. Let An,k(t) denote the total weight of partitions on [n+1]={1,2, ..., n+1} with the largest singleton {k+1}. In this paper, explicit formulas for An,k(t) and many combinatorial identities involving An,k(t) are obtained by umbral operators and combinatorial methods. In particular, the permutation case leads to an identity related to tree enumerations, namely, eqnarray* ∑k=0n(n choose k)Dk+1(n+1)n-k = nn+1, where Dk is the number of permutations of [k] with no fixed points.

Full Text: PDF PostScript