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

1
vote
1answer
13 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
27 views

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

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

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

Let $f : N/9 → N/9$ be defined by $f(x) = (5x + 3) \bmod 9$. Find $f^{−1}$ if it exists.
0
votes
0answers
19 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
6 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
20 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
0answers
11 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
22 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
39 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
1answer
26 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
24 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
35 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
42 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
48 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
44 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
50 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
38 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
15 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
34 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
36 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
39 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
39 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
38 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
85 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
28 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: ...
0
votes
0answers
34 views

Trial division formula [on hold]

I'm not very good with mathematic notation, I'm trying to describe a formula for trial division. Can anyone point me in the right direction or provide an answer? Also please do explain the notation ...
0
votes
0answers
12 views

How can I find out the Energy of this Energy signal?

I am trying to solve the problems in my text book. but I reached an impasse in 'discrete-signal' chapter. $x[nT]=(-0.5)^nu[nT]$, $ $ $ $ $T=0.01s$ ...
-1
votes
0answers
28 views

Understanding the set structure of probability theory [on hold]

Since events have their own probabilities and outcomes have their own probabilities. Why don't we just consider only one of events or outcomes directly? What's the motivation to have this set-point ...
-1
votes
2answers
24 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 ...
-1
votes
1answer
37 views

Need help on understanding a theorem on subsets

An example in my textbook for Discrete Mathematics states, that, Let A be a set, and B = {A, {A}} Then A is a included in B, and so is {A} also an element of B. (Understood) Also it states, {A} is a ...
1
vote
2answers
57 views

Is there an application form $\emptyset\to\emptyset$.

What is the cardinal of $\mathcal F(\emptyset,\emptyset)$ where $\mathcal F(X,Y)$ is the set of the function from $X\to Y$ ? I would say $0$ because a function can't associated nothing at nothing, but ...
2
votes
0answers
24 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
-1
votes
1answer
72 views

define two functions whose compositions are equal to identity

Let B be the set $B = \{1,2,....n\}$ where n is a positive integer. Let C be the set of all bitstrings of length n and let Z be the set of all functions from B to $\{0,1\}$. How do I find the two ...
14
votes
13answers
3k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [on hold]

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142. But I ...
2
votes
3answers
92 views

If $\gcd(ab,c)=d$ and $c|ab$ then $c=d$

For all positive integers $a$, $b$, $c$ and $d$, if $\gcd(ab, c) = d$ and $c | ab$, then $c = d$. Need help proving this question, I know that $abx + cy = d$ for integers $x,y$ and that $c|ab$ can be ...
1
vote
1answer
34 views

Raising an adjacency matrix to a power: Why does it work?

An adjacency matrix $M$ represents the number of ways to travel between pairs of points in a network in exactly one move. $M^k$ represents the number of ways to travel between pairs of points in a ...
3
votes
4answers
62 views

Intuitive explanation for p ∨ q → r ≡ ( p → r) ∧ (q → r)

Although, it is possible to prove the above equivalence using truth tables, I don't know how to prove it without using truth tables.Can someone explain it in plain english?
3
votes
1answer
38 views

How many numbers between 1 and 10000, inclusive, are multiples of 12 or 20?

I calculated the multiples of 12 and multiples of 20, 833 and 500 respectively. Now I calculated the multiples of 12 * 20 = 240,and as a result have 41. The solution would be 833 + 500-41 = 1292 ...
-5
votes
0answers
24 views

How does an image an preimage come about from inequality? [closed]

How does an image or a preimage come about from inequality like this: f(x)={1 < x < 4}
0
votes
1answer
27 views

uniform distribution vs normal distribution for discount use case [closed]

Problem statement: Reward a customer with lucky draw coupon of X% discount in between 1% to 100% Assume that slabs are pre-defined ( all are theoretical) 1% discount : 90% customers 10% ...
0
votes
1answer
28 views

Union of subspace

Q. Say U and W are subspaces of a a finite dimensional vector space V (over the field of real numbers). Let S be the set-theoretical union of U and W. Which of the following statements is true: a) ...