2,961 research outputs found
Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
No full textWe give three applications of a recently-proven "Decomposition Lemma," which
allows one to count preimages of certain sets of permutations under West's
stack-sorting map . We first enumerate the permutation class
, finding a new example
of an unbalanced Wilf equivalence. This result is equivalent to the enumeration
of permutations sortable by , where is the bubble
sort map. We then prove that the sets ,
,
and are
counted by the so-called "Boolean-Catalan numbers," settling a conjecture of
the current author and another conjecture of Hossain. This completes the
enumerations of all sets of the form
for
with the exception of the set
. We also find an explicit formula for
, where
is the set of permutations in with descents.
This allows us to prove a conjectured identity involving Catalan numbers and
order ideals in Young's lattice
Binary Codes and Period-2 Orbits of Sequential Dynamical Systems
No full textLet be the (global) SDS map of a sequential dynamical system
(SDS) defined over the complete graph using the update order
in which all vertex functions are equal to the same function . Let denote the maximum number of periodic
orbits of period that an SDS map of the form can have. We
show that is equal to the maximum number of codewords in a binary code
of length with minimum distance at least . This result is significant
because it represents the first interpretation of this fascinating
coding-theoretic sequence other than its original definition
Postorder Preimages
No full textGiven a set of decreasing plane trees and a permutation , how many
trees in have as their postorder? Using combinatorial and geometric
constructions, we provide a method for answering this question for certain sets
and all permutations . We then provide applications of our results to
the study of the deterministic stack-sorting algorithm
Proofs of Conjectures about Pattern-Avoiding Linear Extensions
No full textAfter fixing a canonical ordering (or labeling) of the elements of a finite
poset, one can associate each linear extension of the poset with a permutation.
Some recent papers consider specific families of posets and ask how many linear
extensions give rise to permutations that avoid certain patterns. We build off
of two of these papers. We first consider pattern avoidance in -ary heaps,
where we obtain a general result that proves a conjecture of Levin, Pudwell,
Riehl, and Sandberg in a special case. We then prove some conjectures that
Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding
linear extensions of rectangular posets
Colin Humphris
No full text"Colin Humphris 2 Sqdrn. RAAF. 1941 - 1942 Author of - 'Trapped on Timor' (as a result of bombing of Darwin Feb. 19, 1942)".Colin Humphris. 2 Squadron, Royal Australian Air Force 1941 - 1942. Author of - 'Trapped on Timor' (as a result of bombing of Darwin February 19, 1942)
Boolean, Free, and Classical Cumulants as Tree Enumerations
No full textDefant found that the relationship between a sequence of (univariate) classical cumulants and the corresponding sequence of (univariate) free cumulants can be described combinatorially in terms of families of binary plane trees called troupes. Using a generalization of troupes that we call weighted troupes, we generalize this result to allow for multivariate cumulants. Our result also gives a combinatorial description of the corresponding Boolean cumulants. This allows us to answer a question of Defant regarding his troupe transform. We also provide explicit distributions whose cumulants correspond to some specific weighted troupes.18 pages, 7 figure
Interview with Colin Wilson, part 4, undated
No full textInterview with Colin Wilson, part 4, features an interview with author Colin Wilson in which he discusses his views regarding society and art, his reclusive nature, and the intellectual and fantastical elements of his works, undated
Interview with Colin Wilson, part 2, undated
No full textInterview with Colin Wilson, part 2, features an interview with author Colin Wilson in which he discusses his views regarding society and art, his reclusive nature, and the intellectual and fantastical elements of his works, undated
Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets
No full textThough iterated maps and dynamical systems are not new to combinatorics, they have enjoyed a renewed prominence over the past decade through the elevation of the subfield that has become known as dynamical algebraic combinatorics. Some of the problems that have gained popularity can also be cast and analyzed as finite asynchronous cellular automata (CA). However, these two fields are fairly separate, and while there are some individuals who work in both, that is the exception rather than the norm. In this article, we will describe our ongoing work on toggling independent sets on graphs. This will be preceded by an overview of how this project arose from new combinatorial problems involving homomesy, toggling, and resonance. Though the techniques that we explore are directly applicable to ECA rule 1, many of them can be generalized to other cellular automata. Moreover, some of the ideas that we borrow from cellular automata can be adapted to problems in dynamical algebraic combinatorics. It is our hope that this article will inspire new problems in both fields and connections between them
Providence College Faculty Author Series 2017-2018: D. Colin Jaundrill
No full textIn this installment of the Faculty Authors Series, D. Colin Jaundrill (History, Providence College) discusses his newest book, Samurai to Soldier: Remaking Military Service in Nineteenth-Century Japan
- …
