How many ways can n balls be placed in k boxes?
Answers
Answered by
0
Hey mate, I already solved this question yesterday for my cousin's assignment. I am going to paste the same answer here. Please mark brainliest if you like. Thanks :)
Let x1,x2,…,xkx1,x2,…,xk be the numbers of balls placed in box 1,2,…,k1,2,…,k, respectively.
Then you are asking for the number of solutions in positive integers of the equationx1+x2+⋯+xk=nx1+x2+⋯+xk=n
There are many ways you can go about this.
You could denote this number by f(n,k)f(n,k) and set up a recurrence, you could find a bijection between these solutions and a more familiar set or you could use generating functions.
Notice that f(n,k)f(n,k) is the coefficient of tntn in the expression
(t+t2+⋯)k = tk(1−t)k = tk(∑m=0∞(m+k−1k−1)tm)(t+t2+⋯)k = tk(1−t)k = tk(∑m=0∞(m+k−1k−1)tm)
So the number you are looking for is (n−1k−1).
Let x1,x2,…,xkx1,x2,…,xk be the numbers of balls placed in box 1,2,…,k1,2,…,k, respectively.
Then you are asking for the number of solutions in positive integers of the equationx1+x2+⋯+xk=nx1+x2+⋯+xk=n
There are many ways you can go about this.
You could denote this number by f(n,k)f(n,k) and set up a recurrence, you could find a bijection between these solutions and a more familiar set or you could use generating functions.
Notice that f(n,k)f(n,k) is the coefficient of tntn in the expression
(t+t2+⋯)k = tk(1−t)k = tk(∑m=0∞(m+k−1k−1)tm)(t+t2+⋯)k = tk(1−t)k = tk(∑m=0∞(m+k−1k−1)tm)
So the number you are looking for is (n−1k−1).
Similar questions