0
$\begingroup$

Imagine you have been given n different colored balls and a task to choose at most k balls from them such that none of the same colored balls is selected for any given sequence and considering same colored balls as non-identical (distinguishable).

For example

$5$ Balls: Red, Red, Blue, Blue, Green. You have to choose at most $3$ balls.

So the solution would be:

  • k = $0$ $\Rightarrow$ { $\Phi$ } = $1$ //Empty Set
  • k = $1$ $\Rightarrow${(red), (red), (blue), (blue), (green)} = $5$
  • k = $2$ $\Rightarrow$ {(red, blue), (red, blue), (red, blue), (red, blue), (red, green), (red, green), (blue, green) , (blue, green) } = $8$
  • k = $3$ $\Rightarrow$ {(red, blue, green), (red, blue, green), (red, blue, green), (red, blue, green)} = $4$

So the total number of possible ways are: $18$

Is it possible to solve this problem using Stars and bars; Assuming 3 Buckets

  • Bucket 1 = [ Red, Red]
  • Bucket 2 = [ Blue, Blue]
  • Bucket 3 = [ Green]

With a general approach with $n$ and $K$, Or is to possible to generalize it calculating sets where we have same colored balls and subtracting it with all possible sets.

$\endgroup$