2
$\begingroup$

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?

  • 0
    @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 anything2011-11-04

3 Answers 3

2

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

  • 0
    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$2011-11-04
0

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.

  • 0
    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?2011-11-04
0

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

  • 0
    @Ankit,see edit..2011-11-04