How many ways can you make change for a dollar? This post points to two approaches to the problem, one computational and one analytic.
SICP gives a Scheme program to solve the problem:
(define (count-change amount) (cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
Concrete Mathematics explains that the number of ways to make change for an amount of n cents is the coefficient of zn in the power series for the following:
Later on the book gives a more explicit but complicated formula for the coefficients.
Both show that there are 292 ways to make change for a dollar.
How many k × k magic squares are possible? If you start from a liberal definition of magic square, there’s an elegant result. For the purposes of this post, a magic square is a square arrangement of non-negative numbers such that the rows and columns all sum to the same non-negative number m called the magic constant. Note that this allows the possibility that numbers will be repeated, and this places no restriction on the diagonals.
With this admittedly non-standard definition, the number of k × k magic squares with magic constant m is always a polynomial in m of degree no more than (k – 1)2. For k = 3, the result is
(m + 1)(m + 2)(m2 + 3m + 4)/8
There is no general formula for all k, but there is an algorithm for finding a formula for each value of k.
Source: The Concrete Tetrahedron
Update: I had reported the polynomial degree as k + 1, but looking back at Concrete Tetrahedron, that book lists the order as (k + 1)2. However, the paper cited in the comments lists the exponent as (k – 1)2, which I believe is correct.
More on magic squares