Discrete Structures - Spring-2021 Assignment-02: Counting + Principle of Inclusion-Exclusion

Discrete Structures – Spring-2021 Assignment-02 Due Date: 7 May 2021
Counting + Principle of Inclusion–Exclusion

Problem 1
Part A: We want to make a 6 character password such that the password must start and end with a digit. Moreover,
one digit must be even and other must be odd. There must be one capital letter.
How many such password can we make?
Note: Characters for password can be Capital letters, Small letters and Digits.
Part B: Consider the letters {L, A, H, O, R, E}.
If w arrange all the anagrams (permutations) of LAHORE in alphabetical order, what will be the 413th word?
Problem 2
Suppose that a department contains 10 men and 15 women. How many ways are there to form a committee with six
members if it must have the same number of men and women?
Problem 3
You want to send postcards to 12 friends. In the shop there are only 3 kinds of postcards. In how many ways can you
send the postcards, if
(a) there is a large number of each kind of postcard, and you want to send one card to each friend;
(b) there is a large number of each kind of postcard, and you are willing to send one or more postcards to each friend
(but no one should get two identical cards);
(c) the shop has only 4 of each kind of postcard, and you want to send one card to each friend?
Problem 4
There is a class of 40 girls. There are 18 girls who like to play chess, and 23 who like to play soccer. Several of them like biking.
The number of those who like to play both chess and soccer is 9. There are 7 girls who like chess and biking, and 12 who like
soccer and biking. There are 4 girls who like all three activities.
In addition we know that everybody likes at least one of these activities. How many girls like biking?
Problem 5
a. How many positive integers not bigger than 20 are divisible by either 2 or 3?
b. Find all primes less than a speciﬁed positive integer n. (let’s say n =100).
Pigeonhole Principle
Problem 6
a. How many cards must be chosen from a standard deck of 52 cards to guarantee that at least two of four aces (A) are chosen?
b. How many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of
two different kinds?
c. How many cards must be chosen from a standard deck of 52 cards to guarantee that at least two cards of the same kind?
d. How many cards must be chosen from a standard deck of 52 cards to guarantee that at least two of the four aces (A) and two
of the 13 kinds are chosen?
(Hint: Two cards are of the same kind, if they have same number or figure. They may belong to different suits, e.g. a 3 of club
and a 3 of hearts are of the same kind.)
Problem 7
A drawer contains 6 pairs of black, 5 pairs of white, 5 pairs of red, and 4 pairs of green socks.
a. How many single socks do we have to take out to make sure that we take out two socks with the same color?
b. How many single socks do we have to take out to make sure that we take out two socks with different colors?
Problem 8
We select 38 even positive integers, all less than 1000. Prove that there will be two of them whose difference is at most 26.
Generalized Counting
Problem 9
a. How many possible passwords can be formed from the letters: ASSISTANT_TITAN ?
b. How many different strings can be made from the letters in MISSISSIPPI, using all the letters?
c. How many different strings can be made from the letters in ABRACADABRA, using all the letters?
Problem 10
a. How many non-negative integer solutions are there of the equation: x + y + z + w = 15?
b. How many solutions are there to the equation:
Discrete Structures – Spring-2021 Assignment-02 Due Date: 7 May 2021
𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 + 𝒙𝟒 + 𝒙𝟓 = 𝟐𝟓
such that 𝒙𝟏 ≥ 𝟏, 𝒙𝟐 ≥ 𝟓, 𝒙𝟑 ≥ 𝟏𝟓.
c. How many non-negative integer solutions are there of the equation: x + y + z + w = 15, such that 𝒘 = 𝟓, 𝒛 ≥ 𝟓?
Problem 11
In how many ways can you distribute n pennies to k children if each child is supposed to get at least 5 pennies?
Problem 12
A toy shop has 15 airplanes, 15 buses, 17 trains, and 20 bikes in the stock.
a. How many ways are there for a person to take 15 toys home if all the airplanes are identical, all the buses are
identical, all the trains are identical and all the bikes are identical?
b. How many ways are there for a person to take 15 toys home if all the airplanes are distinct, all the buses are
distinct, all the trains are distinct and all the bikes are distinct?
c. How many ways are there for a person to take 25 toys home if all the airplanes are identical, all the buses are
identical, all the trains are identical and all the bikes are identical?
Problem 13
In how many ways can you read off the word MATHEMATICS from the following tables:
Combinatorial Identities
Problem 14
a. What is the coefficient of x101y99 in the expansion of (2x − 3y)200.
b. What is the coefficient of x9 in (2 − x)19
c. Give a formula for the coefficient of xk in the expansion of (10x + 20/x)100, where k is zero i.e. it is just a constant.
(We shall get a term independent of 𝒙).
Problem 15
Prove the following identities using combinatorail argument. (No algebraic expansion, manipulation at all)

Discrete Structures - Spring-2021 Assignment-02: Counting + Principle of Inclusion-Exclusion

Uploaded by

Copyright:

Available Formats

Discrete Structures - Spring-2021 Assignment-02: Counting + Principle of Inclusion-Exclusion

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Structures - Spring-2021 Assignment-02: Counting + Principle of Inclusion-Exclusion

Uploaded by

Copyright:

Available Formats

Discrete Structures – Spring-2021 Assignment-02 Due Date: 7 May 2021

Counting + Principle of Inclusion–Exclusion

You might also like