# Tagged Questions

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

30 views

### Proof of R is transitive if and only if $R^{-1}$ is transitive.

Question:Let R be a realation in a set X. Prove that $R$ is transitive if and if only if $R^{-1}$ is transitive. My proof $R$ is transitive ≡ [(x, y)∈R∧(y, z)∈R⇒(x, z)∈R] by the def. of a ...
37 views

59 views

### how to generate parity check matrix for a non-systematic generator matrix?

Introduction: Suppose $C$ is an $\left [ n,k \right ]$ code. Let $I_{k}$ be the $k\times k$ identity matrix. Let $P$ be a $k\times \left (n-k \right )$ matrix. Then, $\left ( I_{k} | P\right )$ is ...
50 views

### Prove that $\{(a, a), (b, b), (c, c), (a, b), (b, a), (c, a), (a, c)\}$ is reflexive and symmetric but not transitive.

Question: Let $A=\{a, b, c\}$ and let $R=\{(a, a), (b, b), (c, c), (a, b), (b, a), (c, a), (a, c)\}$. Prove that $R$ is reflexive and symmetric but not transitive. I checked that the relation $R$ is ...
29 views

### If $f(n) = \Theta(n^{\log_b{a}}\lg^k{n})$ where $k \ge 0$ , then the master recurrence has solution $T(n) = \Theta(n^{\log_b{a}}\lg^{k+1}n)$.

I'm working through problems to the book "introduction to algorithms". I'm going through the section on the master recurrence and have been running into some roadblocks. I found a solution to the ...
217 views

### Extremly simple combinatorics - divide to groups

We have a group of $10$ men and $4$ women, we want to divide this group into two groups of $7$ such that each of those groups has at least $1$ woman. What I did: I actually solved this in two ...
### (i) Show that the drawings in Fig. $1.4$ represent the same graph. (ii) Find the group of automorphisms of the graph in Fig. $1.4$.
From A Course in Combinatorics by van Lint, Wilson: Problem $1A$: (i) Show that the drawings in Fig. $1.4$ represent the same graph (or isomorphic graphs). (ii) Find the group of automorphisms of ...