# Enigmatic Code

Programming Enigma Puzzles

## Pizza Puzzle

This puzzle is inspired by a combinatorial problem that surfaced in the Feedback section of New Scientist in early 2011. (See issues #2794 and  #2798), and was brought to my attention by Hugh Casement. [link]

Here is the puzzle:

When ordering a pizza from the Enigmatic Pizza Company you can specify the toppings on your pizza. There are 34 possible toppings to choose from, and you can have up to 11 toppings on your pizza. But you can have no more than three helpings of any individual topping.

The most basic pizza available would be one with no toppings at all. And a fully loaded veggie pizza might have 3 helpings of cherry tomatoes, 3 helpings of mixed peppers, 3 helpings of jalapeño peppers and 2 helpings of mozzarella cheese, using up all 11 toppings.

What is the total number of different pizza combinations that are available?

### 8 responses to “Pizza Puzzle”

1. Jim Randell 23 November 2016 at 9:52 am

I looked at defining:

choose(n, k, m)

where:

n = the number of values available (toppings)
k = the number of slots to fill
m = maximum number of times a value can be used

so the number of different toppings for one pizza is: choose(34, 11, 3).

I came up with the following:

choose(n, 0, m) = 1
choose(0, k, m) = 0 [k > 0]
choose(n, 1, m) = n [n > 0, m > 0]

and the general case:

choose(n, k, m) = sum(choose(n – 1, k – i, m) for i = 0 to min(k, m))

I don’t have a closed formula for calculating this, but it can be implemented directly as a computer program.

The code runs in 50ms and gives us:

choose(34, 11, 3) = 7,039,463,632

but that’s if all slots are filled. I suppose we might put fewer than 11 toppings on.

If we consider using only 10 of the slots:

choose(34, 10, 3) = 1,806,739,396

And for fewer than 10:

choose(34, 9, 3) = 428,844,856
choose(34, 8, 3) = 93,303,276
choose(34, 7, 3) = 18,400,800
choose(34, 6, 3) = 3,242,393
choose(34, 5, 3) = 500,786
choose(34, 4, 3) = 66,011
choose(34, 3, 3) = 7,140
choose(34, 2, 3) = 595
choose(34, 1, 3) = 34
choose(34, 0, 3) = 1

sum(choose(34, i, 3) for i = 0 to 11) = 9,390,568,920

Here is the program:

```from enigma import irange, cached, arg, printf

# count the number of (unordered) combinations with repetition
# n - number of values
# k - number of slots to fill
# m - max number of occurrences of each value
@cached
def _choose(n, k, m):
# if there are 0 slots to fill we can do that in 1 way
if k == 0: return 1
# if there are no values there are no ways
if n == 0: return 0
# if there is 1 slot to fill we can do that in n ways
if k == 1: return n
# otherwise we can fill 0 - m slots with the first value
return sum(_choose(n - 1, k - i, m) for i in irange(0, min(k, m)))

# if m is None, we can use as many occurrences as we like (multichoose)
def choose(n, k, m=None):
if m is None: m = k
return _choose(n, k, m)

# command line arguments
N = arg(34, 0, int)
K = arg(11, 1, int)
M = arg( 3, 2, int)
printf("N={N} K={K} M={M}")

# find all solutions with up to K slots
t = 0
for k in irange(0, K):
x = choose(N, k, M)
printf("choose({N}, {k}, {M}) = {x}")
t += x
printf("total = {t}")
```

So, if I’ve worked it out right, this is the total number of different kinds of pizza we could make.

Solution: The total number of pizza combinations available is 9,390,568,920.

I’d be interested to hear from anyone who can verify that this is indeed the solution, or can up with a closed formula for choose(n, m, k) (perhaps using the Inclusion-Exclusion Principle, or Generating Functions).

The Feedback article that inspired this problem is about investigating the claim of a pizza company that “more than 1.8 billion pizza combinations” are available using this method.

The quoted figure is very close to choose(34, 10, 3) = 1,806,739,396, which is the number of pizza combinations if exactly 10 topping options are used (but no more than 3 servings of any of the individual 34 available toppings can be used). But if we were to allow not all the slots to be used we get:

sum(choose(34, i, 3) for i = 0 to 10) = 2,351,105,288

There is also the additional complication of specifying a pizza as two “half-pizzas”, each of which can be specified as above.

This would give a total number of different combinations for one pizza as:

T(sum(choose(34, i, 3) for i = 0 to 11)) = 44,091,392,325,330,267,660

Note that the choose(n, k, m) function with m=1 corresponds to the C(n, k) combinatorial function:

choose(n, k, 1) = C(n, k) = n! / k!(n − k)!

and choose(n, k, k) corresponds to the “multichoose” function:

choose(n, k, k) = M(n, k) = C(n + k − 1, k) = (n + k − 1)! / k!(n − 1)!

2. arthurvause 25 November 2016 at 9:39 am

Here are two variants of a solution using generating polynomials. The first solution sums the combinations for each of 0,1,..11 toppings. The second intruduces a “no flavour” topping which can have up to 11 helpings on a pizza.

```# polynomial multiplication
def mult(a,b):
prod = [0]*(len(a)+len(b)-1)
for i,v in enumerate(a):
for j,w in enumerate(b):
prod[i+j] += v*w
return prod

# generating polynomial 1+x+x^2+x^3
a=[1,1,1,1]
for i in xrange(33):
a = mult(a,[1,1,1,1])
print "combinations for each of 0,1,2,,11 toppings", a[:12]
print "total combinations for 0,1,2,,11 toppings", sum(a[:12])

a=[1,1,1,1]
for i in xrange(33):
a = mult(a,[1,1,1,1])
# generator for a fictitious "no flavour" topping  1+x+x^2+x^3 + ... + x^11
a = mult(a,[1]*12)
print "total combinations for 11 toppings, including a 'no flavour' topping", a[11]
```
3. Paul 25 November 2016 at 9:57 am

They are the coefficients of the generating function (1+x+x^2+x^3)^34, which gives the following:-

1
34
595
7140
66011
500786
3242393
18400800
93303276
428844856
1806739396
7039463632
25548426676
86887295256
278281163196
842918860256
2423475652202
6634470805556
17341148802846
43380805158856
104084976799870
239976458448628
532562712473226
1139331051928416
2352859144971660
4696140231374136
9069162213979428
16963345961804176
30758965447699060
54114045013193176
92439326336974716
153431242064263328
247603544155029095
388721046695453966

• Paul 25 November 2016 at 10:02 am

MMa code to generate the list

Column[CoefficientList[Series[(1+x+x^2+x^3)^34,{x,0,34}],x]]

• Paul 25 November 2016 at 4:13 pm

And in general we have the coefficients of (1+x^2 + x^3 + … x^n)^t

where “n” is the max number of toppings and “t” is max possible toppings to choose from.

I have tested the theory and it seems sound.

P.C.

4. arthurvause 27 November 2016 at 8:41 am

By the way, the October 2012 puzzle in IBM Ponder This illustrates the use of generating polynomials.

5. Jim Randell 27 November 2016 at 1:38 pm

Thanks for the solutions involving generating functions. It’s not a technique I’m used to (although my initial searches did seem to indicate that it might be a way to attack this problem), but I’ve read up a bit about them and it seems to be a very useful technique.

Below are my notes (mostly for my own benefit, but could possibly help explain the technique to someone else who is new to it too).

If we have toppings a, b, c, …, then we can represent using up to three of topping a as:

(a⁰ + a¹ + a² + a³)

Similarly for all the other toppings, giving us the product:

(a⁰ + a¹ + a² + a³)(b⁰ + b¹ + b² + b³)(c⁰ + c¹ + c² + c³)…

which if we multiplied out the product would give us a lot of terms, each one representing a different combination of toppings for a pizza.

So, there will be 1 term with a total of zero toppings:

a⁰b⁰c⁰…

and 34 terms with exactly 1 topping:

a¹b⁰c⁰…, a⁰b¹c⁰…, a⁰b⁰c¹…, …

and so-on until we arrive at the terms with exactly 11 toppings, for example (without the zero exponents this time):

a³b³c³d², …

If we can count the number of terms with exponents that sum to 11, we would find the number of different pizzas with exactly 11 toppings.

By setting x = a = b = c = … we can consider the polynominal:

(x⁰ + x¹ + x² + x³)³⁴

Multiplying this out will give us the same number of terms of x^n as there are pizzas with exactly n toppings.

So we can find the number of pizzas with exactly 11 toppings by determining the co-efficient of x¹¹ in the product.

At this point we can turn to a computer to do the tedious multiplication for us. We can consider a polynomial to be represented by a list, with element 0 containing the co-efficient of x⁰, element 1 containing the co-efficient of and so forth. For example, we would represent (1 + 5x − 7x² + 13x³) as [1, 5, −7, 13].

We can then write code to multiply out two such polynomials (which gives us code very similar to that posted by Arthur above):

```from enigma import printf

# mutliply two polynomials
def poly_mul(p, q):
r = [0] * (len(p) + len(q) - 1)
for (j, b) in enumerate(q):
for (i, a) in enumerate(p):
r[i + j] += a * b
return r

# raise a polynomial to a positive integer power
def poly_pow(p, n):
r = [1]
for _ in range(n):
r = poly_mul(r, p)
return r

# consider the polynomial (x^0 + x^1 + x^2 + x^3)
p = [1, 1, 1, 1]

# raise it to the 34th power
r = poly_pow(p, 34)

# the coefficient of x^11 gives us the number of pizzas with exactly
# 11 toppings
printf("{n} pizzas with exactly 11 toppings", n=r[11])

# summing the first 12 coefficients gives us the number of pizzas with
# up to 11 toppings
printf("{n} pizzas with up to 11 toppings", n=sum(r[:12]))
```

If the restrictions of toppings were less uniform (e.g. you were only allowed two helpings of some toppings, but up to four of others), the generating polynomial could be adjusted accordingly.

The same approach can be used for other combination based problems.

For example, determining how many different ways there are to make change for £1 given 1p, 2p, 5p, 10p, 20p and 50p coins.

We can consider multiplying together the following polynomials (one for each denomination of coin):

(x^0 + x^1 + x^2 + … + x^100)
(x^0 + x^2 + x^4 + … + x^100)
(x^0 + x^5 + x^10 + … + x^100)
(x^0 + x^10 + x^20 + … + x^100)
(x^0 + x^20 + x^40 + … + x^100)
(x^0 + x^50 + x^100)

and then determine the coefficient of x^100 to give us the number of ways to give change for £1.

```# make a polynomial from (exponent, coefficient) pairs
# (we can use enumerate() to reverse the process)
def poly_new(ps):
p = []
for (e, c) in ps:
if c == 0: continue
x = e + 1 - len(p)
if x > 0: p.extend([0] * x)
p[e] += c
return p

# multiply together a collection of polynomials
def poly_multiply(p, *qs):
r = p
for q in qs:
r = poly_mul(r, q)
return r

# denominations and amount
ds = (1, 2, 5, 10, 20, 50)
amount = 100

ps = list(poly_new((n, 1) for n in irange(0, amount, step=d)) for d in ds)
r = poly_multiply(*ps)

printf("{n} ways to make change for {amount}p", n=r[amount])
```

I shall add some routines to the enigma.py library to make it easier to use this technique.

• Tessa Fullwood 12 December 2016 at 8:42 pm

This way calculates the combinations for each set of n toppings, with n <= 11.

For a set of n toppings, n<=11, there are C(34,n) ways of assembling a set of toppings.

If there is a single helping of each topping then this gives 1 combination. If one topping has 2 helpings then this adds C(n, 1) combinations. If two toppings have 2 helpings then this results in C(n,2) extra combinations. If two toppings have 2 helpings and one topping has 3 helpings, then this adds C(n,2) * C(n-2,1) combinations.

These can be extended, using the limit, that total helpings do not exceed 11. The limit applies for 4<= n <= 11.

Totalling up the added combinations with n from 1 to 11, multiplied by the number of ways of assembling a set also results in the total above of 9390568920.