scientific article; zbMATH DE number 3981410

From MaRDI portal
Publication:3746003





Denote by \(\tau_ n\) the full cycle (1,2,...,n) in the symmetric group \(S_ n\), and let \(\sigma_ 1,\sigma_ 2,...,\sigma_ k\) be a set of k pairwise disjoint transpositions in \(S_ n\). Label n points 1,2,...,n in cyclic order on a circle. For \(i=1,2,...,k\) denote by \(C_ i\) the chord connecting the points a and b if \(\sigma_ i=(a,b)\). Define \(k^ 2\) numbers \(a_{ij}\) as follows: \(a_{ii}=0\), \(i=1,2,...,k\), \(a_{ij}=0\) if \(C_ i\cap C_ j=\emptyset\) and \(a_{ij}=1\) if \(C_ i\cap C_ j\neq \emptyset\), and let A be the \(k\times k\) matrix \(A=(a_{ij})\). It has been shown by \textit{M. Cohn} and \textit{A. Lempel} [J. Comb. Theory, Ser. A 13, 83-89 (1972; Zbl 0314.05005)] that if \(\theta =\sigma_ 1\cdot \sigma_ 2\cdot \cdot \cdot \sigma_ k\cdot \tau_ n\) then the number of \(\theta\) orbits is equal to \(1+nullity\)(A). With a modification in the definition of A, the first author [ibid. 23, 198-207 (1977; Zbl 0406.05003)] has proved the same result in case the \(\sigma_ i\) are not disjoint. The purpose of the present paper is to present an algorithm whereby one associates a sequence of disjoint transpositions \(\sigma_ 1',\sigma_ 2',...,\sigma_ k'\) and a cycle \(\tau\) of length 2k with a non-disjoint sequence \(\sigma_ 1,\sigma_ 2,...,\sigma_ k\) so that the number of orbits of \(\theta =\sigma_ 1\cdot \sigma_ 2\cdot \cdot \cdot \sigma_ k\cdot \tau\) equals the number of orbits of \(\theta '=\sigma_ 1'\cdot \sigma_ 2'\cdot \cdot \cdot \sigma_ k'\cdot \tau\), and the matrices A and A' associated with \(\sigma_ 1,\sigma_ 2,...,\sigma_ k\), \(\tau_ n\) and \(\sigma_ 1',\sigma_ 2',...,\sigma_ k',\tau\), respectively, are identical.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3746003)