4. Let n ≥ 8 be an even integer and let k be an integer with...

4. Let n ≥ 8 be an even integer and let k be an integer with 2 ≤ k ≤ n/2. Consider k-element subsets of the set S = {1, 2, . . . , n}. How many such subsets contain at least two even numbers?

Solutions

Expert Solution

Since $n\geq 8$ is an even integer, let n=2m. And let k be an integer such that $2\leq k\leq m$ . Now the set S has 2m elements, so from S we can choose k elements in $^{2m}C_k$ ways, i.e., S has $^{2m}C_k$ numbers of k-element subsets.

Now to find the number of subsets containing atleast two even integers, we find the number of subsets which contains no even integer or exactly one even integer. Now observe that S has exactly m odd integers and exactly n even integers. So to find the number of subsets containing no even integer (that is, the subset contains odd integers only), we have to choose k elements from m odd integers of S, which can be chosen in $^{m}C_k$ ways. Hence, the number of subsets of S that contains no even integer is $^{m}C_k$ . Now let's find the number of subsets containing exactly one even integer. So the subset will contain exactly one even integer ( which can be any of m even integers of S) and k-1 odd integers (which has to chosen from m odd integers of S). So the even integer can be chosen in m ways and the k-1 odd integers can be chosen in $^{m}C_{k-1}$ ways. Hence, the number of subsets containing exactly one even integer is $m\cdot {^{m}C_{k-1}}$ .

So the number of subsets of S that contains less than 2 even integers is $^mC_k+m\cdot {^{m}C_{k-1}}$ and hence the number of subsets that contains atleast 2 even integers is $^{2m}C_k-\left (^mC_k+m\cdot {^{m}C_{k-1}}\right )$ where $m=\frac{n}{2}$ .

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

(a) Let n = 2k be an even integer. Show that x = rk is an...

(a) Let n = 2k be an even integer. Show that x = rk is an element of order 2 which commutes with every element of Dn. (b) Let n = 2k be an even integer. Show that x = rk is the unique non-identity element which commutes with every element of Dn. (c) If n is an odd integer, show that the identity is the only element of Dn which commutes with every element of Dn.

Prove that if n is an integer and n^2 is even the n is even.

Let k be an integer satisfying k ≥ 2. Let G be a connected graph with...

Let k be an integer satisfying k ≥ 2. Let G be a connected graph with no cycles and k vertices. Prove that G has at least 2 vertices of degree equal to 1.

Let S_k(n) = 1^k + 2^k + ··· + n^k for n, k ≥ 1. Then,...

Let S_k(n) = 1^k + 2^k + ··· + n^k for n, k ≥ 1. Then, S_4(n) is given by S_4(n)= n(n+1)(2n+1)(3n^2 +3n−1)/ 30 Prove by mathematical induction.

that, given an integer N and an integer K, returns the minimum number of rounds that...

that, given an integer N and an integer K, returns the minimum number of rounds that are necessary for John to leave the casino with N chips, having played all-in no more than K times.

prove that if an even integer n is subtracted from an odd integer m. then m...

prove that if an even integer n is subtracted from an odd integer m. then m - n is odd.

Let n be a positive integer. Prove that if n is composite, then n has a...

Let n be a positive integer. Prove that if n is composite, then n has a prime factor less than or equal to sqrt(n) . (Hint: first show that n has a factor less than or equal to sqrt(n) )

Let n be a positive integer. Let S(n) = n sigma j=1 ((1/3j − 2) −...

Let n be a positive integer. Let S(n) = n sigma j=1 ((1/3j − 2) − (1/3j + 1)). a) Compute the value of S(1), S(2), S(3), and S(4). b) Make a conjecture that gives a closed form (i.e., not a summation) formula for the value of S(n). c) Use induction to prove your conjecture is correct.

Consider an n×n square board, where n is a fixed even positive integer. The board is...

Consider an n×n square board, where n is a fixed even positive integer. The board is divided into n 2 unit squares. We say that two different squares on the board are adjacent if they have a common side. N unit squares on the board are marked in such a way that every unmarked square on the board is adjacent to at least one marked square. Determine the smallest possible value of N.

In C++ Let n be a non-negative integer. The factorial of n, written n!, is defined...

In C++ Let n be a non-negative integer. The factorial of n, written n!, is defined by 0 ! 5 1, n! = 1·2·3· · ·n if n $ 1. For example, 4! = 1·2·3·4 = 24. Write a program that prompts the user to enter a nonnegative integer and outputs the factorial of the number. Allow the user to repeat the program. Example: If the user enters a 3 then your program should perform answer = 3 * 2...

Subjects