What is the largest number of recipes that could be created from n ingredients?

Question

My friend is a cocktail enthusiast who just moved internationally and had to leave his liquor bottles behind. He has a book of 200 or so recipes that he's copied all the required ingredients to a file and now trying to figure out what bottles he should buy to create the maximum number of possible drinks.

Obviously the answer is to buy all of them if you want to be able to make the most number of recipes. A better question would be how many recipes can be made with n bottles. If we can see that there's a large jump in the number of possible recipes that can be created between 5 and 6 ingredients, then it would make sense to get the 6th.

This seems like a straightforward enough question but I'm having trouble wrapping my head around it. Are there similar problems that we could use as a model for this one?

EDIT: For this problem I care about the specific recipes in my file.

Answer 1

This is essentially the "maximum $k$-intersection" problem:

Given a set $S$, some subsets $\{S_1,\dots,S_n\}$ of $S$, and an integer $k$, how can we choose $k$ of the subsets $S_{i_1},\dots,S_{i_k}$ so that $\left|\bigcap_{\ell=1}^k S_{i_\ell}\right|$ is as large as possible?

In your case, we can take $S$ to be the set of all recipes. For each ingredient $i$, we form the set $S_i$ consisting of all the recipes which do not use the ingredient $i$. Then the intersection of $S_{i_1},\dots,S_{i_k}$ consists of all those recipes which do not use any of the ingredients $i_1,\dots,i_k$; that is, they can be made using only the remaining $n-k$ ingredients. So finding the maximum number of recipes you can make with $n-k$ ingredients is exactly equivalent to solving the maximum $k$-intersection problem.

For example, suppose your recipe file contained the following four recipes:

• Gin and tonic: gin, tonic water
• Vodka tonic: vodka, tonic water
• Screwdriver: vodka, orange juice
• Whiskey neat: whiskey

Then we would have \begin{align} S_\text{gin}&=\{\text{vodka tonic}, \text{screwdriver}, \text{whiskey neat}\}\\ S_\text{tonic water}&=\{\text{screwdriver}, \text{whiskey neat}\}\\ S_\text{vodka}&=\{\text{gin and tonic},\text{whiskey neat}\}\\ S_\text{orange juice}&=\{\text{gin and tonic},\text{vodka tonic},\text{whiskey neat}\}\\ S_\text{whiskey}&=\{\text{gin and tonic},\text{vodka tonic},\text{screwdriver}\} \end{align}

If we wanted to know how many recipes you can make with at most $3$ of these $5$ ingredients, you'd look for the largest possible intersection of $5-3=2$ sets. In this case we can get a two-element intersection in various ways: \begin{align} S_\text{gin} \cap S_\text{whiskey}&= \{\text{vodka tonic},\text{screwdriver}\} \\ S_\text{orange juice} \cap S_\text{whiskey}&=\{\text{gin and tonic},\text{vodka tonic}\} \\ S_\text{gin} \cap S_\text{tonic water}&= \{\text{screwdriver},\text{whiskey neat}\} \end{align} and so on. For example, the first line says we can get two viable cocktails by buying everything except whiskey and gin. For this particular recipe file, this is the maximum number you can get with three ingredients, as there are no $4$-element sets and no two of the $3$-element sets are identical.

Unfortunately, this problem is in general NP-hard, as proved, e.g., here. So for general inputs, it's probably computationally intractable, at least to come up with an exact solution. However, there may be some hope.

If you don't have too many ingredients, a brute-force solution might be good enough. In this case "too many" probably starts somewhere around 25-30, at least if you want to hit arbitrary values of $k$; with $n$ ingredients, the brute force approach will involve checking $2^n$ possible combinations.

Also, finding the exact optimal solution is difficult, but there are good algorithms for finding solutions that are close to optimal. For example, this paper gives such an algorithm (for the minimum $k$-union problem, which is trivially equivalent to the maximum $k$-intersection problem). Note that this still seems to be an active area of research; the peer-reviewed version of that paper was published in 2017.

Answer 2

If the order of composition of the ingredients does not matter, I guess adding the $(n+1)$-th ingredient increases the amount of recipes $R_n$ by \begin{align} R_{n+1}-R_n =&\,\sum_{m=1}^{n+1} \frac{(n+1)!}{(n+1-m)!m!}-\sum_{m=1}^{n} \frac{n!}{(n-m)!m!}\\ =&\,1+ \sum_{m=1}^{n} \frac{n+1}{n+1-m}\frac{n!}{(n-m)!m!}-\sum_{m=1}^{n} \frac{n!}{(n-m)!m!}\\ =&\,1+ \sum_{m=1}^{n} \left(\frac{n+1}{n+1-m}-1\right)\frac{n!}{(n-m)!m!}\\ =&\,1+ \sum_{m=1}^{n} \left(\frac{m}{n+1-m}\right)\frac{n!}{(n-m)!m!}. \end{align}

Answer 3

I'm going to assume that any combination of these will work for your question.

The number of ways you can choose $r$ objects from a set of $n$ is given by $\binom{n}{r}=\frac{n!}{r!(n-r)!}$. You can use $nCr$ on your calculator for this too

If we take your example of using $5$ ingredients, there is $\binom{5}{5}=1$ recipe for $5$ ingredients, and $\binom{5}{5}+\binom{5}{4}+\binom{5}{3}+\binom{5}{2}+\binom{5}{1}=31$ for any number of recipes. In short, you are comparing the sum: $$\sum_{r=1}^{n}{\binom{n}{r}}$$ For increasing values of $n$. The value of this sum is $2^n-1$, based off the identity $$\sum_{r=0}^{n}{\binom{n}{r}}=2^n$$

The comparison of term $n$ with term $n+1$ gives: $$\frac{2^{n+1}-1}{2^n-1}=\frac{2(2^n-1)+1}{2^n-1}=2+\frac{1}{2^n-1}$$ Which we can interpret as the number of recipes one can make as nearly doubling each time you add a new ingredient. Here are the first few $$n=1\to F=3$$ $$n=2\to F=2.\dot{3}$$ $$n=3\to F=2.\dot{1}4285\dot{7}$$ $$n=4\to F=2.0\dot{6}$$ $$n=5\to F=2.0322...$$ In conclusion, there is no real cap, doubling the number of recipes by adding just one ingredient is beneficial no matter how many you have.