Combinatorial congruences from p-subgroups of the symmetric group

DOI10.1007/BF02988317MaRDI QIDQ687729zbMATH OpenOpenAlexFDO

Publication date 28 October 1993

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02988317

\(p\)-subgroups deriving congruences from group action spinning Stirling numbers symmetric group wheel system

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Congruences; primitive roots; residue systems (11A07) Bell and Stirling numbers (11B73) Other combinatorial number theory (11B75) Congruences in many variables (11D79) Subgroups of symmetric groups (20B35)

Review text

There has been considerable interest in the methods of deriving congruences from group actions; see \textit{G.-C. Rota} and \textit{B. Sagan} [Eur. J. Comb. 1, 67-76 (1980; Zbl 0453.05008)], or \textit{B. Sagan} [J. Number Theory 20, 210-237 (1985; Zbl 0577.10003)]. The author introduces a different approach to this question. Let \(p\) be a prime and \(H\) a finite set. A wheel system on \(H\) is a family \(\mathcal W\) of subsets of \(H\) (called wheels) with the following three properties: (1) the order of any wheel is a power of \(p\) (a wheel of order \(p^ i\) is called a \(p^ i\)-wheel), (2) distinct wheels of the same order are disjoint, and (3) each \(p^{i+1}\)-wheel is the union of \(p^ i\)-wheels. Wheels of order \(>1\) are called proper. A wheel system \(\mathcal W\) is called complete if \(\mathcal W\) is maximal with respect to the conditions (1), (2) and (3). When one assigns to each proper \(p^ i\)-wheel of a given wheel system \(\mathcal W\) a cyclic ordering of the \(p^{i-1}\)-wheels it contains, \(\mathcal W\) gets an orientation. A spinning is such a permutation of the elements of a given proper wheel that takes its subwheels and preserves its orientation. The subgroup generated by all spinnings of a complete wheel system is the symmetric group \({\mathcal S}_ H\). After proving numerous interesting technical lemmas the author gives some number theoretic applications of his approach. So, he proves (Lemma 3.5): Let \(a= b_ 1+ \cdots+ b_ k\) and suppose \((a,p)= (a,b_ 1,\dots,b_ k)=1\). Then \[ \begin{pmatrix} ap^ n\\ b_ 1 p^ n,\ldots,b_ k p^ n\end{pmatrix}\equiv 0\pmod a. \] Also, he proves the following result (Theorem 5.1): Let \(I(m)\) denote the number of idempotent maps \({\mathbf m}\to {\mathbf m}\). If \(p>2\), then \[ I(p^ n)\equiv 1+ p^{n-1} \left[(\mu-n) p(p-1)+sp+\sum^{p-1}_{k=1} {p\choose k} \sum^ s_{j=0} k^{p+ j-k}{s\choose j}\right]\pmod{p^{n+1}}, \] where \(s=(p-1)(n-1)\) and \(\mu\) denotes the number of proper wheels of a wheel system on \(p^ n\) elements. Concerning some divisibility properties of the Stirling numbers of second kind he proves (Theorem 5.2): Let \(P(m,k)\) denote the number of surjections \({\mathbf m}\to {\mathbf k}\). Then \[ P(p^ n,k)\equiv P(p^{n-1},k)+ p^{n-1} \bigl[P(p+(n-1)(p-1),k)-P(1+ (n-1)(p-1),k)\bigr]\pmod{p^{n+1}}. \]

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Combinatorial congruences from \(p\)-subgroups of the symmetric group

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