1. What is the total number of functions from a set of size 9 to a set of size 12?

A. \(9^{12}\) B. \(12^9\) C. \(12!\) D. \(9!\)

2. Which of the following is the addition rule for counting?

A. Count the ways to perform stage 1 and multiply by ways in stage 2 B. If given alternative parts \(A_i\), the total ways equal \(\sum |A_i|\) C. Use factorial function D. Use combinations only

3. If sets \(S_1 \subseteq S_2\) and \(S_1 \Rightarrow A\), what can we conclude about \(S_2 \Rightarrow A\)?

A. \(S_2 \Rightarrow A\) is always false B. \(S_2 \Rightarrow A\) is always true C. Cannot conclude anything D. \(S_2 \Rightarrow A\) holds only if \(A\) is atomic

4. What is the value of \(C_n\), the nth Catalan number, in terms of binomial coefficients?

A. \(\frac{1}{n} \binom{2n}{n}\) B. \(\frac{1}{n+1} \binom{2n}{n}\) C. \(\binom{n}{2n}\) D. \(2^n\)

5. Which connective has the highest precedence in propositional logic formulas?

A. \(\to\) B. \(\vee\) C. \(\wedge\) D. \(\neg\)

6. If an argument has premises \(p \to q\), \(q \to r\), which formula is guaranteed to be true?

A. \(p \to r\) B. \(r \to p\) C. \(q \to p\) D. \(r \to q\)

7. If \(X\) has \(n\) elements, how many bijections \(f: X \to X\) are there?

A. \(n\) B. \(n^n\) C. \(n!\) D. \((n-1)!\)

8. What is the main combinatorial tool used to compute the number of ways to place 10 distinct books in two racks each having 5 shelves?

A. Permutations B. Combinations C. Product rule and counting arrangements in compartments D. Inclusion-Exclusion Principle

9. The formula \(p \to q \lor r\) is logically equivalent to which of the following?

A. \(p \land \neg q \to r\) B. \(p \lor q \to r\) C. \(\neg p \to q \land r\) D. \(q \land r \to p\)

10. How many 5-letter words can be formed from the English alphabet if all letters must be distinct?

A. \(26^5\) B. \(26 \times 25 \times 24 \times 23 \times 22\) C. \(5^{26}\) D. \(26 \times 26 \times 26 \times 26 \times 26\)

11. According to the definition of truth assignment, what is \(f(p \to q)\) if \(f(p) = T\) and \(f(q) = F\)?

A. T B. F C. Cannot be determined D. T or F depending on other variables

12. If a polynomial with integer coefficients has \(n\) distinct integer roots for the equation \(f(x) = 2009\), what ensures that the equation \(f(x) = 9002\) has no integer root?

A. \(n = 1\) B. The polynomial is linear C. \(n\) is at least a certain minimum depending on 2009 and 9002 D. There is no relation between number of roots and other values taking integer roots

13. The number of increasing sequences of length \(r\) from the set \(\{1, 2,\ldots, n\}\) is equivalent to:

A. \(n^r\) B. Number of combinations \(C(n,r)\) C. Number of permutations \(P(n,r)\) D. Number of sequences with repetition allowed

14. Given 3 blue bags, 4 red bags, and 5 green bags, what type of combinatorial problem determines the smallest \(n\) such that distributing \(n\) balls guarantees certain color/quantity conditions?

A. Inclusion-Exclusion Principle B. Pigeonhole Principle (Generalized) C. Permutation counting D. Generating functions

15. Which of the following formulas is logically equivalent to \(p \leftrightarrow q\)?

A. \((p \to q) \wedge (q \to p)\) B. \((p \wedge q) \vee (\neg p \wedge \neg q)\) C. \(p \vee q\) D. \(\neg p \vee \neg q\)

16. How many 4-letter words can be formed using letters A, B, C, D such that no three consecutive letters are the same?

A. Total words minus those with any triple repetition B. \(4^4 - 4\) C. \(4^4\) only D. Words with strictly increasing letters

17. How many 12-letter words from \{A, B, C\} do not contain the sub-word "BCA"?

A. Total words minus those with "BCA" as sub-word B. \(3^{12}\) C. Count words using inclusion-exclusion for forbidden substring D. Count words with repeated letters only

18. What is an example of a tautology in propositional logic?

A. \(p \land \neg p\) B. \(p \lor \neg p\) C. \(p \to q\) D. \(\neg p \to q\)

19. A formula involving connectives \(\wedge, \vee, \to\) is assigned all atomic variables to \(T\). What will be the value of the formula?

A. Always \(F\) B. Always \(T\) C. Depends on the formula D. Depends on the number of atoms

20. In counting the number of arrangements where a specific letter precedes another in a multiset word, which approach is most applicable?

A. Direct factorial division only B. Using order restrictions and inclusion-exclusion C. Ignoring the restrictions D. Using combinations only

21. When counting words of length \(n\) made from an alphabet of size \(k\), under what condition does the total count equal \(k^n\)?

A. Letters must be distinct B. Letters can repeat freely C. No two consecutive letters are the same D. Words are strictly increasing

22. When arranging letters with multiple copies (like A, A, A, B, B), how do we calculate the number of distinct words?

A. Use factorial of total number of letters divided by the product of factorials of repeated letters B. Simply factorial of total letters C. Use permutation with repetition formula without division D. Use the number of letters without repetitions

23. How many 4-letter words are there using letters in alphabetical order from the English alphabet?

A. \(26^4\) B. Number of combinations \(C(26,4)\) C. \(26!\) D. \(4!\)

24. Given three atomic variables \(p,q,r\), what is the total number of possible truth assignments?

A. 6 B. 8 C. 9 D. 4

25. What kind of generating function can be used to count the ways to distribute identical balls into distinct boxes with minimum constraints on each box?

A. Ordinary generating function B. Exponential generating function C. Binomial generating function D. Multivariate generating function incorporating constraints

26. What is the truth value \(f(p \vee q)\) if \(f(p) = F\) and \(f(q) = F\)?

A. T B. F C. Cannot be determined D. Depends on other variables

27. What is a composition of a natural number \(n\)?

A. A partition of \(n\) into unordered sums B. An expression of \(n\) as a sum of positive integers, ordered C. A combination of \(n\) elements D. Number of permutations of \(n\)

28. How many permutations of letters in the word "MISSISSIPPI" have no two S letters adjacent?

A. Number of ways arranging all letters minus those with S adjacent B. Use inclusion-exclusion counting C. Treat all S as one letter D. Directly factorial of all letters

29. What does the principle of counting using complements typically help with?

A. Counting complex objects by subtracting easier-to-count unwanted patterns B. Counting only the desired patterns C. Counting multisets D. Recursive counting

30. What is the key monotonicity property in logic concerning sets of formulas?

A. If \(S_1 \subseteq S_2\) and \(S_1 \Rightarrow A\), then \(S_2 \Rightarrow A\) B. If \(S_1 \subseteq S_2\) and \(S_2 \Rightarrow A\), then \(S_1 \Rightarrow A\) C. \(S_1 = S_2\) if both imply \(A\) D. None of the above

31. What is the cardinality of the Cartesian product \(A \times B \times C\) if \(|A|=m\), \(|B|=n\), and \(|C|=p\)?

A. \(m+n+p\) B. \(m \times n \times p\) C. \(\max(m,n,p)\) D. \(\min(m,n,p)\)

32. How is the negation connective \(\neg p\) evaluated in a truth assignment?

A. If \(f(p) = T\), then \(f(\neg p) = T\) B. If \(f(p) = T\), then \(f(\neg p) = F\) C. \(f(\neg p) = f(p)\) D. \(f(\neg p)\) can be arbitrary

33. For license plates with two alphabets followed by two digits, if the sum of digits must be even when starting with a vowel, how is the total number of plates computed?

A. Sum of plates starting with vowels (with even sum) and plates starting with consonants (no restriction) B. Total plates for vowels multiplied by total plates for consonants C. Equal distribution among vowels and consonants D. Counting vowels only

34. Using the multiplication rule, how many distinct 3-digit numbers with digits chosen from \(\{1, 3, 5, 7, 9\}\) can be formed with no repetition?

A. \(5^3\) B. \(5 \times 5 \times 5\) C. \(5 \times 4 \times 3\) D. \(3 \times 4 \times 5\)

35. Which connective binds last according to precedence rules in propositional logic?

A. \(\neg\) B. \(\wedge\) C. \(\to\) D. \(\vee\)

36. Which method can best solve the number of 8-letter words from \{A,B,C,D\} with no 3 consecutive equal letters?

A. Direct counting with restrictions B. Recurrence relations or dynamic programming C. Factorials D. Counting strictly increasing subsequences

37. What is the truth value of the formula \(p \wedge q\) if \(f(p) = T\) and \(f(q) = F\)?

A. T B. F C. Cannot be determined D. T or F depending on context

38. How many ways can we arrange 4 couples in a row if each couple must sit together?

A. \(8!\) B. \(4! \times 2^4\) C. \(4! \times 2!\) D. \(2^4\)

39. What is the formula to calculate the number of ways to form a word of length \(n\) from an alphabet of size \(m\)?

A. \(n^m\) B. \(m^n\) C. \(n + m\) D. \(n \times m\)

40. What does \(P(n,r)\) represent in combinatorics?

A. Number of permutations of \(n\) elements taken \(r\) at a time B. Number of combinations of \(n\) elements taken \(r\) at a time C. Number of functions from \(n\) to \(r\) D. Number of partitions of \(n\) into \(r\) parts

41. Which generating function technique counts the number of distributions of identical items into distinct boxes with lower bounds?

A. Ordinary generating functions with shifted indices B. Exponential generating functions C. Binomial generating functions D. Uniform generating functions without restrictions

42. What does the expression \(\text{Map}([k], S)\) represent in combinatorics?

A. The set of all permutations of \(k\) from \(S\) B. The set of all functions from the set \([k]\) to the set \(S\) C. The power set of \(S\) of size \(k\) D. The number of subsets of size \(k\) of \(S\)

43. What is the number of ways to distribute \(t\) identical books among \(n\) students so that each student gets at least \(s\), if each student can receive multiple copies?

A. Use generating functions with coefficients counting non-negative solutions B. Use permutations C. Use factorial \(t!\) D. Use combinations without repetitions

44. How do we count number of ways to distribute \(t\) identical books to \(n\) students so that each gets at least \(s\) copies, using generating functions?

A. Generating function with factor \((x^s + x^{s+1} + \ldots)^n\) B. Using factorial computations only C. Permutations of books D. Direct counting without generating functions

45. Which combinatorial principle states that if a function \(f : A \to B\) has pre-images of equal sizes \(k\) for all elements in \(B\), then \(|A| = k|B|\)?

A. Principle of Bijection B. Pigeonhole Principle C. Principle of Disjoint Pre-images of Equal Size D. Inclusion-Exclusion Principle

46. For a polygon with \(n\) vertices, how many ways are there to triangulate it using non-crossing diagonals?

A. \(C_{n-2}\), where \(C_m\) is the mth Catalan number B. \(C_{n}\) C. \(n!\) D. \(2^{n-2}\)

47. How many different words of length 9 can be formed from the English alphabet \(\{a,b,\dots,z\}\)?

A. \(26^9\) B. \(9^{26}\) C. \(26 \times 9\) D. \(\binom{26}{9}\)

48. If a committee of 5 students is to be formed from 17 girls and 20 boys, and a treasurer and spokesperson selected from them, how do we count distinct committees?

A. Count combinations of 5 students only B. Count permutations of 5 students only C. Count combinations multiplied by permutations of selecting treasurer and spokesperson D. Count all permutations of 22 students taken 5 at a time

49. How is a truth table for a formula with \(k\) atomic variables constructed?

A. List all \(k\) variables with all \(2^k\) possible truth assignments B. List a subset of assignments only C. Assign truth values arbitrarily D. Use only \(k\) assignments

50. Which condition satisfies the formula \(p \to q \lor r\)?

A. When \(p\) is true and both \(q\) and \(r\) are false, the formula is false B. When \(p\) is false the formula is false C. When \(q\) and \(r\) are true the formula is false D. Always true