Stars and Bars

Problem

Count the ways to choose k items from n types when order does not matter but repetition is allowed. The stars and bars formula gives C(n + k - 1, k).

Return 0 if n <= 0 or k < 0, and 1 when k = 0.

Hint

Transform the problem into placing k dividers among n + k - 1 slots.

case 1

in: [3,2]

expected: 6

case 2

in: [5,0]

expected: 1

case 3

in: [1,4]

expected: 1

case 4

in: [4,3]

expected: 20

case 5

in: [0,2]

expected: 0

Starter codePython

import math


def stars_and_bars(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor