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

2
votes
1answer
44 views

Could Master Theorem be applied to this recurrence relation?

I have the following recurrence relation $T(n) = 4T(\frac{n+4}{2}) + n$ Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ...
0
votes
1answer
18 views

Nested Quantifiers (And vs Implies)

I would like to understand something regarding the nested quantifiers in discrete math. In the following question part (c): Let $M(x,y)$ be "$x$ has sent $y$ an e-mail message", and $T(x,y)$ be "$...
0
votes
0answers
30 views

Probability // Dice problem [duplicate]

I couldn't figure out the solution of it. Assume we are tossing a fair dice 3 times. Describe the probability space related to this experiment and calculate the probability that we have tossed ...
1
vote
1answer
23 views

Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
3
votes
1answer
48 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
0
votes
3answers
42 views

Comparing the cardinality of (0,1) and (0,1] [duplicate]

Question Consider the intervals of real numbers (0,1) = {x | 0 < x < 1} and (0,1] = {x | 0 < x ≤ 1}. Show that |(0,1)| = |(0,1]| Work I stated that since both intervals are uncountably ...
0
votes
1answer
39 views

Showing the convergence of a difference equation?

Suppose I have some variable $x_t$ which is the value of $x$ at time step $t$. Now, half the time I update it by adding $0.05$ and the other half of the time I update it by multiplying it by $0.95$. ...
0
votes
0answers
18 views

Find the classes of $L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ and $L_2=\{wxw^R|w,x\in(0,1)\}$

$L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ $L_2=\{wxw^R|w,x\in(0,1)\}$ My attempt: $L_2$ seems regular since it's finite. $L_1$ is DCFL since we can identify strings of $L_1$ using single stack, first we ...
0
votes
0answers
17 views

What is union of $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$

$L=L_1^+\cup L_2^*$ Where, $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$ My attempt: $L=L_1^+\cup L_2^*$ $L=(CSL)^+\cup (CSL)^*=CSL \cup CSL =...
0
votes
1answer
24 views

Subset of regular language $a^*$

Given $L\subseteq a^*$, then $L$ is definitely decidable $L$ is definitely Turing – recognizable $L$ may not be Turing – recognizable. $L$ is regular My attempt: $L$ may not be regular, ...
0
votes
0answers
21 views

First Intersection Of Periodically Repeating Intervals

I have a set of coupled tasks, let's say $M$ of them. The $ith$ coupled task is represented as the following 3-tuple $\{A_i,D_i,B_i\}$ where $A_i$ represents the time it takes to perform the first ...
0
votes
0answers
27 views

Complexity of some contact circuit

How to prove that for every boolean function $f$ of $n$ variables there exists a (1, 2)-contact circuit $\Sigma_f$ (i.e. with one input and two outputs), implementing boolean function system $(f, \...
2
votes
2answers
39 views

Number of possible routes through n countries and 2n cities, with restrictions

Someone is planning a round-the-world trip that involves visiting $2n$ cities, with two cities from each of $n$ different countries. He can choose a city to start and end the journey in, with ...
0
votes
3answers
58 views

Number of Surjective functions. How does $2! S(r, 2) = 2^r−2$ for $|A| = r, |B| = 2$ where $r \ge 2$?

Currently prepping for a Discrete Mathematics exam and stumbled across a question from last year's exam: Suppose that $|A|= r$ and $|B|=2$, where $r \geq 2$ . Find all values of $r$ for which the ...
0
votes
6answers
70 views

Is the following function bijective?

Is this function bijective? Bijective means both onto and 1 to 1 $$ F(x) = \frac{x^2+1}{x^2+2} $$ I'm not sure how to go about this. Edit: The domain is ${\rm I\!R}$
1
vote
1answer
35 views

Prove that $\lambda(f) = o(2^n)$ for almost all boolean functions

How to prove that $\lambda(f) = o(2^n)$ for almost all boolean functions $f$ of $n$ variables? Here $\lambda(f)$ denotes minimal length (i.e. count of terms) of all possible disjunctive normal forms (...
1
vote
0answers
24 views

Lower bound of DNF terms count for some symmetric boolean function

Consider boolean function $s_n^{[r,\,n - r]}\colon \{0,1\}^n\rightarrow\{0,1\}$ defined as follows: $$ s_n^{[r,\,n - r]}(x_1, ..., x_n) = 1 \iff |\{x_i: x_i = 1\}| \in [r,\,n - r] $$ (in other words,...
3
votes
3answers
139 views

Problem solving a word problem using a generating function

How many ways are there to hand out 24 cookies to 3 children so that they each get an even number, and they each get at least 2 and no more than 10? Use generating functions. So the first couple ...
5
votes
2answers
158 views

Confusion about event in a sample space.

I am a beginner in probability and counting. I am reading an open course by MIT. While reading the introductory chapter I am stuck in one conceptual doubt, if I understand correctly an event is the ...
1
vote
0answers
21 views

How to solve complicated floor function equations?

I have been thinking about solving equations involving several groups of floor functions. My research on solving floor function equations has only shown sums of individual floors, such as: $\lfloor ...
0
votes
1answer
21 views

How to write the formula in Disjunctive Normal Form (DNF)?

Formula is: $$\emptyset=((p \lor r)\to q)\land (q\to r)$$ This is what I've already done: $$(p \lor r) \lor \lnot q)\land (q \lor \lnot r)$$ $$(p \lor r \lor \lnot q)\land (q \lor \lnot r)$$ and ...
2
votes
1answer
35 views

Show that a 2k regular graph has a matching of size at least k-1

Let $H$ be a 2k-regular graph with $n=4k+1$ vertices (and thus $m=k(4k+1)$ edges). Show that $H$ has at least k-1 independent edges (or that there exists a matching of size at least k-1 in $H$). If ...
0
votes
1answer
29 views

Let $X$ denote an infinite set. Is every partitioning of $X^2$ induced by an associative operation $f:X^2 \rightarrow X$?

Proposition. Let $X$ denote an infinite set. Then for each partitioning $\Pi$ of $X$, there exists a function $f : X \rightarrow X$ whose coimage is $\Pi$. I'd like to know whether the analogous ...
1
vote
0answers
27 views

Constructing a bijection between two sets of pairs

I am working on a problem in a different area and the following problem appeared. Let numbers $j,k,l \in \mathbb{N}_0$ be fixed. I need to construct a bijection between the sets $$\{(A,B) \in \...
0
votes
1answer
49 views

Solving Chinese Remainder Theorem Algebraically

I am doing a practice problem for my final which asks: Solve the following Chinese Remainder Theorem: $$ x \equiv 2 \pmod{3}, \\ x \equiv 3 \pmod{5}, \\ x \equiv 5 \pmod{7}, \\ x \equiv 7 \pmod{11} \...
0
votes
0answers
20 views

Regular expression that defnes the set of all words

I'm trying to write a regular expression that defines the set of all words written in lower case characters and digits that contain a binary number. My idea: $(\varepsilon |[a-z]^{*})(\varepsilon |(...
0
votes
1answer
15 views

Regular expression that begins and ends with digit

I'm trying to write a regular expression that defines all words written in lower case characters and digits that begin with a digit, end with a digit and contain total of 4 digits. My idea is : $[0-...
1
vote
1answer
21 views

Is the hypercube graph $Q_n$ k-factorable for k=modn?

Definition of k-factorable graph: https://en.wikipedia.org/wiki/Graph_factorization I have proved that a hypercube of any dimension has a perfect matching, thus also a 1-factorization. Can it be ...
0
votes
0answers
38 views

Sticky boots and modular arithmetic: Find the formula!

Suppose a trek begins and on this trek the road is paved by squares with labels on them. The warning sign next to the beginning of the first square, labeled $1$, states: Beware that due to natural ...
0
votes
0answers
20 views

Prove that every maximal outerplanar graph has a 3-coloring

A maximal outerplanar graph is an outerplanar graph (which is a graph with a planar drawing with all vertices belonging in the outer face), where adding any edge would make it stop being outerplanar. ...
1
vote
1answer
64 views

Can we logically analyze mathematical theorems as if-then statements?

Many theorems in math have an if-then form. For example: "If a polynomial is of $n^{th}$ degree, then it has $n$ roots. In my other question, I learned that in order to analyze statements using truth ...
1
vote
1answer
78 views

Are standalone statements conventionally considered to imply truth?

From what I understand, the statement $\exists x(p(x) \vee q(x))$ in the English language sounds something like this: "There exists $x$ such that $p(x)$ or $q(x)$". But this sounds like an incomplete ...
0
votes
1answer
45 views

Regular language or not?

Let $L$ be a regular language over the alphabet $A=\{0, 1\}$. Is it true that the language of strings $0^n$, where binary representation of n $\in L$, is regular?
0
votes
0answers
9 views

Prove that for any PDA there is another PDA that accepts exactly the same language bu has only one POP state.

Prove that for any PDA there is another PDA that accepts exactly the same language but has only one POP state. My attempt: Let the counter example $L=\{wcw^R|w\in(a,b)^*\}$ and string of $L$ is $...
0
votes
1answer
11 views

Possible strings of Kleene star of $L = \{a^nb^n|n≥1\}$

Consider the following CFL. $L = \{a^nb^n|n≥1\}$ Then which of the following string can be accepted by the kleene star of the language. $aaabbb$ $aabbaaabbab$ $abbaab$ $λ$ My attempt: The ...
0
votes
1answer
13 views

Find the classes of given languages?

Consider the following statements $L_1 = \{wxw^R \mid w∈(a,b)^*, x∈c\}$ $L_2 = \{wy \mid w,y∈(a,b)^*\}$ $L_3 = \{zwz \mid w∈(a,b)^*,z∈\{a\}\}$ $L_4 = \{wxw \mid w∈(a,b)^*,x∈\{c\}^*\}$ Find the ...
0
votes
1answer
15 views

Is given statement decidable or undecidable?

A given non-terminal A in a given grammar CFG is ever used in the generation of word.-Decidable/undecidable? My attempt: It should be decidable problem, We can solve this problem using membership ...
0
votes
1answer
18 views

Definition of rational number in logical expression format

So I have to translate the following definition of rational number into logical expression. The real number r is rational if there exist integers p and q with q = 0 such that r = p/q. I have ...
0
votes
3answers
34 views

Are two relations equal if they are both equivalence relations

If R and S are both equivalence relations on a non empty set A, then does R=S? That was the question on my assignment, I think they are because equivalence relations have to be reflexive, symmetric ...
0
votes
3answers
74 views

Meaning of mathematical symbol $\pm$

What is the meaning of the $\pm$ symbol in relation to this expression? For example, the perceived area of a circle probably grows somewhat more slowly than actual (physical, measured) area: $$ \...
0
votes
1answer
16 views

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$?

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$? My attempt : Using pumping lemma $L=\{a^mb^n|m\neq n \space, m,n\...
3
votes
1answer
81 views

Find $\sum_{k=1}^n \binom{2n-k}{n}(-1)^k$

Is there closed form for $\sum_{k=1}^n \binom{2n-k}{n}(-1)^k$? I got above expression for a counting exercise. I wonder that it might have the closed form but I am not sure yet. Can anyone have any ...
1
vote
1answer
23 views

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true? $L_1\cup L_2$ is a ...
0
votes
2answers
17 views

Determine if the binary relation is reflexive, symmetric, anti-symmetric, or transitive.

Let $X$ be any set containing at least three distinct elements $a,b,c\in X$. Let $S$ be the relation on $\mathbb{P}(X)$ such that $(A,B)\in S$ when $A\cap B=\{a\}$. I'm not even sure how to write ...
0
votes
1answer
20 views

Is the complement of a symmetric relation symmetric?

My assignment asks us to prove or provide a counter example for If R is symmetric, then Rc is symmetric. I know that if R is symmetric, then (x,y) and (y,x) are both in R, but what I do not ...
1
vote
2answers
33 views

Correct order of the growth function [closed]

$5 \log( \log n) $ $n (\log n)^2$ $\sqrt{n} \log n$ $n^{\frac{4}{3}}$ $n \log (\log n)$ $7 \sqrt{n}$ What is the ascending order of the growth function? Please give the explanation as well.
0
votes
1answer
19 views

Help with set theory question about binary relations

On my assignment I was asked the question: Determine, with reason, if the binary relation is reflexive, symmetric, antisymmetric, or transitive. Let X be any set containing at least three distinct ...
0
votes
2answers
22 views

A regular expression that defines a language

I am reading a chapter about regular expressions and there is the following example present in the book : Let $\sum =\left \{ 0,1 \right \}$. Find regular expressions over $\sum$ that define the ...
0
votes
0answers
14 views

Proving Results Related to $R(3,3,3)$

I've been working on some problems in my introductory discrete mathematics course, and I am trying to figure out a proof that $R(3,3,3) \leq 17.$ I initially consider an instance where we have a $K_{...
6
votes
2answers
153 views

Is my understanding of Binary relations correct?

On my assignment it asks Determine with reason if the binary relation is reflexive, symmetric, antisymmetric or transitive. $$R = \{(a, b) \in \mathbb{Z} \times \mathbb{Z} \mid a \text{ is ...