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
1answer
7 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
23 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 ...
1
vote
3answers
42 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
21 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 ???
-1
votes
2answers
37 views

Is there a way to simplify… [on hold]

Is there a logical equivalence to ¬p∨q?
-2
votes
0answers
37 views

In Z_437, calculate 30 circled division 29 [on hold]

I am having trouble with modular division, especially finding inverses. I know the answer is 212, but I was hoping someone could show me how to reach this answer. Other practice problems include (all ...
1
vote
3answers
31 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
25 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 ...
3
votes
1answer
39 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 ...
0
votes
0answers
25 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$ ...
-2
votes
1answer
29 views

basic statistic [on hold]

1) In a class of 32 children, 16 have a skateboard, 12 have a bicycle and 17 have a scooter. 5 of them have a skateboard and a bicycle. 7 of them have a skateboard and a scooter. 4 of them have a ...
1
vote
2answers
26 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
36 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
35 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
26 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)$ ?
2
votes
1answer
24 views

Finding the recurrence relation(with square roots) [on hold]

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
36 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
19 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
4answers
53 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$: ...
2
votes
1answer
24 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 = ...
-1
votes
1answer
35 views

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

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

Let f : N9 → N9 be defined by f(x) = (5x + 3) mod 9. Find f −1 if it exists. [on hold]

Let $f : N/9 → N/9$ be defined by $f(x) = (5x + 3) \bmod 9$. Find $f^{−1}$ if it exists.
1
vote
0answers
47 views

How to find the eigenvalues numerically

How to find the eigenvalue numerically for this ode $$u''-ku'-\lambda u=0$$ with BCs $u(\pm c)=u(0)$ ? I tried to discretize in space like so: $$x_j=jh$$ $$u''=\frac{u_{j+1}-2u_j+u_{j-1}}{h^2}$$ ...
0
votes
1answer
11 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
votes
0answers
21 views

Discrete mathematics combinations with repetition?? [on hold]

A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernickel bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are there to choose a) six bagels? ...
0
votes
1answer
25 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
25 views

Adding two variables with subscripts [on hold]

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 ...
1
vote
2answers
41 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 ...
1
vote
2answers
34 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
25 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
41 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
44 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
28 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 ...
13
votes
5answers
2k 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, ...
-2
votes
2answers
52 views

Prove by mathematical induction $F(2) + F(4) + … + F(2n) = F(2n+1) -1$, for every positive integer n. [on hold]

I got that $F(2k+1) -1 + F(2k+1) = F(2k+2) -1$, but I do not know how to add those two. Can you please help me? Thank you.
0
votes
1answer
33 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
22 views

The complete bipartite graph K2,5 is planar [on hold]

I wonder why The complete bipartite graph K2,5 is planar?
2
votes
1answer
46 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
54 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
40 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 ...
0
votes
1answer
39 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
votes
0answers
16 views

Linear Non-Homogeneous Recurrences - Guessing the particular solution [on hold]

why does one need to multiply the particular solution of the function $4\cdot7^n$ with n, but this is not the case with $5 \cdot 2^n$. So what I'm asking is, why is the particular solution to $4 ...
1
vote
0answers
40 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
39 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
40 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
21 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
50 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
15 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
41 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
43 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?