Visualizing this problem, as unique ways to hand out ninja stars to ninjas. This also shows how each larger solution is made up of its neighboring, more simple solutions.

alt text http://www.freeimagehosting.net/uploads/58531735d3.png

Here is how to implement it in php: (might help you understand it too)

```
function multichoose($k,$n)
{
if ($k < 0 || $n < 0) return false;
if ($k==0) return array(array_fill(0,$n,0));
if ($n==0) return array();
if ($n==1) return array(array($k));
foreach(multichoose($k,$n-1) as $in){ //Gets from a smaller solution -above as (blue)
array_unshift($in,0); //This prepends the array with a 0 -above as (grey)
$out[]=$in;
}
foreach(multichoose($k-1,$n) as $in){ //Gets the next part from a smaller solution too. -above as (red and orange)
$in[0]++; //Increments the first row by one -above as (orange)
$out[]=$in;
}
return $out;
}
print_r(multichoose(3,4)); //How many ways to give three ninja stars to four ninjas?
```

Not optimal code: Its more understandable that way.

Our output:

```
(0,0,0,3)
(0,0,1,2)
(0,0,2,1)
(0,0,3,0)
(0,1,0,2)
(0,1,1,1)
(0,1,2,0)
(0,2,0,1)
(0,2,1,0)
(0,3,0,0)
(1,0,0,2)
(1,0,1,1)
(1,0,2,0)
(1,1,0,1)
(1,1,1,0)
(1,2,0,0)
(2,0,0,1)
(2,0,1,0)
(2,1,0,0)
(3,0,0,0)
```

Fun use to note: Upc relies upon this exact problem in barcodes. The sum of the whitespace and blackspace for each number is always 7, but is distributed in different ways.

```
//Digit L Pattern R Pattern L\R Pattern (Number of times a bit is repeated)
0 0001101 1110010 2100
1 0011001 1100110 1110
2 0010011 1101100 1011
3 0111101 1000010 0300
4 0100011 1011100 0021
5 0110001 1001110 0120
6 0101111 1010000 0003
7 0111011 1000100 0201
8 0110111 1001000 0102
9 0001011 1110100 2001
```

Note only 10 of the 20 combinations are used, which means the code can be read upside-down just fine. All 20 can be used however, and are in EAN13, with a bit more complexity.

http://en.wikipedia.org/wiki/EAN-13

http://en.wikipedia.org/wiki/Universal_Product_Code

http://www.freeimagehosting.net/uploads/58531735d3.png