Monthly Archives: December 2011

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

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

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, elementary number theory | 4 Comments

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

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, elementary number theory | 2 Comments

The Duality “Gap” in Linear Programming

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

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

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

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