Consider tiling a 1 times 100 rectangular board with a red, blue or green square
ID: 3027277 • Letter: C
Question
Consider tiling a 1 times 100 rectangular board with a red, blue or green square tile. The total number of tilings is. b) The number of nonnegative integer solutions to the equation x_1 + x_2 + x_3 = 12 is c) There are injective distributions of 8 identical toys to 10 children. d) There are surjective distributions of 12 distinct toys to 7 children so that each child is assigned at least one toy. e) There are distributions of 5 distinct candy bars to 9 children so that no child receives more than one candy bar?Explanation / Answer
a) Size of the rectangular board is 1 x 100. Therefore, the size of the tiles is 1 x 1. So total number of tilings is 100.
b) The required solutions to the given equation are of the form (x1, x2, x3) where each xi {0,1,2,…,12} & xi = 12
c) Let X and Y be two finite sets having n and m elements. In other words, |X| = n, |Y| = m
Then there are m!/(m – n)! one-one functions (injections) from X to Y provided m > n. If m < n, there does not exists any one-one map.
Therefore, there are 10!/(10 – 8)! = 10!/2! Injective distributions of 8 identical toys to 10 children.
Answer: 10!/2!
d) Number of onto functions from a set A containing m elements to a set B containing n elements = n! S(m, n)
Where S(m, n) is the Stirling number of the second kind.
The Stirling number gives the number of ways of dividing up A into n non-empty pieces, and the n! then gives the number of ways of assigning those pieces to the n elements of B.
Therefore, there are 7! S(12, 7) surjective distributions of 12 distinct toys to 7 children so that each child is assigned at least one toy.