How many ways are for K people to work a one-day shift for N days so each of them works at least one day

Question

1. Each person must work at least a day.
   2. Only one person can work in a given day.

Example: 2 people, 3 days -> 6 -> (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1)

Answer 1

What you want is ${N \brace K}K!$. Where the brackets denote the Stirling number of the second kind.

This is because, first you must split the $N$ days into $K$ non-empty groups (this can be done in $N\brace K$ ways ). And then, these $K$ groups must be distributed among the $K$ persons, this can be done in $K!$ ways.

Calculating the Stirling numbers of the second kind on a computer is easy with a recursion, just as easy as calculating binomial coefficients, the important recursion is ${N\brace K}=K{N-1\brace K}+{N-1\brace K-1}$.

The following C++ code calculates ${ N \brace K}$ with the previous method:

#include <iostream>
using namespace std;

const int MAX=100;
int ST[MAX][MAX]; // here we store  {i,j} with i,j under MAX

int main(){
    for(int i=1; i<MAX; i++){
        ST[i][1]=1;
    }
    for(int i=1; i<MAX; i++){
        for(int j=2; j<MAX; j++){
            ST[i][j]=j*ST[i-1][j] + ST[i-1][j-1];
        }
    }
    int N,K;
    cin >> N >> K;
    cout << ST[N][K] << endl;
}

---

There is another way which does not use recursion (assuming you calculate the binomial coefficients otherwise).

It is the formula ${N \brace K} = \frac{1}{K!}\sum\limits_{i=0}^K(-1)^{K-i}\binom{K}{i}i^n$.

So your final answer is also $\sum\limits_{i=0}^K(-1)^{K-i}\binom{K}{i}i^n$. (the proof of this is simple via inclusion/exclusion)

This formula allows you to calculate each query in linear time (with respect to $K$).

The other method allows you to precalculate all of the queries in time $K\cdot N$, but it answers each query in constant time.