Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05A15 ( Exact enumeration problems, generating functions [See also 33Cxx, 33Dxx] )

  Expand all        Collapse all Results 1 - 14 of 14

1. CJM Online first

Bacher, Roland; Reutenauer, Christophe
Number of right ideals and a $q$-analogue of indecomposable permutations
We prove that the number of right ideals of codimension $n$ in the algebra of noncommutative Laurent polynomials in two variables over the finite field $\mathbb F_q$ is equal to $(q-1)^{n+1} q^{\frac{(n+1)(n-2)}{2}}\sum_\theta q^{inv(\theta)}$, where the sum is over all indecomposable permutations in $S_{n+1}$ and where $inv(\theta)$ stands for the number of inversions of $\theta$.

Keywords:permutation, indecomposable permutation, subgroups of free groups
Categories:05A15, 05A19

2. CJM 2013 (vol 65 pp. 1287)

Reihani, Kamran
$K$-theory of Furstenberg Transformation Group $C^*$-algebras
The paper studies the $K$-theoretic invariants of the crossed product $C^{*}$-algebras associated with an important family of homeomorphisms of the tori $\mathbb{T}^{n}$ called Furstenberg transformations. Using the Pimsner-Voiculescu theorem, we prove that given $n$, the $K$-groups of those crossed products, whose corresponding $n\times n$ integer matrices are unipotent of maximal degree, always have the same rank $a_{n}$. We show using the theory developed here that a claim made in the literature about the torsion subgroups of these $K$-groups is false. Using the representation theory of the simple Lie algebra $\frak{sl}(2,\mathbb{C})$, we show that, remarkably, $a_{n}$ has a combinatorial significance. For example, every $a_{2n+1}$ is just the number of ways that $0$ can be represented as a sum of integers between $-n$ and $n$ (with no repetitions). By adapting an argument of van Lint (in which he answered a question of Erdős), a simple, explicit formula for the asymptotic behavior of the sequence $\{a_{n}\}$ is given. Finally, we describe the order structure of the $K_{0}$-groups of an important class of Furstenberg crossed products, obtaining their complete Elliott invariant using classification results of H. Lin and N. C. Phillips.

Keywords:$K$-theory, transformation group $C^*$-algebra, Furstenberg transformation, Anzai transformation, minimal homeomorphism, positive cone, minimal homeomorphism
Categories:19K14, 19K99, 46L35, 46L80, , 05A15, 05A16, 05A17, 15A36, 17B10, 17B20, 37B05, 54H20

3. CJM 2012 (vol 65 pp. 1020)

Goulden, I. P.; Guay-Paquet, Mathieu; Novak, Jonathan
Monotone Hurwitz Numbers in Genus Zero
Hurwitz numbers count branched covers of the Riemann sphere with specified ramification data, or equivalently, transitive permutation factorizations in the symmetric group with specified cycle types. Monotone Hurwitz numbers count a restricted subset of these branched covers related to the expansion of complete symmetric functions in the Jucys-Murphy elements, and have arisen in recent work on the the asymptotic expansion of the Harish-Chandra-Itzykson-Zuber integral. In this paper we begin a detailed study of monotone Hurwitz numbers. We prove two results that are reminiscent of those for classical Hurwitz numbers. The first is the monotone join-cut equation, a partial differential equation with initial conditions that characterizes the generating function for monotone Hurwitz numbers in arbitrary genus. The second is our main result, in which we give an explicit formula for monotone Hurwitz numbers in genus zero.

Keywords:Hurwitz numbers, matrix models, enumerative geometry
Categories:05A15, 14E20, 15B52

4. CJM 2012 (vol 65 pp. 241)

Aguiar, Marcelo; Lauve, Aaron
Lagrange's Theorem for Hopf Monoids in Species
Following Radford's proof of Lagrange's theorem for pointed Hopf algebras, we prove Lagrange's theorem for Hopf monoids in the category of connected species. As a corollary, we obtain necessary conditions for a given subspecies $\mathbf k$ of a Hopf monoid $\mathbf h$ to be a Hopf submonoid: the quotient of any one of the generating series of $\mathbf h$ by the corresponding generating series of $\mathbf k$ must have nonnegative coefficients. Other corollaries include a necessary condition for a sequence of nonnegative integers to be the dimension sequence of a Hopf monoid in the form of certain polynomial inequalities, and of a set-theoretic Hopf monoid in the form of certain linear inequalities. The latter express that the binomial transform of the sequence must be nonnegative.

Keywords:Hopf monoids, species, graded Hopf algebras, Lagrange's theorem, generating series, Poincaré-Birkhoff-Witt theorem, Hopf kernel, Lie kernel, primitive element, partition, composition, linear order, cyclic order, derangement
Categories:05A15, 05A20, 05E99, 16T05, 16T30, 18D10, 18D35

5. CJM 2009 (vol 61 pp. 1092)

Irving, John
Minimal Transitive Factorizations of Permutations into Cycles
We introduce a new approach to an enumerative problem closely linked with the geometry of branched coverings, that is, we study the number $H_{\alpha}(i_2,i_3,\dots)$ of ways a given permutation (with cycles described by the partition $\a$) can be decomposed into a product of exactly $i_2$ 2-cycles, $i_3$ 3-cycles, \emph{etc.}, with certain minimality and transitivity conditions imposed on the factors. The method is to encode such factorizations as planar maps with certain \emph{descent structure} and apply a new combinatorial decomposition to make their enumeration more manageable. We apply our technique to determine $H_{\alpha}(i_2,i_3,\dots)$ when $\a$ has one or two parts, extending earlier work of Goulden and Jackson. We also show how these methods are readily modified to count \emph{inequivalent} factorizations, where equivalence is defined by permitting commutations of adjacent disjoint factors. Our technique permits us to generalize recent work of Goulden, Jackson, and Latour, while allowing for a considerable simplification of their analysis.

Categories:05A15, 05E10

6. CJM 2008 (vol 60 pp. 958)

Chen, Yichao
A Note on a Conjecture of S. Stahl
S. Stahl (Canad. J. Math. \textbf{49}(1997), no. 3, 617--640) conjectured that the zeros of genus polynomial are real. L. Liu and Y. Wang disproved this conjecture on the basis of Example 6.7. In this note, it is pointed out that there is an error in this example and a new generating matrix and initial vector are provided.

Keywords:genus polynomial, zeros, real
Categories:05C10, 05A15, 30C15, 26C10

7. CJM 2008 (vol 60 pp. 960)

Stahl, Saul
Erratum: On the Zeros of Some Genus Polynomials
No abstract.

Categories:05C10, 05A15, 30C15, 26C10

8. CJM 2008 (vol 60 pp. 297)

Bini, G.; Goulden, I. P.; Jackson, D. M.
Transitive Factorizations in the Hyperoctahedral Group
The classical Hurwitz enumeration problem has a presentation in terms of transitive factorizations in the symmetric group. This presentation suggests a generalization from type~$A$ to other finite reflection groups and, in particular, to type~$B$. We study this generalization both from a combinatorial and a geometric point of view, with the prospect of providing a means of understanding more of the structure of the moduli spaces of maps with an $\gS_2$-symmetry. The type~$A$ case has been well studied and connects Hurwitz numbers to the moduli space of curves. We conjecture an analogous setting for the type~$B$ case that is studied here.

Categories:05A15, 14H10, 58D29

9. CJM 2001 (vol 53 pp. 758)

Goulden, I. P.; Jackson, D. M.; Latour, F. G.
Inequivalent Transitive Factorizations into Transpositions
The question of counting minimal factorizations of permutations into transpositions that act transitively on a set has been studied extensively in the geometrical setting of ramified coverings of the sphere and in the algebraic setting of symmetric functions. It is natural, however, from a combinatorial point of view to ask how such results are affected by counting up to equivalence of factorizations, where two factorizations are equivalent if they differ only by the interchange of adjacent factors that commute. We obtain an explicit and elegant result for the number of such factorizations of permutations with precisely two factors. The approach used is a combinatorial one that rests on two constructions. We believe that this approach, and the combinatorial primitives that have been developed for the ``cut and join'' analysis, will also assist with the general case.

Keywords:transitive, transposition, factorization, commutation, cut-and-join
Categories:05C38, 15A15, 05A15, 15A18

10. CJM 1997 (vol 49 pp. 865)

Goulden, I. P.; Jackson, D. M.
Maps in locally orientable surfaces and integrals over real symmetric surfaces
The genus series for maps is the generating series for the number of rooted maps with a given number of vertices and faces of each degree, and a given number of edges. It captures topological information about surfaces, and appears in questions arising in statistical mechanics, topology, group rings, and certain aspects of free probability theory. An expression has been given previously for the genus series for maps in locally orientable surfaces in terms of zonal polynomials. The purpose of this paper is to derive an integral representation for the genus series. We then show how this can be used in conjunction with integration techniques to determine the genus series for monopoles in locally orientable surfaces. This complements the analogous result for monopoles in orientable surfaces previously obtained by Harer and Zagier. A conjecture, subsequently proved by Okounkov, is given for the evaluation of an expectation operator acting on the Jack symmetric function. It specialises to known results for Schur functions and zonal polynomials.

Categories:05C30, 05A15, 05E05, 15A52

11. CJM 1997 (vol 49 pp. 641)

Burris, Stanley; Compton, Kevin; Odlyzko, Andrew; Richmond, Bruce
Fine spectra and limit laws II First-order 0--1 laws.
Using Feferman-Vaught techniques a condition on the fine spectrum of an admissible class of structures is found which leads to a first-order 0--1 law. The condition presented is best possible in the sense that if it is violated then one can find an admissible class with the same fine spectrum which does not have a first-order 0--1 law. If the condition is satisfied (and hence we have a first-order %% 0--1 law)

Categories:03N45, 11N45, 11N80, 05A15, 05A16, 11M41, 11P81

12. CJM 1997 (vol 49 pp. 617)

Stahl, Saul
On the zeros of some genus polynomials
In the genus polynomial of the graph $G$, the coefficient of $x^k$ is the number of distinct embeddings of the graph $G$ on the oriented surface of genus $k$. It is shown that for several infinite families of graphs all the zeros of the genus polynomial are real and negative. This implies that their coefficients, which constitute the genus distribution of the graph, are log concave and therefore also unimodal. The geometric distribution of the zeros of some of these polynomials is also investigated and some new genus polynomials are presented.

Categories:05C10, 05A15, 30C15, 26C10

13. CJM 1997 (vol 49 pp. 468)

Burris, Stanley; Sárközy, András
Fine spectra and limit laws I. First-order laws
Using Feferman-Vaught techniques we show a certain property of the fine spectrum of an admissible class of structures leads to a first-order law. The condition presented is best possible in the sense that if it is violated then one can find an admissible class with the same fine spectrum which does not have a first-order law. We present three conditions for verifying that the above property actually holds. The first condition is that the count function of an admissible class has regular variation with a certain uniformity of convergence. This applies to a wide range of admissible classes, including those satisfying Knopfmacher's Axiom A, and those satisfying Bateman and Diamond's condition. The second condition is similar to the first condition, but designed to handle the discrete case, {\it i.e.}, when the sizes of the structures in an admissible class $K$ are all powers of a single integer. It applies when either the class of indecomposables or the whole class satisfies Knopfmacher's Axiom A$^\#$. The third condition is also for the discrete case, when there is a uniform bound on the number of $K$-indecomposables of any given size.

Keywords:First order limit laws, generalized number theory
Categories:O3C13, 11N45, 11N80, 05A15, 05A16, 11M41, 11P81

14. CJM 1997 (vol 49 pp. 301)

Merlini, Donatella; Rogers, Douglas G.; Sprugnoli, Renzo; Verri, M. Cecilia
On some alternative characterizations of Riordan arrays
We give several new characterizations of Riordan Arrays, the most important of which is: if $\{d_{n,k}\}_{n,k \in {\bf N}}$ is a lower triangular array whose generic element $d_{n,k}$ linearly depends on the elements in a well-defined though large area of the array, then $\{d_{n,k}\}_{n,k \in {\bf N}}$ is Riordan. We also provide some applications of these characterizations to the lattice path theory.

Categories:05A15, 05C38

© Canadian Mathematical Society, 2016 :