Combinatorics › Sets and Venn diagrams

Counting relations and functions

Solve the first problem 18 problems

These are 8 of the 18 problems. Sign in for free to see them all. Sign in

1. Distinct values of f(x) minus x ●○○○○ 10 ptsSuppose the function $f(x)$ is defined explicitly by the table $$\begin{array}{c || c | c | c | c | c} x & 0 & 1 & 2 & 3 & 4 \\ \hline f(x) & 0 & 0 & 1 & 3 & 6 \end{array}$$ This function is defined only for the values of $x$ listed in the table. Suppose $g(x)$ is defined as $f(x)-x$ for all numbers $x$ in the domain of $f$. How many distinct numbers are in the range of $g(x)$?
2. Equivalence classes from given related pairs ●○○○○ 10 ptsLet $A=\{a,b,c,d,e\}$. Suppose $R$ is an equivalence relation on $A$. Suppose also that $aRd$, $bRc$, $eRa$ and $cRe$. How many equivalence classes does $R$ have?
3. Permutations with order dividing twelve ●●○○○ 20 ptsLet $A=\{1,2,\dots,6\}$ and let $f: A \to A$ be a one-to-one mapping. Define $f^{(2)}(x)=f(f(x))$ and $f^{(n+1)}(x)=f(f^{(n)}(x))$ for $n \ge 1$. Find the number of mappings $f$ such that $f^{(12)}(x)=x$ for every $x \in A$.
4. Subsets contained in neither of two sets ●●○○○ 20 ptsFind the number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ that are subsets of neither $\{1, 2, 3, 4, 5\}$ nor $\{4, 5, 6, 7, 8\}$.
5. Sizes of two sets from subset counts ●●○○○ 20 ptsLet $A$ and $B$ be two finite sets. The number of subsets of $A$ minus the number of subsets of $B$ is $112$. Find the number of elements in $A$ and in $B$.
6. Value missing from range of a Möbius function ●●●○○ 50 ptsThe function $f$ is defined by $f(x)= \frac{ax+b}{cx+d}$, where $a$, $b$, $c$ and $d$ are nonzero real numbers. It has the properties $f(19)=19$, $f(97)=97$ and $f(f(x))=x$ for all $x$ except $-\frac{d}{c}$. Find the unique number that is not in the range of $f$.
7. Partition of a set with size conditions ●●●○○ 50 ptsLet $N$ be the number of ordered pairs of nonempty sets $\mathcal{A}$ and $\mathcal{B}$ such that $\mathcal{A} \cup \mathcal{B} = \{1,2,3,4,5,6,7,8,9,10,11,12\}$, $\mathcal{A} \cap \mathcal{B} = \emptyset$, the number of elements of $\mathcal{A}$ is not an element of $\mathcal{A}$, and the number of elements of $\mathcal{B}$ is not an element of $\mathcal{B}$. Find $N$.
8. Counting topologies on three points ●●●○○ 50 ptsLet $X$ be a set with $3$ elements. How many topologies can be defined on $X$? Equivalently, how many subsets of the power set $\mathcal{P}(X)$ are topologies on $X$?

More in Sets and Venn diagrams

Counting subsetsMinimum overlap of percentagesParameters from set conditionsThree setsTwo setsUnions and intersections