×

A discontinuity in the distribution of fixed point sums. (English) Zbl 1011.05009

Electron. J. Comb. 10, Research paper R15, 18 p. (2003); printed version J. Comb. 10, No. 2 (2003).
Summary: The quantity \(f(n,r)\), defined as the number of permutations of the set \([n]=\{1,2,\dots,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.

MSC:

05A17 Combinatorial aspects of partitions of integers
05A20 Combinatorial inequalities
05A16 Asymptotic enumeration
11P81 Elementary theory of partitions

Keywords:

permutation
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS