# Find the number of ways of cooking dishes subject to these restrictions

I have the following problem: In $N$ days, I have to do at most $K$ tasks given that I can do only single task in one day and can do every task in $M$ ways. In how many ways can I do this? For instance, I have $N=1$, $K=1$ and $M=1$.

The problem can be interpreted as that in $N=1$ day, I have to do at most $K=1$ task given that I can do that task in $M=1$ ways. So what are the number of ways I can do this task and the answer for this is $1$. But I am confused over the general formula for the problem.

For $N=4$, $M=3$, $K=2$, the answer comes out to be $45$, but I am get baffles on seeing the answers.

Added later. This is the exact question; can you now help me about it?

Chef Dengklek will open a new restaurant in the city. The restaurant will be open for $N$ days. He can cook $M$ different types of dish. He would like to cook a single dish every day, such that for the entire $N$ days, he only cook at most $K$ distinct types of dishes. In how many ways can he do that?

-
Your revised question suggests that exactly one task must be done each day and that the same task can be done on different days; that was not obvious from the initial question – Henry Nov 4 '11 at 7:57
Is the fact that this question is a combinatorics question or not, a question? If it is not, you might skip the question mark in the title. – Did Nov 4 '11 at 8:29
How do you know the answer is 45? How do you know the answer for 5, 7, 3 is 5887? What are you not telling us? – Gerry Myerson Nov 4 '11 at 11:35
@Gerry Myerson these are the sample test cases for the problem at hand lol you made it a mission critical problem ;) dont worry man its not that important and i m nt hiding anything – AnkitSablok Nov 4 '11 at 14:55

Answer edited in light of comment: In your Chef Dengklek question, if $M=K$, then the number of possible ways of cooking up to $K$ different dishes in $N$ days would be $K^N$. So the number of ways of cooking exactly $K$ different dishes would be $K^N-{K \choose 1}(K-1)^N+{K \choose 2}(K-2)^N-\cdots$; this can also be written as $K! S_2(N,K)$ where $S_2$ are Stirling numbers of the second kind.

So allowing $M\ge K$, the number of ways of cooking exactly $K$ different dishes would be ${M \choose K}K! S_2(N,K)$ so the total number of possible ways of cooking up to K different dishes in N days is $$\sum_{i=1}^K {M \choose i}i! S_2(N,i).$$

For $N=4$, $M=3$, $K=2$, this gives $${3 \choose 1}1!\times S_2(4,1)+ {3 \choose 2}2!\times S_2(4,2) = 3\times 1 \times 1 + 3\times 2 \times 7 = 3+42=45.$$

-
for N=5 M=7 K=3 the answer is 5887 but with your formula the answer comes out to be 5782 so there may be something wrong in the fromula – AnkitSablok Nov 4 '11 at 9:13
I have edited the answer in the light of that comment. Note $7\times 1\times 1 + 21\times 2\times 15 + 35\times 6\times 25 = 7 + 630 + 5250 = 5887$ – Henry Nov 4 '11 at 12:58

I, too, am baffled by 45. First, choose the 2 days when you'll do the tasks; this can be done in $4\times3=12$ ways. 3 ways to do each task means multiply by a couple of threes, getting $12\times3\times3=108$. And this is assuming you do both tasks - you say, "do at most $K$ tasks," so you have to add in all the ways of just doing one task, and the one way of not doing any task. So I get a lot more than 45.

-
this is the exact question can you now help me about it – AnkitSablok Nov 4 '11 at 7:00
Chef Dengklek will open a new restaurant in the city. The restaurant will be open for N days. He can cook M different types of dish. He would like to cook a single dish every day, such that for the entire N days, he only cook at most K distinct types of dishes. In how many ways can he do that? – AnkitSablok Nov 4 '11 at 7:00

I will assume that you have to do exactly $K$ tasks.Under this assumption general formula is:

$$n=\frac{N!}{(N-K)!}\cdot M^{K}$$

where $n$ is number of ways.

As Gerry pointed out you have to add in all those solutions when number of tasks is less than $K$ in order to get number of all possible ways.

EDIT:

Number of all possible ways is given by :

$$\sum_{i=0}^K \frac{N!}{(N-i)!}\cdot M^{i}$$

-
this is the exact question can you now help me -: – AnkitSablok Nov 4 '11 at 7:00
Chef Dengklek will open a new restaurant in the city. The restaurant will be open for N days. He can cook M different types of dish. He would like to cook a single dish every day, such that for the entire N days, he only cook at most K distinct types of dishes. In how many ways can he do that? – AnkitSablok Nov 4 '11 at 7:00
@Ankit,see edit.. – pedja Nov 4 '11 at 7:07