Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: A Colorful Involution for the Generating Function for Signed Stirling Numbers of the First Kind. | A Colorful Involution for the Generating Function for Signed Stirling Numbers of the First Kind Paul Levande Department of Mathematics David Rittenhouse Lab. 209 South 33rd Street Philadelphia PA 19103-6395 plevande@ Submitted Nov 3 2009 Accepted Dec 13 2009 Published Jan 5 2010 Mathematics Subject Classification 05A05 05A15 05A19 Abstract We show how the generating function for signed Stirling numbers of the first kind can be proved using the involution principle and a natural combinatorial interpretation based on cycle-colored permuations. We seek an involution-based proof of the generating function for signed Stirling numbers of the first kind written here as E 1 kc n k xk 1 n x x 1 x n 1 k where c n k is the number of permutations of n with k cycles. The standard proof uses 2 an algebraic manipulation of the generating function for unsigned Stirling numbers of the first kind. Fix an unordered x-set A for example a set of x letters or colors . For n G Sn let Kn be the set of disjoint cycles of n including any cycles of length one . Let Sn A n f n G Sn f Kn A be the set of cycle-colored permutations of n where f is interpreted as a coloring of the cycles of n using the colors of A. We follow 1 in using colored permutations . Further let Kn i be the unique cycle of n containing i for any 1 i n and K n Kn be the number of cycles of n. Note that E 1 K n E 1 K n x n 1 kc n k xk n f Sn A nèSn k This research was supported by the University of Pennsylvania Graduate Program in Mathematics THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N2 1 For n f G Sn A let R n f i j 1 i j n f Kn i f Kn j be the set of pairs of distinct elements of n in cycles-not necessarily distinct-colored the same way by f . Define a map Ộ on Sn A as follows for n f G Sn A If R n f 0 let ộ n f n f Otherwise let i j G R n f be minimal under the lexicographic ordering of R n f Let n i j n the product of the transposition i j and n in Sn. Note that if Kn i Kn j left-multiplication by i