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 Discontinuity in the Distribution of Fixed Point Sums | A Discontinuity in the Distribution of Fixed Point Sums Edward A. Bender Department of Mathematics University of California San Diego La Jolla CA 92091 ebender@ E. Rodney Canfield Department of Computer Science University of Georgia Athens GA 30602 erc@ L. Bruce Richmond Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario CANADA N2L 3G1 lbrichmond@ Herbert S. Wilf Department of Mathematics University of Pennsylvania Philadelphia PA 19104-6395 wilf@ AMS Subject Classification 05A17 05A20 05A16 11P81 Submitted Oct 19 2002 Accepted Mar 29 2003 Published Apr 23 2003 THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R15 1 Abstract The quantity f n r defined as the number of permutations of the set n 1 2 . .n whose fixed points sum to r shows a sharp discontinuity in the neighborhood of r n. We explain this discontinuity and study the possible existence of other discontinuities in f n r for permutations. We generalize our results to other families of structures that exhibit the same kind of discontinuities by studying f n r when fixed points is replaced by components of size 1 in a suitable graph of the structure. Among the objects considered are permutations all functions and set partitions. 1 Introduction Let f n r denote the number of permutations of n 1 2 . n the sum of whose fixed points is r. For example when n 3 we find the values r 0 12 3 6 f 3 r 2 1111 Here is the graph of f 15 r The plot shows an interesting steep drop from r n to r n 1 and this paper arose in providing a quantification of the observed plunge. We think that this problem is a nice example of an innocent-looking asymptotic enumerative situation in which thoughts of THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R15 2 discontinuities might be far from the mind of an investigator yet they materialize in an interesting and important way. A quick explanation for the discontinuity is as follows about 74 of permutations have .
