On the number of permutations on \(n\) objects with greatest cycle length \(k\)
type: Item
instance of: scholarly article
title: On the number of permutations on \(n\) objects with greatest cycle length \(k\)
zbMATH Open document ID: 0897.05005
author: S. W. Golomb
author: Peter Gaal
published in: Advances in Applied Mathematics
publication date: 1998-04-20T00:00:00Z
review text: This paper is concerned with the problem of evaluating \(L_{k,n}\), the number of permutations on \(n\) objects with greatest cycle length \(k\). It is shown that, for \(1<k\leq n\), \[ L_{k,n} =\sum_{j\geq 1} {1\over j!k^j} {n!\over (n-kj)!} \sum_t L_{t,n-kj} \] where, in the inner sum, \(t\leq\min (k-1,n-kj)\). Closed formulae are obtained, e.g. for \({n\over 3} <k<{n \over 2}\). Also discussed are the expected length \(E_n\) of the longest cycle, and the relative expected length \(\lambda_n= {E_n\over n}\) of the largest cycle, which tends to Golomb's constant \(\lambda= 0.62432965 \dots\) as \(n\to\infty\).
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 1143892
zbMATH Keywords: enumeration
zbMATH Keywords: number of permutations
zbMATH Keywords: cycle
MaRDI profile type: Publication
full work available at URL: aama.1997.0567
OpenAlex ID: W1514828253
cites work: Q5684568
cites work: Q5585021
DOI: 10.1006/AAMA.1997.0567
description: scientific article; zbMATH DE number 1143892