Monthly Archives: December 2011

The Number of NSEW Lattice Paths with a Maximum Height of y

Posted on December 31, 2011 by mzspivey

I’ve been thinking and learning some about lattice path statistics lately, and a couple of days ago I worked out the answer to the following question (with help from some suggestions from Anthony Quas via Math Overflow). Suppose we have … Continue reading →

Posted in combinatorics, lattice paths | Leave a comment

Checking Multiplication via Digit Sums

Posted on December 27, 2011 by mzspivey

Last week a friend who is a fourth grade teacher came to me with a math problem.  The father of one of his students had showed him a trick for checking the result of a three-digit multiplication problem.  The father … Continue reading →

Posted in arithmetic, number theory | 4 Comments

A Combinatorial Proof of a Formula Involving Euler’s Totient Function

Posted on December 20, 2011 by mzspivey

Several years ago I found a proof of the following identity, which I had not seen before (and still haven’t seen anywhere else): where is Euler’s totient function, the number of positive integers less than or equal to and relatively … Continue reading →

Posted in combinatorics, number theory | 2 Comments

The Duality “Gap” in Linear Programming

Posted on December 17, 2011 by mzspivey

Wait… what?  Doesn’t the strong duality theorem imply that there is no duality gap in linear programming?  Mostly, yes, although there is a sense in which there actually is a duality gap; it occurs when the primal and dual problems … Continue reading →

Posted in linear programming, optimization | 3 Comments

Solving Two-Term Combinatorial Recurrence Relations

Posted on December 14, 2011 by mzspivey

Many named combinatorial numbers satisfy the following general two-term combinatorial recurrence relation: For example: Binomial coefficients: Stirling cycle numbers: Stirling subset numbers: Lah numbers: Eulerian numbers: Second-order Eulerian numbers: It is not known how to solve the recurrence in general. … Continue reading →

Posted in combinatorics, recurrence relations | 1 Comment

Harmonic Numbers and Stirling Numbers

Posted on December 10, 2011 by mzspivey

This post will present three proofs of the following representation of harmonic numbers in terms of Stirling cycle numbers (or unsigned Stirling numbers of the first kind):   Each proof uses a different property of the Stirling numbers. Proof 1: … Continue reading →

Posted in combinatorics, sequences and series | Leave a comment

Generating Geometric and Truncated Exponential Random Variates

Posted on December 5, 2011 by mzspivey

If you do numerical simulations you often find yourself needing to generate random variates from a specific distribution.  There are several techniques for doing this, such as the inverse transform method and the acceptance-and-rejection method.  This post will talk about … Continue reading →

Posted in probability, simulation | Leave a comment

Using Indicator Variables to Calculate Expected Values

Posted on December 1, 2011 by mzspivey

Indicator variables can often be used to find an expected value when doing the calculation directly from the definition would be quite difficult.  This post will look at a couple of examples and give references to several more. First example … Continue reading →

Posted in probability | Leave a comment