A \(D\)-finiteness result for products of permutations
type: Item
instance of: scholarly article
title: A \(D\)-finiteness result for products of permutations
zbMATH Open document ID: 0776.05098
DOI: 10.1016/0012-365X(92)90362-J
author: E. Rodney Canfield
author: David M. Jackson
published in: Discrete Mathematics
publication date: 1992-09-27T00:00:00Z
review text: Let \(e_ k^{\mathbf p}({\mathbf n})\), \({\mathbf p}=(p_ 1,\dots,p_ d)\) and \({\mathbf n}=(n_ 1,\dots,n_ d)\), denote the number of permutations of \(N=n_ 1p_ 1+\cdots+n_ dp_ d\) that can be represented as the product of an arbitrary but fixed full cycle and a permutation with \(n_ i\) cycles of length \(p_ i\), \(1\leq i\leq d\). In ``Counting cycles in permutations by group characters, with an application to a topological problem'' [Trans. Am. Math. Soc. 299, 785-801 (1987; Zbl 0655.05005)], the second author found a closed expression for the generating function for \(e_ k^{\mathbf p}({\mathbf n})\). In this paper, the generating function \(\sum_{k,{\mathbf n}}e_ k^{\mathbf p}({\mathbf n}) z^ kx^ N{\mathbf w}^{\mathbf n}\) is proven to be \(D\)-finite in the variables \(x\) and \({\mathbf w}\) over the field \({\mathbf Q}(z)\). This means that the vector space spanned by all partial derivatives of this series is finite dimensional over \({\mathbf Q}(z)\), and thus the counting function satisfies a linear recurrence with a fixed number of terms. The authors also find an explicit formula for \(e_ k^{\mathbf p}({\mathbf n})\) in terms of the characters associated with the irreducible representations indexed by the conjugacy classes associated with hooks (partitions of the form \(1^ r\), \(N-r)\) evaluated on the conjugacy class indexed by \(p_ 1^{n_ 1},\dots,p_ d^{n_ d}\).
Mathematics Subject Classification ID: 05E10
Mathematics Subject Classification ID: 20C15
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 05A10
zbMATH DE Number: 63150
zbMATH Keywords: number of permutations
zbMATH Keywords: generating function
zbMATH Keywords: characters
zbMATH Keywords: irreducible representations
zbMATH Keywords: conjugacy classes
zbMATH Keywords: hooks
reviewed by: David M. Bressoud
MaRDI profile type: Publication
cites work: Genus distributions for bouquets of circles
cites work: The Euler characteristic of the moduli space of curves
cites work: Counting Cycles in Permutations by Group Characters, With an Application to a Topological Problem
cites work: The diagonal of a D-finite power series is D-finite
full work available at URL: 0012-365x(92)90362-j
OpenAlex ID: W2013331348
Recommended article: Some combinatorial problems associated with products of conjugacy classes of the symmetric group
Recommended article: Generating functions for permutation representations.
Recommended article: \(Q\)-analogues of the number of permutations with \(k\)-excedances
Recommended article: Q3094550
Recommended article: Solutions of questions 12087, 12107.
Recommended article: Representations of symmetric groups with non-trivial determinant
Recommended article: Counting Semiregular Permutations which are Products of a Full Cycle and and an Involution
Recommended article: On permutation weights and \(q\)-Eulerian polynomials
Recommended article: An algebraically derived q-analogue of a character sum associated with a class of semiregular permutations
Recommended article: Two involutions for signed excedance numbers
description: scientific article; zbMATH DE number 63150