math 401 test 1

Question 1

an m-by-n board has a perfect cover by b-ominos if and only if

Answer 1

b is a factor of m or n

Question 2

the magic number for magic squares

Answer 2

s = [n(n^2 + 1)] / 2

each row, column, and the two diagonals add to this

Question 3

how to find the magic square when n is odd

Answer 3

1. place a 1 in the middle square of the top row
2. place successive integers in natural order along upward-right sloping diagonal line
3. when top is reached, but in bottom row as if it came immediately above the top row
4. if box is already filled, put immediately below the last square filled

Question 4

any map can be colored by using ? colors such that two countries sharing a common boundary receive different colors

Answer 4

4

Question 5

latin square of order n

Answer 5

n-by-n array of numbers 1 to n such that each 1 to n occurs once in each row and column

Question 6

orthogonal latin squares

Answer 6

all possible n^2 pairs (i, j) with i = 1, 2, … , n and j = 1, 2, … , n; occur when two latin squares are juxtaposed

Question 7

euler says orthogonal works if n is ?; n = ?

Answer 7

odd; n = 4s

Question 8

the game of nim: when will player 1 win? player 2?

Answer 8

player 1 will win an unbalanced game

player 2 will win a balanced game

Question 9

if the game of nim is unbalanced, what should player 2’s first move be?

Answer 9

balance the game

Question 10

how to tell if a game of nim is balanced

Answer 10

write out the numbers’ binary representations and add down the columns. if all numbers are equal then it is balanced

Question 11

addition principle

Answer 11

the number of objects in a set S can be determined by finding the number of objects in each of the parts and adding the numbers

Question 12

multiplication principle

Answer 12

let S be a set of ordered pairs (a, b) of objects, where the first object comes from a set of size p, and for each choice of a there are q choices for object b. Then |S| = pq

Question 13

subtraction principle

Answer 13

|A| = |U| - |A complement|

Question 14

division principle

Answer 14

let S be a finite set that is partitioned into k parts in such a way that each part contains m objects. then k = |S| / m

Question 15

inclusion exclusion

Answer 15

good - bad

Question 16

permutations of sets

Answer 16

an ordered arrangement of r elements without repetition; P(n, r) = n! / (n-r)!

Question 17

circular r-permutation of a set of elements

Answer 17

an ordered arrangement of r elements around a circle of r positions without repetition; P(n, r) / r = n! / r(n-r)!

Question 18

combinations of sets

Answer 18

an unordered selection of r elements without repetition; (n choose r) = P(n, r) / r! = n! / (n-r)!r!

Question 19

Pascal’s Formula

Answer 19

n choose k = (n-1 choose k) + (n-1 choose k-1)

one subset containing “special” and one excluding it

Question 20

For any n >= 0, n choose 0 + n choose 1 + … + n choose n =

Answer 20

2^n

Question 21

permutations of multisets

Answer 21

an ordered arrangement of r elements of S with repetition

Question 22

Let S be a multiset with objects of k different types, where each object has an infinite repetition number. Then the number of permutations of S is

Answer 22

k^r

Question 23

Let S be a multiset of objects of k different types with finite repetition numbers n1, n2, …, nk respectively. Let the size of S be n = n1+n2+…+nk. Then the number of permutations of S equals

Answer 23

n! / n1!n2!…nk!

Question 24

Let n, n1, n2, …, nk be positive integers with n = n1+n2+…+nk. Then the number of ways to partition a set of n objects into k labeled boxes such that box 1 contains n1 objects, box 2 contains n2, etc. equals ?

If the boxes are not labeled and n1=n2=…=nk, then the number of partitions equals ?

Answer 24

n! / n1!n2!…nk!

n! / k!n1!n2!…nk!

Question 25

There are n rooks of k colors with n1 rooks of the first color, n2 rooks of the second color, …, nk rooks of the kth color. The number of sways to arrange these rooks on an n-by-n board such that no rooks can attack each other is

Answer 25

(n!)^2 / n1!n2!…nk!

Question 26

combinations of multisets

Answer 26

an unordered selection of r elements of S with repetition

Question 27

Let S be a multiset with objects of k types, each with an infinite repetition number. Then the number of r-combinations of S equals

Answer 27

(r+k-1 choose r) which equals (n+k-1 choose k-1)

Question 28

pigeonhole principle simple form

Answer 28

if n+1 objects are put into n boxes, then at least one box contains two or more objects

Question 29

if n objects are put into n boxes and no box is empty, then

Answer 29

each box contains exactly one object

Question 30

if n objects are put into n boxes and no box gets more than one object, then

Answer 30

each box contains exactly one object

Question 31

pigeonhole principle strong form

Answer 31

Let q1, q2, …, qn be positive integers. If q1+q2+…+qn - n+1 objects are put into n boxes, then there exists an i with 1 <= i <= n such that the ith box contains at least qi objects

Question 32

if n(r-1)+1 objects are put into n boxes, then

Answer 32

at least one box contains r or more objects

Question 33

if the average of n nonnegative integers m1, m2, …, mn is greater than r-1, then

Answer 33

at least one of the integers is >= r

Question 34

if the average of n nonnegative integers m1, m2, …, mn is less than r+1, then

Answer 34

at least one of the integers is < r+1

Question 35

a theorem of Ramsey

Answer 35

if m>=2 and n>=2 are integers, there exists a positive integer p such that Kp => Km, Kn. The smallest number p such that Kp => Km, Kn is called the Ramsey number, denoted by r(m,n)

Question 36

algorithm for generating all permutations of a set

Answer 36

begin with 1 2 … n with all left arrows
while there is a mobile integer do
1. find the largest mobile integer m
2. switch m with adjacent integer its arrow points to
3. switch direction of all integers greater than m

Question 37

for a set {1, 2, …, n}, 1 can never be ? and n is ? except ?

Answer 37

1 can never be mobile
n is mobile except if n is in the first position and its arrow points left or n is in the last position and its arrow points right

Question 38

Let i1, i2, …, in be a permutation of {1, 2, …, n}. The pair (ik, il) is called an inversion if k < l and ik > il. Let aj equal the number of integers which precede j in the permutation but are greater than j for i<=j<=n. The sequence of numbers a1, a2, …, an is called

Answer 38

the inversion sequence

Question 39

Let b1, b2, …, bn be a sequence of integers satisfying 0<=b1<=n-1, 0<=b2<=n-2, …, 0<=bn-1<=1, bn=0. Then there exists a unique permutation of {1, 2, …, n} whose inversion sequence is

Answer 39

b1, b2, …, bn

Question 40

Algorithm 1 for determining permutations from inversion sequences

Answer 40

Start from n - write down n
For n-1, if bn-1 = 0, write n-1 before n; if bn-1=1, write n-1 after n
…
For n-k, if bn-k = 0, write (n-k) before the current sequence; if bn-k = 1, write (n-k) between the first two elements of the current permutation; if bn-k = k, write (n-k) in the last position of the permutation
…
Put 1 after the b1’s position of the permutation created

Question 41

Algorithm 2 for determining permutations from inversion sequences

Answer 41

Begin with n empty locations labeled 1, 2, …, n from L to R
Put 1 in the location number b1+1;
Put 2 in the b2+1-th empty location counting from the left;
…
k (general step): Put k in the bk+1th empty location counting from the left;
…
Put n in the remaining empty location;

Question 42

the number of r-permutations of a set

Answer 42

n choose r

Question 43

the number of r-combinations of a set

Answer 43

(r+k-1) choose r

Question 44

total number of nonnegative integer solutions to x1+x2+…+xk = r

Answer 44

(r+k-1) choose r