Find number of red balls after K turns if you paint Q balls from a bag of N distinct ones

Question

This was a question from Infinix Hiring challenge, which ended few days ago.

You have N distinct white balls, and want to paint balls in a red color, instead of painting all of them simultaneously, you decide to take turns. You paint the balls by following these steps:

1. Choose Q balls from the bag
2. Paint the Q with red color
3. Put them back into the bag

Note: Among the chosen Q, red balls remain red but white ones are converted to red You take exactly K turns. In other words, you follow the steps K times. Given N, Q, K, tell how no.of ways each number of balls are colored after K turns. Your task is to determine the number of red balls in the bag after K turns.

Two ways are considered different if the set of selected balls differ in at least one of the K turns.

Sample Explanation: Lets say N = 3, Q = 2, K = 2, then there are 3 balls in the bag, you take 2 turns, and in each you chose 2 balls.

Lets number them 1 to 3, The possible ways are,

(1,2),(1,2) - Total colored are 2 - (1,2)
(1,2),(1,3) - Total colored are 3 - (1,2,3)
(1,2),(2,3) - Total colored are 3 - (1,2,3)
(1,3),(1,2) - Total colored are 3 - (1,2,3)
(1,3),(1,3) - Total colored are 2 - (1,3)
(1,3),(2,3) - Total colored are 3 - (1,2,3)
(2,3),(1,2) - Total colored are 3 - (1,2,3)
(2,3),(1,3) - Total colored are 3 - (1,2,3)
(2,3),(2,3) - Total colored are 2 - (2,3)

So there are 0 ways in which exactly 1 ball is painted red, 3 ways in which exactly 2 balls are painted, 6 ways in which exactly 3 balls are painted red.

What I tried: I started with small numbers, took 5 numbers (1,2,3,4,5) and Q = 2, K = 2.

(1,2)(1,2) = 2 from the first pair, 0 from the second = 2

(1,2)(1,[3|4|5]) = 2 from the first, +1 from the second = 3, 
and this happens 3 times for each of the numbers mentioned in square braces, 
and the same happens for the below one

(1,2)(2,[3|4|5]) = 2 + 1, happens 3 times

(1,2)(3C2 from [3|4|5]) = 2 + 2, happens 3C2 times
And this is true for all distinct 5C2 pairs. ( please correct me if I'm wrong )

Now 5 numbers, Q = 3, K = 2

(1,2,3)(1,2,3) = 2 + 0

Change in one number,
(1,2,3)(1,2,[4|5]) = 2 + 1 happens twice

Change in two numbers,
(1,2,3)(1,2C2) = 2 + 2 happens once

But when there are more than two turns i.e., when K is 3, I facing difficulties in finding method to make a formula, as I'm weak in Combinatorics.

Answer 1

I'll use more standard mathematical notation, $n$ for your N, $q$ for your Q, and $k$ for your K.

By a Generalised inclusion-exclusion principle, the number of ways to fulfil exactly $j$ out of $n$ conditions is

$$ \sum_{l=j}^n(-1)^{l-j}\binom lj\binom nlb_l\;, $$

where $b_l$ is the number of ways to fulfil $l$ particular conditions.

Here we have $n$ conditions of a ball staying white. The number of ways of fulfilling $l$ particular ones of them is

$$ b_l=\binom{n-l}q^k\;, $$

since there are $\binom{n-l}q$ ways to select $q$ balls from the remaining $n-l$ balls, and we do this $k$ times. Thus the number of ways in which exactly $j$ of the balls can remain white is

$$ \sum_{l=j}^n(-1)^{l-j}\binom lj\binom nl\binom{n-l}q^k\;. $$

In your example with $n=3$, $q=2$, $k=2$, for $j=0$ this is

$$ \sum_{l=0}^3(-1)^{l-0}\binom l0\binom3l\binom{3-l}2^2=\binom32^2-3\binom22^2=6\;, $$

and for $j=1$ it is

$$ \sum_{l=1}^3(-1)^{l-1}\binom l1\binom3l\binom{3-l}2^2=3\binom22^2=3\;, $$

in agreement with your results.