Michael Z. Spivey
Department of Mathematics and Computer Science
University of Puget Sound
- Ph.D., operations research, Princeton University, Princeton, New Jersey, 2001.
- M.A., operations research, Princeton University, Princeton, New Jersey, 1999.
- M.S., mathematics, Texas A&M University, College Station, Texas, 1997.
- B.S., mathematics, Samford University, Birmingham, Alabama, 1994.
- High school diploma, humanities, Louisiana School for Math, Science, and the Arts, Natchitoches, Louisiana, 1991.
- A Combinatorial Proof for the Alternating Convolution of the Central Binomial Coefficients,
American Mathematical Monthly, 121 (6): 537-540, 2014.
- We give a combinatorial proof of the identity for the alternating convolution of the central binomial coefficients. Our proof entails applying an involution to certain
colored permutations and showing that only permutations containing cycles of even length remain.
- The Lah Numbers and the nth Derivative of e1/x, with Siad Daboul, Jan Mangaldan, and Peter Taylor. Mathematics Magazine, 86 (1): 39-47,
- We give five proofs that the coefficients in the nth derivative of exp(1/x) are the Lah numbers, a triangle of integers whose best-known applications are in combinatorics and finite difference calculus.
Our proofs use tools from several areas of mathematics, including binomial coefficients, Faà di Bruno's formula, set partitions, Maclaurin series, factorial powers, the Poisson probability distribution, and hypergeometric functions. The
paper is based on the discussion to Siad's question about the nth derivative of exp(1/x) on Math Stack Exchange.
- Optimal Discounts for the Online Assignment Problem. Operations Research Letters, 41: 112-115, 2013.
- This paper proves that, for two simple functions drlt, solving the online assignment problem with crl - drlt as the contribution for assigning resource r to task
l at time t gives the optimal solution to the corresponding offline assignment problem (provided the optimal offline solution is unique). We call such functions drlt optimal discount functions.
This paper gives a simpler proof of the results in one of my dissertation papers, "Some Fixed-Point Results for the Dynamic Assignment Problem," as well as answering the
major open theoretical question from my dissertation.
- Enumerating Lattice Paths Touching or Crossing the Diagonal at a Given Number of Lattice Points. Electronic Journal of Combinatorics,
19 (3): Article P24, 2012.
- This paper gives bijective proofs that, when combined with one of the combinatorial proofs of the general ballot formula, constitute a combinatorial argument yielding the number of lattice paths from (0; 0) to
(n; rn) that touch or cross the diagonal y = rx at exactly k lattice points. The enumeration partitions all lattice paths from (0; 0) to (n; rn). While the resulting formula can be derived
using results from Niederhausen, the bijections and combinatorial proof are new.
- On Solutions to a General Combinatorial Recurrence. Journal of Integer Sequences, 14 (9): Article 11.9.7, 2011.
- This paper gives a partial solution to research problem 6.94 in Concrete Mathematics. It shows how to solve a large class of two-term combinatorial recurrence relations in terms of sums of binomial coefficients
and the two kinds of Stirling numbers. Some known combinatorial identities involving named numbers (e.g., Stirling, Eulerian, Bell) are given a more unified treatment, and some new identities are proved.
- Asymptotic Moments of the Bottleneck Assignment Problem. Mathematics of Operations Research, 36 (2): 205-226, 2011.
- In this paper we give a method by which one can find all of the asymptotic moments of a random bottleneck assignment problem in which costs (independent and identically distributed) are chosen from a wide variety of
continuous distributions. The results improve on those obtained by Pferschy in the mid-90s.
- The Poisson Process and Associated Probability Distributions on Time Scales, with Dylan Poulsen and Robert
Marks. IEEE 43rd Southeastern Symposium on System Theory (SSST): 49-54, March 2011.
- As the title indicates, this article develops the Poisson process and the related Poisson, Erlang, and exponential distributions for a general time scale. As an application, the Poisson distribution and the binomial
distribution are shown to be the same probability distribution on different time scales. (Most of this work was done by Dylan as a summer project while he was an undergraduate. He is now a PhD student at Baylor University.)
- Cycles in War. Integers, 10: Article G2, 747-764, 2010.
- We discuss a simplified version of the well-known card game War in which the cards in the deck have a strict ranking from 1 to n and in which the winning card and losing card are immediately placed, in that
order, at the bottom of the winning player's deck. Under this variation of War we show that it is possible for a standard fifty-two card deck to cycle, and we exhibit such a cycle. This result is a special case of a more general
result that exhibits a cycle construction for an n-card deck for any value of n that is not a power of 2 or 3 times a power of 2. We also discuss results that show that under some assumptions the types of cycles we
exhibit are the only types of cycles that can occur.
- Visualising Continued Fractions. Mathematical Gazette, 94 (530): 284-290, 2010.
- This paper describes a method for visualizing finite continued fractions in terms of a grid.
- Deranged Exams. College Mathematics Journal, 41 (3): 197-202, 2010.
- This expository paper discusses a triangle of numbers Sn,k that are related to the derangement numbers. The Sn,k numbers satisfy a
Pascal-like recurrence relation with subtraction instead of addition. We describe how they relate to numbers studied by other authors and use them to generalize Euler's famous recurrence
relation for the derangement numbers.
- Staircase Rook Polynomials and Cayley's Game of Mousetrap. European Journal of Combinatorics, 30 (2): 532-539, 2009.
- We determine the rook polynomials for two special classes of card decks arising in the game of Mousetrap, introduced by Arthur Cayley 150 years ago.
- A Generalized Recurrence for Bell Numbers. Journal of Integer Sequences, 11 (2): Article 08.2.5, 2008.
- We give a combinatorial proof of a result that generalizes the two most well-known expressions for Bell numbers.
- Symmetric Polynomials, Pascal Matrices, and Stirling Matrices, with Andy Zimmer. Linear Algebra and Its Applications, 428 (4):
- We consider lower-triangular matrices consisting of symmetric polynomials, and we show how to factorize and invert them. Since binomial coefficients and Stirling numbers can be
represented in terms of symmetric polynomials, these results contain factorizations and inverses of Pascal and Stirling matrices as special cases. This work generalizes that of several other
authors on Pascal and Stirling matrices. (Andy did his part of the work as an undergraduate at the University of Puget Sound; he is now a graduate student at the University of Michigan.)
- Counting Functions and Finite Differences, with Natalio Guersenzvaig. Integers, 7: Article A59, 2007.
- Any increasing function p(d) on the natural numbers has an associated counting function pi(n) that yields the number of inputs d for which p(d) <=
n. In this article we derive three formulas that relate a sequence to its finite difference sequence by way of counting functions and the technique of summation by parts. We demonstrate
our formulas by using them to produce several identities for Fibonacci numbers and binomial coefficients.
- Combinatorial Sums and Finite Differences. Discrete Mathematics, 307 (24): 3130-3146, 2007.
- This paper shows how the binomial transform of
a sequence is related to the binomial transform of the finite difference of the sequence. This relationship can be used to give fairly quick derivations of some known binomial sum identities.
The approach is then modified so that it applies to alternating binomial sums, aerated binomial sums, and to sums involving signed and unsigned Stirling numbers of the first kind. The paper
concludes with a generalization of the results for binomial sums and unsigned Stirling numbers of the first kind.
- Quadratic Residues and the Frobenius Coin Problem. Mathematics Magazine, 80 (1): 64-67, 2007.
- An odd prime p has (p-1)/2 quadratic residues mod p, and for relatively prime p and q there are (p-1)(q-1)/2 non-representable
Frobenius numbers. We show that there is a relationship between the non-representable Frobenius numbers of p and q and the quadratic residues of p that accounts for the
presence of (p-1)/2 in both expressions.
- Fibonacci Identities via the Determinant Sum Property. College Mathematics Journal, 37 (4): 286-289, 2006.
- We use the sum property for determinants of matrices to give a three-stage proof of an identity involving Fibonacci numbers. Cassini's and d'Ocagne's Fibonacci identities are obtained at the
ends of stages one and two, respectively. Catalan's Fibonacci identity is also a special case.
- Some Inversion Formulas for Sums of Quotients, with Natalio Guersenzvaig. Crux Mathematicorum, 32 (1): 39-43, 2006.
- This paper proves some identities related to summing the quotients of an integer n from two different directions. The results generalize a problem posed in a previous issue
- The Euler-Maclaurin Formula and Sums of Powers. Mathematics Magazine, 79 (1): 61-65, 2006.
- This paper uses the Euler-Maclaurin formula for approximating a sum by an integral to prove that the limiting value of a certain expression related to the power sum is 1/(e-1).
- See also my letter to the editor, Mathematics Magazine, 83 (1): 54-55, 2010.
- The k-Binomial Transforms and the Hankel Transform, with Laura Steil. Journal of Integer Sequences, 9 (1): Article 06.1.1, 2006.
- We give a new proof of the invariance of the Hankel transform under the binomial transform of a sequence. Our method of proof leads to three variations of the binomial transform;
we call these the k-binomial transforms. We give a simple means of constructing these transforms via a triangle of numbers. We show how the exponential generating function of a sequence
changes after our transforms are applied, and we use this to prove that several sequences in the On-Line Encyclopedia of Integer Sequences are related via our transforms. In the process,
we prove three conjectures in the OEIS. Addressing a question of Layman, we then show that the Hankel transform of a sequence is invariant under one of our transforms, and we show how the
Hankel transform changes after the other two transforms are applied. Finally, we use these results to determine the Hankel transforms of several integer sequences. (This is an extension of
Laura's undergraduate senior thesis; she is now a professor at Mars Hill College in North Carolina.)
- The Humble Sum of Remainders Function. Mathematics Magazine, 78 (4): 300-305, 2005.
- Given an integer n, define the sum of remainders function such that when n is input to the function, the output is the sum of the the remainders obtained by dividing
n successively by 1, 2, ..., n. This paper describes two uses of the sum of remainders function: 1) It provides a simple alternative characterization of perfect numbers, and
2) together with the more famous sum of divisors function, it helps give an expression for the sums of powers of the first n positive integers.
- The Dynamic Assignment Problem, with Warren Powell. Transportation Science, 38 (4): 399-419, 2004. (c)
- In this paper we introduce the dynamic assignment problem, which involves the solution of assignment problems over time with evolving information on the availability of resources and tasks, contributions
for assigning them, and restrictions on the availability of assignments. The paper includes 1) a formal model of the problem, 2) an adaptive approximation strategy for problems with relatively small state
spaces based on the values of resources, tasks, and resource-task pairs that significantly outperforms greedy heuristics, and 3) an extension of this strategy, based on aggregations of
resources and tasks, to problems with larger state spaces. (This paper represents the bulk of the work from my Ph. D. dissertation.)
- Some Fixed-Point Results for the Dynamic Assignment Problem, with Warren Powell. Annals of Operations
Research, 124: 15-33, 2003.
- In the process of testing the adaptive approximation algorithm described in the following paper, we discovered that for certain problem classes, when the optimal solution is input to our
algorithm, the algorithm outputs the optimal solution in the next iteration. This means that the optimal solution is a fixed point under our algorithm for these problem classes. This paper
contains the proofs of this for two of these classes (provided the optimal solution is unique).
- "A Product Calculus." This paper describes an alternate form of calculus, one in which multiplication plays the role that addition does in the usual calculus. This
kind of calculus is not new, but it was not very well-known, and the purpose of my paper was to advertise it. The paper was first written in the summer of 2006. I tried for a few years to have it published and was unsuccessful. In
the intervening years other authors published articles describing the same kind of calculus, it has become more well-known, and I have decided it is not worth my while to continue to try to publish my version. I offer it here for
anyone who is interested. For more information, see the Wikipedia article on multiplicative calculus.
- "L'Hôpital's Rules and Taylor's Theorem for Product Calculus," with Alex Twist. This paper is a follow-up to my product calculus paper. Most of the work was
done by my student Alex during the summer of 2007.
- Solution to Problem 2826, with P. Bornsztein, et al. Crux Mathematicorum, 30 (3): 178-179, April 2004.
- Solution to Problem 2834, with C. Curtis. Crux Mathematicorum, 30 (3): 186, April 2004.
- Solution to Problem 1, 32nd Austrian Mathematics Olympiad, Crux Mathematicorum, 31 (6): 376, October 2005.
- Problem 1737, Mathematics Magazine, 79 (1): 67, February 2006. Also, see the discussion of this problem at Cut-the-Knot.
- Letter to the editor, Mathematics Magazine, 83 (1): 54-55, 2010. (This letter contains some comments on - including the correction to a mistake in - my paper
``The Euler-Maclaurin Formula and Sums of Powers" that appeared in the February 2006 issue of Mathematics Magazine.)