Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Please help me out. Thanks in advance.


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?

share|improve this question
1  
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
1  
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
3  
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

3 Answers 3

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.$$

share|improve this answer
    
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.

share|improve this answer
    
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}$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.