# Tag Info

## New answers tagged discrete-mathematics

1

Hint: Since $3$ and $7$ are (co)prime, find a Bézout's identity first: $$3u+7v=1$$ and multiply both sides by $69$. Next, you'll get all solutions using Euclid's lemma to show that, if $(x,y)$ is a solution, any other solution can be written as $$x'=x+7k,\quad y'=y-3k\qquad(k\in\mathbf Z).$$

0

then if $p=1,q=1$, from the truth table above, we can see $p \rightarrow q \equiv 1\text{ (row 3)}$. I don't follow what you are saying here. This is how I would extend your truth table to attack $\{[p \implies q] \iff [(\neg p) \vee q]\}$. \begin{array}{|c|c|c|c|} \hline p & q & p \vee q & (\neg p) \vee q \\ \hline 1 & 1 & 1 ... 0 There is a natural correspondence between relations on n objects and n×n binary matrices. A reflexive relation is a matrix with a diagonal of all ones and a symmetric relation is a symmetric matrix. 3^2-3 is the number of off-diagonal entries of the matrix for the 3-element case. If the relation is only constrained to be reflexive, they may be any ... 1 Yes, in fact bipartite is equivalent to 2-colorable. 0 For #1, note that \begin{align} a(x)b(x) &= \sum_{n \ge 0} x^n \sum_{k \ge 0} b_k x^k \\ &= \frac{1}{1-x}\sum_{k \ge 0} b_k x^k \\ &= \sum_{k \ge 0} b_k \frac{x^k}{1-x} \\ &= \sum_{k \ge 0} b_k \sum_{n \ge k} x^n \\ &= \sum_{n \ge 0} \left(\sum_{k=0}^n b_k\right)x^n, \end{align} so a(x)b(x) is the generating function of the partial ... 0 a^{5} \equiv a \pmod 5 \implies 5|(a^{5}-a)=a(a^{4}-1)\implies a(a^{4}-1)=5k% for some integer k. Since \gcd(a,5) =1, and by the uniqueness of prime factorizations, 5 is a prime factor of the LHS, but not a prime factor of a. Hence, 5 must be a prime factor of a^{4} -1 so that 5|(a^{4}-1) \implies a^{4} \equiv 1 \pmod 5. 0 E[X_1] = 3.5 E[X_k \mid X_{k-1}] = 3.5 X_{k-1} E[X_k] = E[E[X_k \mid X_{k-1}]] = E[3.5 X_{k-1}] = 3.5 E[X_{k-1}] E[X_n] = 3.5 E[X_{n-1}] = (3.5)^2 E[X_{n-2}] = \cdots 0 Based on the definition you provide, as you say, it just refers to the set of all logical variables appearing as subexpressions of \varphi. Assuming this is like propositional logic, if we have \varphi = P \implies Q where P and Q are logical variables, then var(\varphi) = \{ P,Q\}. 0 The first seven values are \begin{array}{r|r|r} n & g(n) &2^{2^{f(n)}}\\ \hline 1 & 1. & 16. \\ 2 & 2. & 6.8\times 10^{12} \\ 3 & 5. & 1.02\times 10^{512} \\ 4 & 29. & 1.6\times 10^{78913} \\ 5 & 866. & 9.6\times 10^{47586437} \\ 6 & 750797. & 2.9\times 10^{112995071916} \\ 7 & 5.63697\...

0

Even after editing your question and it's sentence structure, wording, spelling, and code. I still don't understand what you're actually asking for? Are you trying to ask for us to prove why it's O(log n) and what line of code from your example indicates O(log n)? Regardless, if that's what you're asking, here's why this would be O(log n) (considering that ...

0

On the set of all people set $(x,y) \in R$ if $x$ is the parent of $y$. Then for any two people $x$ and $y$ it is not possible that $x$ is the parent of $y$ and that $y$ is the parent of $x$. Therefore the implication $$(x,y) \in R \quad\text{and}\quad (y,x) \in R \implies x=y$$ is vacuously true so $R$ is antisymmetric.

0

Take the set of all floors from a building. If $f_1$ and $f_2$ are floors, consider$$f_1\mathrel Af_2\quad\text{if}\quad\text{f_1 is above than or equal to f_2}.$$Then $A$ is an antisymmetric relation.

0

The three most common elementary ones in my experience are: Subset relation, like for geometric locus results Real number inequalities Divisibility of positive integers These are all applicable in real life as long as the mathematical concepts model what you are looking at.

1

Alternative approach. ABCDEFAG Imagine each element is a building block. So normally, there are $\binom{8}{4}$ ways of choosing 4 of the 8 blocks. When you outlaw having more than 1 A, the physical effect is equivalent to taking the two A blocks and gluing them together, so that you can't use them separately. Now you only have 7 blocks, so the number of ...

1

See the answer is in question itself. The question says 'duplicates' so the two A's are identical. And if we have to choose different letters, we can eliminate the duplicates and find the no. of ways just like you did in the first method.

2

First way should be the correct one. Note that in your second way, when we say $8 \choose 4$, we consider two $A$'s different. But normally, total number of ways of choosing $4$ out of $8$ letters with duplicates should be $${6 \choose 4}+{6 \choose 3}+{6 \choose 2} = 50$$ where ${6 \choose 4}$ is the number of choices where we don't choose any $A$'s, ${6 \... 0 A partition is a grouping of elements of a set, i.e. a collection of subsets of$X$, such that every element of$X$is included exactly once (the subsets are disjoint, and their union is all$X$). If you have a partition of$X$you can define an equivalence relation on it by identifying elements in the same "partition set", but that is just a ... 1 Here is a depiction of the$5$-stair graph. Each non-space character is a vertex and there is an edge between and only between adjacent characters: e xo xoo xooo eoooo Clearly, any Hamiltonian path must start and end at the es, which are only of degree$1$. The path must also pass through the x vertices on the diagonal; since they are degree$2$... 2 Think of a binary string of length n as a (row) vector of n components. That is, regard "110101" as the vector$(1,1,0,1,0,1)$. Now take an$n\times n$matrix$A$consisting of 0's and 1's whose determinant is an odd number. Using this we can construct a bijection$f:S\to S$by the following method:$ f(x) = xA\pmod 2$here$xAmeans multiplying ... 1 Hint: Show that 𝐺 has a vertex with degree at most 4 . First try contradiction. If all vertices of G are of at least 5 degree, by handshake lemma and |𝐸|≤3|𝑉|−6, we know that it requires |V|=12, |E|=30, and G to be a 5-regular graph. Except this case, it's not possible for all vertices of G to have at least 5 degree, so for other cases, G has at least a ... 3 An algebraic variation mimicking @BrianMScott's nice combinatorial proof. We obtain \begin{align*} \color{blue}{\sum_{1\leq i\leq j\leq n}(j-i)}&=\sum_{1\leq i<j\leq n}(j-i)\\ &=\sum_{1\leq i<j\leq n}\sum_{k=i+1}^j 1\\ &=\sum_{1\leq i<k\leq j\leq n}1\\ &=\sum_{1\leq i<k<j<n+1}1\\ &\,\,\color{blue}{=\binom{n+1}{3}} \end{... 0 $$\displaystyle\sum_{j=1}^n\displaystyle\sum_{i=1}^j(j-i)= \displaystyle\sum_{j=1}^n\bigl(\left( \displaystyle\sum_{i=1}^jj \right)-\left(\displaystyle\sum_{i=1}^j i \right)\bigr)= \displaystyle\sum_{j=1}^n\bigl(\left( j\displaystyle\sum_{i=1}^j1 \right)-\left(\frac{j(j+1)}{2} \right)\bigr)\\ =\displaystyle\sum_{j=1}^n\bigl(j^2-\frac{j(j+1)}{2} \bigr)=\... 1 hope this procedure be clear enough for you$$\displaystyle\sum_{j=1}^n\displaystyle\sum_{i=1}^j(j-i) = \displaystyle\sum_{j=1}^n\displaystyle\left(\sum_{i=1}^j(j)-\sum_{i=1}^j(i)\right)=\displaystyle\sum_{j=1}^n\displaystyle \left(j^2-\frac{j^2+j}{2}\right)=\displaystyle\sum_{j=1}^n\displaystyle \left(\frac{j^2-j}{2}\right) = \frac{1}{2}\left(\... 4 You can reduce it to a single summation by splitting the region into diagonals. Forn=4$for instance, we’re adding up the entries in the following partial matrix: $$\left[\begin{array}{ccc} 0&1&2&3\\ &0&1&2\\ &&0&1\\ &&&0 \end{array}\right]$$ If the main diagonal is the$0$-th diagonal, then the$i$-th ... 0 $$\begin{array}{rcl} z^k \in \text{Palindrome} &\implies& z^k = \text{rev}(z^k) \\ &\implies& z^k{}_1 = z^k{}_{kn}~,~z^k{}_2 = z^k{}_{kn-1}~,~z^k{}_3 = z^k{}_{kn-2}~,~\dots \\ &\implies& z_1 = z_n~,~z_2 = z_{n-1}~,~z_3 = z_{n-2}~,~\dots \\ &\implies& z \in \text{Palindrome} \end{array}$$ Third line follows from$z^k{}_{a} = z_{...

1

Note that the degree of a chromatic polynomial $n = |V(G)|$ and the coefficient of $r^{n-1} = -|E(G)|$. With these facts, one can find graphs with 1, 2, 3, and 6 as their chromatic polynomial fairly quickly due to their nice form. For example $K_3$ and a singleton. (The chromatic polynomial is the product of the chromatic polynomial of each component.) $K_3$...

1

If $n \ge 8$ you are told that $3$ is in $A$ and $5,8$ are not. How many binary choices does that leave you? If $n \lt 3$ you cannot satisfy the requirement that $3$ be in $A$, so there are none. How about the range from $3$ to $7$?

2

The question seems incorrectly stated, for example if you take $x=1$ there is no $n$ such that $1/2^n > x$, you probably meant $<$. For that problem, for every $x>0$ show that there exist an $n \in \mathbb{N}$ such that $\frac{1}{2^n} < x$, we need to find an $n$ such that $\frac{1}{2^n}$ is as small as we like. Turning it around, given $x >0$ ...

4

Assume $G$ is not complete. Then there are vertices $x,y$ not joined by an edge. Consider a colouring of $G-x-y$ with $m=\chi(G-x-y)$ colours. Then by assigning a new $(m+1)$st colour to $x$ and $y$, we obtain a valid colouring of $G$ and conclude that $$\chi(G)\le \chi(G-x-y)+1.$$

1

Let's say $S_{t,u}$ is the number of binary $n$ by $n$ matrices with $t$ rows of zeroes and $u$ columns of zeroes. The rows can be chosen in $C(n,t)$ ways and the columns can be chosen in $C(n,u)$ ways. The remaining portion of the matrix has $(n-t)(n-u)$ binary elements. So $$S_{t,u} = C(n,t)C(n,u)2^{(n-t)(n-u)}$$ (Note that this formula works even when $t=... 0 Solve$x^2+5x+6 \equiv (x+2)(x+3) \pmod {187}$. Besides the two 'in your face' solutions,$x \equiv -2 \pmod{187}$and$x \equiv -3 \pmod{187}$, we can buttress the argument given by José Carlos Santos to find all four solutions. We want to find integers$x, k, j$satifying$\;\text{L1:}\quad x + 2 = 11k\;\text{L2:}\quad x + 3 = 17j$Subtracting$\text{L1}...

1

Remember from your last question that, intuitively, random variables are independent exactly when information about one doesn't help you predict the outcome of the other. A classic example is a dice roll and a coin toss. Knowing you rolled a $4$ doesn't tell you if you're about to flip a heads. So saying that $X_1 + X_2$ is not independent of $X_1 + X_2 \... 1 A simple argument proves the statement. Essentially, it proves explicitly that$\text{rev}(z^n) = (\text{rev}(z))^n$(if you assume it, there is nothing to prove). Before showing the argument, some preliminaries. Any word can be written as$z = z_1 \dots z_k$, where$k \geq 0$is the length of$z$and the$z_i$'s are single characters of any alphabet$E$. A ... 0 This is known as the "cauchy product", and as far as I know it is the only way to do it. However, it's not as complicated as it looks. The$n$th coefficient of$x^n$in$AB$is$\displaystyle \sum_{i+j=n} a_i b_j$. That is $$a_0b_n + a_1b_{n-1} + \ldots + a_{n-1}b_1 + a_nb_0$$ Notice each product sums to$n$:$a_0 b_n$is$0+n = na_1 b_{n-1}$... 2 Welcome to MSE! Remember the intuitive idea of a random variable: It simply chooses some real number$r$according to a probability distribution. Consider the random variable$X$which takes values in$\{1,\ldots,6\}$based on the roll of a dice. Consider also the random variable$Y$which takes values in$\{0,1\}$based on the flip of a coin. Then we can ... 0 The main question here is, why$4$cases in the basic step. @Angelo Randina's answer explains this. I will, here, try to explain the problem that will arise if we don't do the 4 base cases. Basic Step:$P(12) = 4\times 3$or four stamps of 3 cents Inductive Step: Now, since we have only done the basic step for$P(12)$, we will have to let$12\le k$instead ... 0 Idea: Using division, any$p\ge3$satisfies$p=4k, p=4k+1, p=4k+2$, or$p=4k+3$. But if$p=4k$or$p=4k+2$, then$p$is divisible by$2$. 3 What you need is $$4(k+1)-2=4k+2=2(2k+1)=\dfrac{2(2k+1)(2k+2)}{2(k+1)}=\dfrac{(2k+1)(2k+2)}{k+1}.$$ Can you take it from here? 1 Somehow I've never come across relation composition before! Anyway, this should work. Let$A = \{a, b, c\}$. Let$R$equate$a, b$and leave$c$alone. Let$S$equate$b, c$and leave$a$alone. Then$aRSc$but we don't have$aSRc$. Let me know if I misunderstood the definition and I'll edit or delete my post. 1$\mathbb{Z}/2 \times \mathbb{Z}/8$is not cyclic, so it needs at least$2$generators to get the whole group. So if you take the "cycle graph" as you've defined it, you will not get a cayley graph at all. If instead you take the cayley graph with two generators (one of$\mathbb{Z}/8$and one of$\mathbb{Z}/2$) you'll find you do get the product of ... 0 First let us get rid of the non-homogeneous member$9n2^{n-1}$. For this look for a solution of a recurrence which has a form$f_1(n)=(an+b)2^{n-1}$. It is easy to see that we can pick$a=\tfrac 9{19}$and$b=a^2$. Then a general solution of the recurrence is a sum of$f_1$and a general solution of a recurrence$g(n+1)=9g(n)+5g(n-1)$. The latter is a ... 0 Hint: if every vertex has degree$2$, your graph is the union of disjoint cycles. 1 If you introduce a nonnegative integer slack variable$y_6$so that you get four equalities in$y$, you obtain the correct count of $$\sum_{k=6}^9 \binom{k+4}{4}=1750$$ Alternatively, count the number of nonnegative integer solutions to $$\sum_{j=1}^6 y_j = 9$$ and subtract the ones that have$y_5 \ge 4$: $$\sum_{j=1}^6 y_j = 5$$ This approach yields$$\... 1 Here is one approach which may or may not be what you're looking for: Choose an arbitrary binary string to be the key. Then bit-wise xor with the key is a bijection. More concretely, take a binary string$x$, and flip all the bits where the corresponding entry of the key is a 1. For instance, if$n=3$and the key is$101$, then this bijection is "flip ... 1 What's wrong with$10 \times 9 \times 8$is that you take the order of the people chosen into account. Say you're counting$ABC$and$ACB$as different objects. That's the number of permutations of picking three objects from ten objects. To count the number of combinations$C_3^{10}$instead of$P_3^{10}$, we have to divide the number of permutations$P_3^...

0

The reason for this is because if you have say A,B,C,D and you were to choose 2 then you can do this by selecting first one letter. For example A, with a there are 3 different combinations: AB, AC, AD. After A we can ignore A and move onto B since every letter has already been taken out with A. With B we have: BC, BD. Lastly, since we are ignoring A and B ...

1

You pick the first letter the second letter the third letter the fourth letter the fifth letter the sixth letter the one and only digit the position of the one and only digit

1

The quantity $26^6\cdot 10$ tells you a) how to pick the $6$ letters in order, and b) how to pick the one digit, but it doesn't tell you where the digit goes in the string. For example, you're not classifying the strings "8aabaea" and "aa8baea" as different. What do you need to change?

-1

I'd start with considering that is $h$ is not one to one considering the $x\ne y$ so that $h(x) = h(y)$ and see what happens. $g$ is onto so there are $a,\alpha \in A$ so that $g(a) = x$ and $g(\alpha) = y$. And.... well, seems the obvious thing to try is to $h(g(a)) = h(x)$ while $h(g(\alpha) = h(y) = h(x)$. So if $a \ne \alpha$ then $h\circ g$ is not one-...

4

Since $h$ is not one to one, there is $b_1, b_2 \in B$ distinct such that $h(b_1) = h(b_2)$. Since $g$ is onto, there is $a_1, a_2 \in A$ such that $g(a_1) = b_1$ and $g(a_2) = b_2$. Then notice that $h(g(a_1)) = h(b_1) = h(b_2) = h(g(a_2))$. So then $h\circ g$ is not one to one.

Top 50 recent answers are included