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
0answers
175 views

warshall algorithm on excel

How can I implement the warshall algorithm on microsoft excel? What I need: -The user input the matrix R [Relation] -then user gets matrix R infinity matrix How is it possible? It is for an assignment....
0
votes
2answers
55 views

Question about proof for why every partial order on a nonempty finite set has a minimal element

The proof goes as follows: Proof. Let $R$ be a partial order on a set, $A$. For any element, $a ∈ A$, let $g(a)$ be the set of elements “less than or equal to $a$”, that is, $g(a)::=R\{a\}\cup\{a\}...
1
vote
1answer
38 views

Finding permutations recursively.See constraints below

Problem: Let $P(n)$ be the number of permutations of $m$ letters taken $n$ at a time with repetitions but no $3$ consecutive letters being the same. Find a recurrence relation connecting $P(n)$, $P(n-...
2
votes
2answers
57 views

100-level discrete maths, induction problem, prove $n^2 \ge 2n + 1$

I've just run into this problem, and was able to go as far, and understand the induction step up to the bolded section. The last part I found in the back of my book, italicized, I can't understand. ...
0
votes
1answer
64 views

First order logic expression of “Each finite state automaton has an equivalent push-down automaton”?

Problem is Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such ...
0
votes
2answers
38 views

Switching the order of summations.

Why is the below statement true? $$\sum_{j=0}^{n}\left(-\sum_{t=0}^{k}{{k+1}\choose {t}}j^t(-1)^{k+1-t}\right) = -\sum_{t=0}^{k}{{k+1}\choose {t}}(-1)^{k+1-t}\left(\sum_{j=0}^{n}j^t\right)$$ More ...
2
votes
5answers
475 views

How many $3$ integer subsets have no consecutive integers, where integers are less than $20$?

I have to determine how many integers between $1$ and $20$ are possible if no two consecutive integers are in a set. I've thought it has something to do with a combination of an element $(a,a+2,a+4)$ ...
0
votes
1answer
25 views

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways is that solution is correct ???
2
votes
3answers
95 views

Discrete Math logically equivalent?

Show that $$(p \land q) \lor (\lnot p \land \lnot q) \equiv p\leftrightarrow q$$ How would I go about doing this? Do I use a truth table or a more "algebraic" process?
-2
votes
1answer
50 views

discrete finite summation of non-linear functions

Does anyone have idea for dealing with the two following series summations $$ \sum_{i=1}^n \dfrac{1}{a+b x_i}=c $$ $$ \sum_{i=1}^n \dfrac{x_i}{a+b x_i}=d $$ I need to find the values of 'a' and 'b'...
3
votes
1answer
43 views

Let $p \neq \pm 1, 0$ be an integer. Prove that $p$ is prime iff for all $a \in \mathbb Z$, either $p \mid a$ or $(a, p) = 1$.

I'll try in $\to$ direction; Nothing divides the prime $p$ but $\pm1, \pm p$. If $a = \pm p$ or $a = \pm 1$ then $p \mid a$. Assume $p = 2$ . If $a$ is even, then $p \mid a$ and if $a$ is odd, then ...
1
vote
1answer
58 views

Hanging a painting with nails so that removing any subset of nails from a given collection makes painting fall, and subsets are minimal

So I'm aware of the result that for positive integers $k \leq n$ it's possible to hang a painting with $n$ nails, such that if any $k$ nails are removed then the painting falls, but never when $k-1$ ...
1
vote
2answers
41 views

Proof - Uniqueness part of unique factorization theorem

The uniqueness part of the unique factorization theorem for integers says that given any integer $n$, if $n=p_1p_2 \ldots p_r=q_1q_2 \ldots q_s$ for some positive integers $r$ and $s$ and prime ...
2
votes
1answer
290 views

Must the number of people at a party who do not know an odd number of other people be even

I have a homework question in my discrete mathematics class as the title shows, I feel the answer is no, but googling this question seem's to contradict my answer. Let me explain: So if they are ...
1
vote
4answers
47 views

X and Y be finite sets and f: X->Y be a function.

The option D is the correct option. But, I have a doubt since the inverse of function can exist or cannot exist, how can this option be true. How to approach these questions? Should we assume ...
0
votes
1answer
34 views

Is p|(q|r) is it equivalent to (q and r)

Using De Morgan's laws can I turn $p|(q|r)$ into: $(q \ and \ r)$ or does the and become an or, such as $(q \ or \ r)$ ?
1
vote
1answer
39 views

Finding the recurrence relation(with square roots) [closed]

I came across a very peculiar recurrence relation : $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)} $ And Initial Condition $T(0) = T(1)= 1$ Any helps on how to find it
2
votes
2answers
47 views

How many zero-sum $n$-tuples are there?

The question is extremely short and concise. How many $n$-tuples $X \in \{\, -1,0,1 \,\}^n$ have the zero-sum property $\sum_{x \in X} x = 0$ ? At the moment I have nothing to share of my own since ...
1
vote
0answers
25 views

Obtain cycles with $a < $ nr. of edges $< b$

I have a chemistry/mathematical problem and I would like to get your opinion. Imagine you are generating a planar, cyclic molecule, with a total $N$ is the number of atoms. By Euler graph theory, the ...
4
votes
3answers
65 views

Prove by contradiction $a,b,c>0$?

Suppose $a,b,c$ are real numbers such that $a+b+c>0$, $ab+bc+ca>0$, and $abc>0$. Prove by contradiction that $a,b,c>0$. I have tried to solving it case by case like: case $1$: $a,b,c<0$...
2
votes
1answer
90 views

Count the number of strings of length 8 over A = {w, x, y, z} that begins with either w or y and have at least one x

Count the number of strings of length $8$ over $A = \{w, x, y, z\}$ that begins with either $w$ or $y$ and have at least one $x$ So here is what I came up with..Can someone check my work? $A = \{w,x,...
-1
votes
1answer
64 views

Use induction to prove the following equation: $2 + 6 + 10 + \cdots + (4n − 2) = 2n^2$ where $n \ge 1$ [closed]

Use induction to prove the following equation: $2 + 6 + 10 + \cdots + (4n − 2) = 2n^2$ where $n \ge 1$
0
votes
1answer
80 views

DNF or CNF functions

The problem tells us to find the full DNF and CNF of the logic function $f(P, Q, R)$ = True if and only if either Q is True or R is False. I feel fine with converting to get the full DNF or CNF form, ...
1
vote
1answer
96 views

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T .

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T . I have no idea what this question is even asking me. What ...
-1
votes
1answer
50 views

Adding two variables with subscripts [closed]

What is the explanation to why $x_{3k} + x_{3k+1}$, is equal to $x_{3k+2}$. Isn't that incorrect because there is no value 1 in the subscript $x_{3k}$? I saw this in a prove in http://www2.math.ou....
1
vote
2answers
49 views

Find $a_i, b_i$ such that they are all distinct

Very tough, I spent at least an hour, not solving this! From the set of integers $ \{1,2,3,\ldots,2009\}$, choose $ k$ pairs $ \{a_i,b_i\}$ with $ a_i<b_i$ so that no two pairs have a common ...
2
votes
2answers
112 views

Statements with multiple quantifiers

Suppose $P(x,y)$ is a predicate whose truth depends on $x$ ($x\in D$) and $y$ ($y\in E$). In the following statement,does the order of assigning values to $x$ and $y$ matter? For example, assign some ...
0
votes
1answer
30 views

Name for $f(a,b) = c/d$

What is the a name for functions of the form $f(a_1/b_1,\ldots,a_n/b_n) = c/d$ where $a_1,\ldots,a_n,b_1,\ldots,b_n,c,d \in Z$ and all the denominators are not zero. I was thinking about calling ...
1
vote
2answers
111 views

How to find the amount of binary digits in a decimal number?

This seems like such a simple question but I can't seem to come up with an answer. I know the formula for the number of digits of $2^n$ is $1+[nlog(2)]$. So the amount of decimal digits of $2^{100}$ ...
1
vote
2answers
214 views

Subset vs. Proper subset

I'm a bit confused on the wording here.. For example: $$A = \{c, d, f, g\}$$ $$C = \{d, g\}$$ Is $C$ "subset" of $A$? Obviously, yes. But.. the proper subset states that: If $C$ and $A$ are any ...
1
vote
1answer
43 views

interpreting words as if-then statements

In my book it is stated the $P \rightarrow Q$ is used to interpret $P$ only if $Q$. So, in the statement "$x$ divides 4 only if $x$ divides 8" should the symbolic form not be $P: x \text{ divides }4$...
17
votes
5answers
3k views

How is an empty set truly “empty”?

In a related question, an answerer says: an empty bag is a bag with nothing inside it. Makes sense, but I'm reading a textbook right now that says: The empty set has only one subset (namely, ...
0
votes
1answer
100 views

Determine truth value of ∃x P(x , y) when P(x,y) is the proposition $x^2 = y$

Although this may be a simple question but I'm forgetting if this would be a false statement. So let $P(x,y)$ be the proposition $x^2 = y$, where $x$ and $y$ are integers. What would the truth ...
0
votes
1answer
162 views

The complete bipartite graph K2,5 is planar [closed]

I wonder why The complete bipartite graph K2,5 is planar?
2
votes
1answer
58 views

Finding the smallest number a such that $a! > 3^a$ for the naturnal number $n$ in statement $n! > 3^n$

I'm doing discrete maths as a subject at my uni and I've been asked to solve the following equation, yet I'm having trouble understanding both what it's asking me to do and how I need to go about ...
2
votes
3answers
510 views

Mathematical induction: using 3 cent and 7 cent stamps

Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 cents can be obtained using 3 cent and 7 cent stamps. I thought this was the simple kind of ...
0
votes
1answer
116 views

Writing regular expressions

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the ...
1
vote
1answer
147 views

Give some examples of strings in, and not in, these sets, where Σ = {a,b}

Here's the set: {w : for some u ∈ Σ*, www = uu} From what I understand, it's saying "w (which is a string) such that for some u (which is another string) is an element of the possible combinations ...
1
vote
0answers
73 views

Rewriting regular expressions

For the following two regular expressions, how would I rewrite them as a simpler expression representing the same set? $b^* \cup a^* \cup (a \cup b)^*$ $\Big((a^*b^*)^*(b^* \cup a^*)^*\Big)^*$ I ...
0
votes
1answer
95 views

What is the image and preimage of the set values between 2 and 5?

Define f:$\Bbb R$ $\to$ $\Bbb R$ as a floor function: f(x) = $\lfloor x \rfloor$. What is $f^{-1}$ ({x| 2 < x < 5}? I figured out the image of the set values between 2 and 5. {2, 3, 4}. But I ...
1
vote
2answers
80 views

Looking for set of combinatorics problems

I'm preparing to Mathematics for Computer Science exam. What I learned from past edition of exams is fact of very often occurence of old problems. I mean more or less known problems, but possible to ...
0
votes
1answer
31 views

Number of partitions containing $k$ occurrences of a given number

Consider the ordered partitions of $N$ with size $m$ ($m \leq N$), that is, the set $\mathcal{P}_m^N$ of all vectors $\vec{n} \in \mathbb{N}^m$ such that $\sum_{i=1}^m n_i = N$. In how many of these ...
1
vote
2answers
55 views

Venn diagram of $A \cup B = B$

I have to draw 3 Venn diagrams. A $\cup$ B = B. B $\cap$ A = B. B - A = B. I understand how to shade all of these, but I do not understand what "= B" is in any of these. I've searched and can't find ...
1
vote
1answer
21 views

Define each set requested by listing the elements.

a) Give a set A with cardinality of 2. So I put A = {1,2}. easy enough b) Construct a set B so that both of the following statements are true: A $\in$ B and A $\subseteq$ B I was just gonna write B ...
0
votes
2answers
53 views

Is $\langle\mathbb Q^+, *\rangle$ a monoid?

Q: Given the set of positive rational numbers $\mathbb Q^+$, the operation is multiplication$~*$. Is $\left<\mathbb Q^+, *\right>$ a monoid? My answer is: $ \forall x, y, z \in \mathbb Q^+$, ...
1
vote
1answer
56 views

If $A = \{x\mid12 < x < 15\}$ and the universal set is the set of positive real numbers less than $15$, what is the complement of $A$?

I have to answer in set builder notation. I put $A^c = \{x\mid 0 \lt x \le 12\}$. I feel that was too easy. Am I missing something?
0
votes
1answer
54 views

Probability distributions associated with Markov chain

Let's say I have a Markov chain, with all the transition probabilities known, and there's a cost associated with each transition. The cost for transitioning from node $a$ to node $b$ is given by the ...
1
vote
3answers
96 views

Is $\{\}$ equal to $\{ \{\} \}$? [duplicate]

Is $\emptyset$ equal to $\{\emptyset\}$? I know an emptyset contains no elements. So I feel like they would be equal. Can someone explain how they wouldn't be?
0
votes
2answers
148 views

5-Card Poker Two-Pair Probability Calculation

Question: What is the probability that 5 cards dealt from a deck of 52 (without replacement) contain exactly two distinct pairs (meaning no full house)? Solution: $$\frac{\binom{13}{2}\binom{4}{2}\...
-2
votes
2answers
71 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are working with ...