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.

learn more… | top users | synonyms

0
votes
2answers
18 views

Proving a relation is anti-symmetric and transitive

$P$ is a binary relation. $P ⊆ \mathbb{R}^2$. $P = \{(x,y): y = |x|\}$. As I understand for relation to be transitive: $(a,b) \in P$ and $(b,c) \in P$ then $(a,c \in P)$ for this particular relation ...
0
votes
1answer
41 views

Find the middle term in the expansion of $\left(x^2 - \frac{7}{x^3}\right)^{18}$

Find the middle term in the expansion of $\displaystyle \bigg (x^2-\frac{7}{x^3}\bigg)^{18}$. $k=4 , n=18$ $=\sum^{18}_{k=0}$$ (^{18}_k).(x^2)^{18-k}.(\frac{7}{x^{3}})^{k}$ $=(^{18}_4).(x^...
1
vote
2answers
14 views

Partial order relation aRb is true when b contains a, 001R0101 is true - why?

Note: I'm taking a course in Polish, where the word "ciąg" is used, which translates to "sequence", but may be translated as a "word" or a "string". We have a set of binary sequences: ...
1
vote
2answers
57 views

True or False: $A\cap (B\times C)=(A\cap B)\times (A\cap C)$

True or false. Prove by showing the statement is true in general or by giving a counter example. $A\cap (B\times C)=(A\cap B)\times (A\cap C)$ I'm not sure what the question is trying to get at. ...
2
votes
1answer
52 views

“Exactly one person” quantifier [closed]

How do I translate the following English sentences without Uniqueness Quantifier: There is exactly one person who hates everyone All people hates exactly one person.
0
votes
1answer
35 views

Four color theorem and five color theorem

Every graph whose chromatic number is more than ____ is not planner. My attempt: The answer should be $4$ by four color theorem. Somewhere, I read "Five color theorem"(See Theorem 6.3.8 at ...
0
votes
1answer
35 views

First order predicate logic for “Every bike is a two wheeler manufactured by Hero”.

Let $A(x)=x$ is a two wheeler $B(x)=x$ is a bike $C(x)=x$ is manufactured by hero. Which of the following is first order predicate logic for statement Every bike is a two wheeler manufactured ...
6
votes
2answers
60 views

optimize pasting text

Someone asked me how can he paste a string 1000 times in Windows notepad. While this can be done easily using editors like Vi, I'm trying to answer his question using notepad only. So the problem goes ...
-4
votes
2answers
40 views

algebra and discrete mathematics prove [closed]

I am trying to solve this question but it's bit confusing. Can someone please help me with this question? (a) Prove the following either by direct proof or by contraposition: Let $a \in \mathbb{Z}$, ...
-1
votes
1answer
41 views

Using the laws of logic (algebraic version) to show the following equivalences [closed]

I have some questions about algebra and discrete, with using law of logic. I am not sure how to prove the equivalences. Can someone please show me how this works and show the equivalence using the ...
-1
votes
0answers
11 views

Integrate Beta and Normal CDF mixture

Is it possible to integrate the following integral? $\int_0^1 y^{m-1}(1-y)^{n-1}\Phi\left(\Phi^{-1}(y)+\mu\right)dy$, where $m, n, \mu$ are constants and $\Phi(.)$ is the normal CDF Thank you
1
vote
1answer
61 views

Number of integer solutions to $a_1\ge a_2\ge\ldots\ge a_i\gt 0$ such that $a_1+a_2+\ldots+a_i=n$ [duplicate]

What is the number of (positive) integer solutions of: $$a_1+a_2+\ldots+a_i=n$$ where $a_1 \ge a_2 \ge \ldots\ge a_i\gt 0$ ? Also, the order of summands does not matter.
2
votes
1answer
51 views

How can I prove that $(a + b )\oplus(a + c)$ is not possible to simplify. Or is it?

I was trying to simplify the following expression $(a + b )\oplus(a + c)$, where $+$ is just a simple addition of two numbers and $\oplus$ is a binary xor operation. By simplifying I mean exanding or ...
1
vote
1answer
36 views

Using generating function to solve initial value problems

I have a hard exam coming up and something I've struggled with since week 1 of semester is initial value problems. How would I go about solving: (a) $u_{n} - 7u_{n-1} = 3 * 7^n : u_0 = 4 $ (b) $u_{n}...
0
votes
0answers
31 views

Finding a general solution of recurrences

I am unsure how to even start the questions :S I need to learn this stuff for the final exam of my subject and its hard to find a tutorial on how to answer this type of question.
2
votes
2answers
27 views

Logic Puzzle (Valid and Invalid Arguments)

I have been given a logic puzzle and I am having a tough time figuring out how to set it up and solve. Here is the puzzle: a) The Statement "If Dr. Jones did not commit the murder then neither Ms. ...
0
votes
1answer
52 views

How many integer numbers from 0 to 100000 contain 2 or more digits 5?

How many integer numbers from 0 to 100000 contain 2 or more digits 5? I know that I need to apply some kind of formula to this problem, but I can't choose which one. Can you please help me?
0
votes
2answers
32 views

How to simplify this logical expression?

Using logical laws, I would like to simplify the following expression: $\neg a \lor \neg b \lor (a \wedge b \wedge \neg c)$ 1) Distribution law: $(\neg a \lor a) \land (\neg a \lor b) \land (\neg ...
-1
votes
1answer
21 views

Discrete Maths Relations on the set {1,2,3,4}

I just want to make sure that I am doing these correctly. Here is what I have: Reflexive, symmetric, antisymmetric and transitive: And i have - {(1,1) (2,2) (3,3) (4,4)}. not Reflexive, not ...
1
vote
1answer
35 views

Find the range of the function $f(x) = 4x + 8$ for the given domain $D = \{-5, -1, 0, 6, 10\}$

The question is to find the range of each function for the given domain $f(x)=4x+8$, $D=\{-5, -1, 0,6, 10\}$. Is the range just $R= \{-12,4,8,32,48\}$ or am I mistaken? Could you elaborate why my ...
0
votes
1answer
20 views

non-homogeneous Recurrence Relation for f(x) = n^2

Im having some trouble with a non-homogeneous Recurrence Relation. My question is: $u_{n} - 5u_{n-1} + 4u_{n-2} = n^2$ My working out so far: $r^{2}-5r+4r = 0$ = (r-1)(r-4) Giving the roots 1 and ...
0
votes
2answers
62 views

Is $y \in\{f(x)\mid x \in X\} ⇔ f(x) \space ∃ x \in X$ true?

Definition 9 $f(A) =\{f (x) \mid x\in A\}$ The following is from the proof of $f(\bigcup_{\gamma \in \Gamma}A_{\gamma})$ = $\bigcup_{\gamma \in \Gamma}f(A_{\gamma})$. $$y \in f \left( \bigcup_{\...
0
votes
1answer
65 views

What does ± times ± equal? [closed]

What does ± times ± equal as we know that - * - = + and + * + = + ? I'm sorry for this layman question I'm purely curious. Thanks.
0
votes
3answers
39 views

How many numbers of $7$ digits can be formed with the digit $0,1,1,5,6,6,6$.

How many numbers of $7$ digits can be formed with the digit $0,1,1,5,6,6,6$. My attempt: Seventh place, total number of possibility is $=\frac{6!}{2!\times 3!}=60$ ways. Sixth place, total ...
0
votes
0answers
26 views

Simplifying logical expression using logical laws

I simplified the logical expression: $(z \land w) \lor (\lnot z \land w) \lor (z \land \lnot w)$ using logical laws following these steps: 1) Absorption Law: $(z \land w) \lor (\lnot z \land w)$ ...
1
vote
2answers
44 views

In how many ways can $5$ students and $3$ teacher sit around a table so that no two teachers are together?

In how many ways can $5$ students and $3$ teacher sit around a table so that no two teachers are together? My attempt: $5$ student can sit $(5-1)!$ in round table. A teacher can sit between two ...
2
votes
1answer
29 views

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$.

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$. My attempt: Divisible by $5$ is possible only when ...
5
votes
1answer
65 views

number of ways to partition an integer.

A partition of a positive integer n is a way of writingn as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 ...
0
votes
1answer
16 views

Can you denote a family $F: N → P(R)$ such that $F(n) = R\space, ∀n ∈ N$ in a set builder notation?

I don't fully understand the meaning of the following underlined explanation. Can you denote $F: N → P(R)$ such that $F(n) = R\space, ∀n ∈ N$ in a set builder notation? Definition A family of ...
0
votes
0answers
40 views

Prove by contradiction that any sequence of five distinct integers must contain a 3-chain.

Define a $3$-chain to be a (not necessarily contiguous) subsequence of three integers, which is either monotonically increasing or monotonically decreasing. We will show here that any sequence of five ...
-2
votes
0answers
15 views

Formal Specification - discrete math for Stack

I need to define a series of Abstract Data Types (ADT) using discrete mathematics for a Formal Specification. For example, to define Empty of a Set ADT I would do the following ...
0
votes
0answers
34 views

Decrease distance between max and min

Let $a:=(a_1,a_2,\ldots,a_n) \in \mathbb{Z}^n $ and $k \in \mathbb{N}^*$, with $$f: \begin{cases} \hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\ \hfill ((a_1,a_2,\...
0
votes
0answers
16 views

Finding δ(s,v) for all v∈V , when given zero weighted cycle edges- in linear time

Formally: Let it be $G=(V,E)$ directed graph with a weight function $w: E -> R $. Let it be $s∈V$ (source vertex). For all $e∈E$ so that $e$ belongs to a cycle in G, $w(e)=0$ (if $e$ doesn't ...
0
votes
1answer
47 views

How to know the contrapositive of a compound logical expression?

In simple expressions like: $p \implies q $ the contrapositive would be: $\lnot q \implies \lnot p$. But in other cases where the expression gets more complex: ($p \land q) \implies (\lnot q \lor p)$. ...
0
votes
2answers
38 views

Lattices and Boolean algebra

I have read in a text book that the set of natural numbers form a lattice under divisibility. How can it possibe, since there is no upper bound and therefore a Sup of the set?
2
votes
2answers
41 views

The existence of a cycle in a graph

Let $C$ and $D$ be different cycles in the graph $G$, and $e$ a common edge of cycles $C$ and $D$. Show that $G$ contains a cycle not passing through the $e$. I think, it's not easy task, because ...
1
vote
2answers
10 views

Find total number of relations that are equivalence as well as partial order set

Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements. My attempt: As equivalence relation has property reflexive, symmetric and ...
2
votes
4answers
76 views

Recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, then find $a_{20}$

Consider the recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, given that $a_0=0, a_1=1$. Let $a_{20}=x\times10^9$, then the value of $x$ is______ . My attempt: $a_r=3-6a_{r-1}-9a_{r-2}$ I ...
1
vote
0answers
37 views

In how many ways consonants and vowels alternatively for letters of word `CONSTITUTION`. [closed]

In how many ways consonants and vowels alternatively for letters of word CONSTITUTION. My attempt: The word 'CONSTITUTION' has 7 consonants (C N S T T T N) ...
0
votes
0answers
15 views

Partition of set [list]

i have a question that: "List all the partition of set {1,2,3,4}" i have solved this using the definition: "A partition of a set S is a collection of disjoint non empty subsets of S that have S as ...
1
vote
1answer
34 views

generating function for $0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,\dotsc$

I know that the generating functions is $$x + x^4 + x^7 + x^{10} +\dotsb$$ and then we can factor out a $x$ to get $$x(1+(x^3) + (x^3)^2 + (x^3)^3 + \dotsb )$$ Now I need my answer in closed form ...
0
votes
1answer
40 views

What is the order of

What is the order of the following: $$\frac{(33x^{7}+6)(x^{2}+3)}{\sqrt{x^3+7x^2-x+5}}$$ Would it be $$\Theta (x^{\frac{17}{2}})$$
3
votes
1answer
173 views

Question about regular languages

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?
1
vote
1answer
28 views

Minimum length $m$ of $n$ string with pairwise Hamming distance $m/2$

I want to construct $n$ binary strings, each of the same length $m$ (to be determined), such that each pair of string has Hamming distance exactly $m/2$ (i.e. the strings disagree on $m/2$ positions). ...
1
vote
1answer
9 views

Deduce the Conclusion for the Premises

I have done this problem over 20 times now and am officially stumped. The instructions are Deduce the conclusion for the premises, giving a reason using the rule of inferences for each step. a) p -> ...
0
votes
0answers
23 views

Where can I find the demonstration of $\sum_{j=0}^J \Delta x f(x_j) \to \int_0^1 f(x) dx$?

Let $x \in \left[0, 1\right]$. Define a partition $x_j = j \Delta x$ with $j=1,\ldots, J$ and $J\Delta x = 1$. Then, $\Delta x = \frac{1}{J}$. I can't find the demonstration of \begin{equation} \...
3
votes
0answers
24 views

Proving Logical equivalence [5-26]

I have to prove a problem statement with logical equivalences but I seem to keep getting stuck. Here is the problem: $$ [(q \to p) \land \lnot p] \to (p \land q) \equiv p \lor q $$ Here is the work I ...
1
vote
1answer
15 views

Proving Logic statement

So I have an statement that I need to prove using Logical Equivalences: $$(p\land q) \lor [p \land (\lnot( \lnot p \lor q)) ] \equiv p $$ I made it through some steps but I can't seem to make it to ...
0
votes
0answers
39 views

Relations on equivalence classes

To be short, I will abstract a bit from my particular problem. Let $S$ be a set and $\sim$ be an equivalence relation, defined on that set. Let $R \subseteq (S/\sim) \times (S/\sim)$ be a relation ...
0
votes
0answers
20 views

How do I calculate such possible number of total and serial schedule?

Consider the following two transactions $T_1$ and $T_2:$ How many non serial schedules are possible, if we execute both transactions concurrently? $3000$ $3001$ $3002$ $3003$ My try: ...