Discrete Mathematics and Combinatorics Commons^™

Optimizing Buying Strategies In Dominion, Nikolas A. Koutroulakis

Rose-Hulman Undergraduate Mathematics Journal

Dominion is a deck-building card game that simulates competing lords growing their kingdoms. Here we wish to optimize a strategy called Big Money by modeling the game as a Markov chain and utilizing the associated transition matrices to simulate the game. We provide additional analysis of a variation on this strategy known as Big Money Terminal Draw. Our results show that player's should prioritize buying provinces over improving their deck. Furthermore, we derive heuristics to guide a player's decision making for a Big Money Terminal Draw Deck. In particular, we show that buying a second Smithy is always more optimal …

The Vulnerabilities To The Rsa Algorithm And Future Alternative Algorithms To Improve Security, James Johnson

Cybersecurity Undergraduate Research Showcase

The RSA encryption algorithm has secured many large systems, including bank systems, data encryption in emails, several online transactions, etc. Benefiting from the use of asymmetric cryptography and properties of number theory, RSA was widely regarded as one of most difficult algorithms to decrypt without a key, especially since by brute force, breaking the algorithm would take thousands of years. However, in recent times, research has shown that RSA is getting closer to being efficiently decrypted classically, using algebraic methods, (fully cracked through limited bits) in which elliptic-curve cryptography has been thought of as the alternative that is stronger than …

Divisibility Probabilities For Products Of Randomly Chosen Integers, Noah Y. Fine

Rose-Hulman Undergraduate Mathematics Journal

We find a formula for the probability that the product of n positive integers, chosen at random, is divisible by some integer d. We do this via an inductive application of the Chinese Remainder Theorem, generating functions, and several other combinatorial arguments. Additionally, we apply this formula to find a unique, but slow, probabilistic primality test.

On The Order-Type Complexity Of Words, And Greedy Sidon Sets For Linear Forms, Yin Choi Cheng

Dissertations, Theses, and Capstone Projects

This work consists of two parts. In the first part, we study the order-type complexity of right-infinite words over a finite alphabet, which is defined to be the order types of the set of shifts of said words in lexicographical order. The set of shifts of any aperiodic morphic words whose first letter in the purely-morphic pre-image occurs at least twice in the pre-image has the same order type as Q ∩ (0, 1), Q ∩ (0, 1], or Q ∩ [0, 1). This includes all aperiodic purely-morphic binary words. The order types of uniform-morphic ternary words were also studied, …

One Formula For Non-Prime Numbers: Motivations And Characteristics, Mahmoud Mansour, Kamal Hassan Prof.

Basic Science Engineering

Primes are essential for computer encryption and cryptography, as they are fundamental units of whole numbers and are of the highest importance due to their mathematical qualities. However, identifying a pattern of primes is not easy. Thinking in a different way may get benefits, by considering the opposite side of the problem which means focusing on non-prime numbers. Recently, researchers introduced, the pattern of non-primes in two maximal sets while in this paper, non-primes are presented in one formula. Getting one-way formula for non-primes may pave the way for further applications based on the idea of primes.

Decomposition Of Beatty And Complementary Sequences, Geremías Polanco

Mathematics Sciences: Faculty Publications

In this paper we express the difference of two complementary Beatty sequences, as the sum of two Beatty sequences closely related to them. In the process we introduce a new Algorithm that generalizes the well known Minimum Excluded algorithm and provides a method to generate combinatorially any pair of complementary Beatty sequences.

Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon

Senior Theses

This thesis begins with a selective overview of problems in geometric graph theory, a rapidly evolving subfield of discrete mathematics. We then narrow our focus to the study of unit-distance graphs, Euclidean coloring problems, rigidity theory and the interplay among these topics. After expounding on the limitations we face when attempting to characterize finite, separable edge-maximal unit-distance graphs, we engage an interesting Diophantine problem arising in this endeavor. Finally, we present a novel subclass of finite, separable edge-maximal unit distance graphs obtained as part of the author's undergraduate research experience.

Generalized Far-Difference Representations, Prakod Ngamlamai

HMC Senior Theses

Integers are often represented as a base-$b$ representation by the sum $\sum c_ib^i$. Lekkerkerker and Zeckendorf later provided the rules for representing integers as the sum of Fibonacci numbers. Hannah Alpert then introduced the far-difference representation by providing rules for writing an integer with both positive and negative multiples of Fibonacci numbers. Our work aims to generalize her work to a broader family of linear recurrences. To do so, we describe desired properties of the representations, such as lexicographic ordering, and provide a family of algorithms for each linear recurrence that generate unique representations for any integer. We then prove …

Meertens Number And Its Variations, Chai Wah Wu

Communications on Number Theory and Combinatorial Theory

In 1998, Bird introduced Meertens numbers as numbers that are invariant under a map similar to the Gödel encoding. In base 10, the only known Meertens number is 81312000. We look at some properties of Meertens numbers and consider variations of this concept. In particular, we consider variations of Meertens numbers where there is a finite time algorithm to decide whether such numbers exist, exhibit infinite families of these variations and provide bounds on parameters needed for their existence.

(R1979) Permanent Of Toeplitz-Hessenberg Matrices With Generalized Fibonacci And Lucas Entries, Hacène Belbachir, Amine Belkhir, Ihab-Eddine Djellas

Applications and Applied Mathematics: An International Journal (AAM)

In the present paper, we evaluate the permanent and determinant of some Toeplitz-Hessenberg matrices with generalized Fibonacci and generalized Lucas numbers as entries.We develop identities involving sums of products of generalized Fibonacci numbers and generalized Lucas numbers with multinomial coefficients using the matrix structure, and then we present an application of the determinant of such matrices.

Unomaha Problem Of The Week (2021-2022 Edition), Brad Horner, Jordan M. Sahs

UNO Student Research and Creative Activity Fair

The University of Omaha math department's Problem of the Week was taken over in Fall 2019 from faculty by the authors. The structure: each semester (Fall and Spring), three problems are given per week for twelve weeks, with each problem worth ten points - mimicking the structure of arguably the most well-regarded university math competition around, the Putnam Competition, with prizes awarded to top-scorers at semester's end. The weekly competition was halted midway through Spring 2020 due to COVID-19, but relaunched again in Fall 2021, with massive changes.

Now there are three difficulty tiers to POW problems, roughly corresponding to …

Structure Of Number Theoretic Graphs, Lee Trent

Mathematical Sciences Technical Reports (MSTR)

The tools of graph theory can be used to investigate the structure
imposed on the integers by various relations. Here we investigate two
kinds of graphs. The first, a square product graph, takes for its vertices
the integers 1 through n, and draws edges between numbers whose product
is a square. The second, a square product graph, has the same vertex set,
and draws edges between numbers whose sum is a square.
We investigate the structure of these graphs. For square product
graphs, we provide a rather complete characterization of their structure as
a union of disjoint complete graphs. For …

Generating B-Nomial Numbers, Ji Young Choi

Communications on Number Theory and Combinatorial Theory

This paper presents three new ways to generate each type of b-nomial numbers: We develop ordinary generating functions, we find a whole new set of recurrence relations, and we identify each b-nomial number as a single binomial coefficient or as an alternating sum of products of two binomial coefficients.

Distribution Of The P-Torsion Of Jacobian Groups Of Regular Matroids, Sergio R. Zapata Ceballos

Electronic Thesis and Dissertation Repository

Given a regular matroid $M$ and a map $\lambda\colon E(M)\to \N$, we construct a regular matroid $M_\lambda$. Then we study the distribution of the $p$-torsion of the Jacobian groups of the family $\{M_\lambda\}_{\lambda\in\N^{E(M)}}$. We approach the problem by parameterizing the Jacobian groups of this family with non-trivial $p$-torsion by the $\F_p$-rational points of the configuration hypersurface associated to $M$. In this way, we reduce the problem to counting points over finite fields. As a result, we obtain a closed formula for the proportion of these groups with non-trivial $p$-torsion as well as some estimates. In addition, we show that the …

Introduction To Discrete Mathematics: An Oer For Ma-471, Mathieu Sassolas

Open Educational Resources

The first objective of this book is to define and discuss the meaning of truth in mathematics. We explore logics, both propositional and first-order , and the construction of proofs, both formally and human-targeted. Using the proof tools, this book then explores some very fundamental definitions of mathematics through set theory. This theory is then put in practice in several applications. The particular (but quite widespread) case of equivalence and order relations is studied with detail. Then we introduces sequences and proofs by induction, followed by number theory. Finally, a small introduction to combinatorics is …

Contributions To The Teaching And Learning Of Fluid Mechanics, Ashwin Vaidya

Department of Mathematics Facuty Scholarship and Creative Works

This issue showcases a compilation of papers on fluid mechanics (FM) education, covering different sub topics of the subject. The success of the first volume [1] prompted us to consider another follow-up special issue on the topic, which has also been very successful in garnering an impressive variety of submissions. As a classical branch of science, the beauty and complexity of fluid dynamics cannot be overemphasized. This is an extremely well-studied subject which has now become a significant component of several major scientific disciplines ranging from aerospace engineering, astrophysics, atmospheric science (including climate modeling), biological and biomedical science …

Irreducibility And Galois Groups Of Random Polynomials, Hanson Hao, Eli Navarro, Henri Stern

Rose-Hulman Undergraduate Mathematics Journal

In 2015, I. Rivin introduced an effective method to bound the number of irreducible integral polynomials with fixed degree d and height at most N. In this paper, we give a brief summary of this result and discuss the precision of Rivin's arguments for special classes of polynomials. We also give elementary proofs of classic results on Galois groups of cubic trinomials.

Determinant Formulas Of Some Hessenberg Matrices With Jacobsthal Entries, Taras Goy, Mark Shattuck

Applications and Applied Mathematics: An International Journal (AAM)

In this paper, we evaluate determinants of several families of Hessenberg matrices having various subsequences of the Jacobsthal sequence as their nonzero entries. These identities may be written equivalently as formulas for certain linearly recurrent sequences expressed in terms of sums of products of Jacobsthal numbers with multinomial coefficients. Among the sequences that arise in this way include the Mersenne, Lucas and Jacobsthal-Lucas numbers as well as the squares of the Jacobsthal and Mersenne sequences. These results are extended to Hessenberg determinants involving sequences that are derived from two general families of linear second-order recurrences. Finally, combinatorial proofs are provided …

Mathematical Magic: A Study Of Number Puzzles, Nicasio M. Velez

Rose-Hulman Undergraduate Mathematics Journal

Within this paper, we will briefly review the history of a collection of number puzzles which take the shape of squares, polygons, and polyhedra in both modular and nonmodular arithmetic. Among other results, we develop construction techniques for solutions of both Modulo and regular Magic Squares. For other polygons in nonmodular arithmetic, specifically of order 3, we present a proof of why there are only four Magic Triangles using linear algebra, disprove the existence of the Magic Tetrahedron in two ways, and utilizing the infamous 3-SUM combinatorics problem we disprove the existence of the Magic Octahedron.

Tiling Representations Of Zeckendorf Decompositions, John Lentfer

HMC Senior Theses

Zeckendorf’s theorem states that every positive integer can be decomposed uniquely into a sum of non-consecutive Fibonacci numbers (where f₁ = 1 and f₂ = 2). Previous work by Grabner and Tichy (1990) and Miller and Wang (2012) has found a generalization of Zeckendorf’s theorem to a larger class of recurrent sequences, called Positive Linear Recurrence Sequences (PLRS’s). We apply well-known tiling interpretations of recurrence sequences from Benjamin and Quinn (2003) to PLRS’s. We exploit that tiling interpretation to create a new tiling interpretation specific to PLRS’s that captures the behavior of the generalized Zeckendorf’s theorem.

The Name Tag Problem, Christian Carley

Rose-Hulman Undergraduate Mathematics Journal

The Name Tag Problem is a thought experiment that, when formalized, serves as an introduction to the concept of an orthomorphism of $\Zn$. Orthomorphisms are a type of group permutation and their graphs are used to construct mutually orthogonal Latin squares, affine planes and other objects. This paper walks through the formalization of the Name Tag Problem and its linear solutions, which center around modular arithmetic. The characterization of which linear mappings give rise to these solutions developed in this paper can be used to calculate the exact number of linear orthomorphisms for any additive group Z/nZ, which is demonstrated …

Arithmetical Structures On Paths With A Doubled Edge, Darren B. Glass, Joshua R. Wagner

Math Faculty Publications

An arithmetical structure on a graph is given by a labeling of the vertices that satisfies certain divisibility properties. In this note, we look at several families of graphs and attempt to give counts on the number of arithmetical structures for graphs in these families.

Combinatorial And Asymptotic Statistical Properties Of Partitions And Unimodal Sequences, Walter Mcfarland Bridges

LSU Doctoral Dissertations

Our main results are asymptotic zero-one laws satisfied by the diagrams of unimodal sequences of positive integers. These diagrams consist of columns of squares in the plane; the upper boundary is called the shape. For various types of unimodal sequences, we show that, as the number of squares tends to infinity, 100% of shapes are near a certain curve---that is, there is a single limit shape. Similar phenomena have been well-studied for integer partitions, but several technical difficulties arise in the extension of such asymptotic statistical laws to unimodal sequences. We develop a widely applicable method for obtaining these limit …

Consecutive Prime And Highly Total Prime Labeling In Graphs, Robert Scholle

Rose-Hulman Undergraduate Mathematics Journal

This paper examines the graph-theoretical concepts of consecutive prime labeling and highly total prime labeling. These are variations on prime labeling, introduced by Tout, Dabboucy, and Howalla in 1982. Consecutive prime labeling is defined here for the first time. Consecutive prime labeling requires that the labels of vertices in a graph be relatively prime to the labels of all adjacent vertices as well as all incident edges. We show that all paths, cycles, stars, and complete graphs have a consecutive prime labeling and conjecture that all simple connected graphs have a consecutive prime labeling.

This paper also expands on work …

Combinatorial Identities On Multinomial Coefficients And Graph Theory, Seungho Lee

Rose-Hulman Undergraduate Mathematics Journal

We study combinatorial identities on multinomial coefficients. In particular, we present several new ways to count the connected labeled graphs using multinomial coefficients.

An Exploration Of The Use Of The Fibonacci Sequence In Unrelated Mathematics Disciplines, Molly E. Boodey

Honors Theses and Capstones

No abstract provided.

Adjoint Appell-Euler And First Kind Appell-Bernoulli Polynomials, Pierpaolo Natalini, Paolo E. Ricci

Applications and Applied Mathematics: An International Journal (AAM)

The adjunction property, recently introduced for Sheffer polynomial sets, is considered in the case of Appell polynomials. The particular case of adjoint Appell-Euler and Appell-Bernoulli polynomials of the first kind is analyzed.

Some Results And Examples On Vertex Equitable Labeling, Mohamed Saied Aboshady, Reda Amin Elbarkoki, Eliwa Mohamed Roshdy, Mohamed Abdel Azim Seoud

Basic Science Engineering

In this paper we present a survey for all graphs with order at most 6 whether they are vertex equitable or not and we get an upper bound for the number of edges of any graph with 𝑝 vertices to be a vertex equitable graph. Also, we establish vertex equitable labeling for the 𝑚-chain of the complete bipartite graph 𝐾2,𝑛 and for the graph 𝑃𝑛 × 𝑃𝑚.

Greatest Common Divisor: Algorithm And Proof, Mary K. Flagg

Number Theory

No abstract provided.

Congruence Relations Mod 2 For (2 X 4^T + 1)-Colored Partitions, Nicholas Torello

Senior Theses

Let p_r(n) denote the difference between the number of r-colored partitions of n into an even number of distinct parts and into an odd number of distinct parts. Inspired by proofs involving modular forms of the Hirschhorn-Sellers Conjecture, we prove a similar congruence for p_r(n). Using the Jacobi Triple Product identity, we discover a much stricter congruence for p_3(n).