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
40 views

How do you prove the stable marriage lattice is distributive?

Show that the stable matching Lattice is distributive, i.e., if M1,M2,M3 are stable matching then: M1 join (M2 meet M3) = (M1 join M2) meet (M1 join M3) and M1 meet (M2 join M3) = (M1 meet M2) join ...
0
votes
1answer
46 views

The number of functions on a finite set of numbers for which the Cauchy-Schwarz inequality is an equality

Let $f$ be a function from $\{1,2,3,\dots,10\}$ such that $$(\sum_{i=1}^{10} {{|f(i)|}\over {2^{i}}})^{2} = (\sum_{i=1}^{10}{|f(i)|}^{2})(\sum_{i=1}^{10}{{1}\over {4^{i}}}) $$ How many such ...
2
votes
0answers
105 views

How to find expectation in this weird problem? (Pretty Interesting)

There are $N$ wires. The $i^\text{th}$ wire has $P_i$ bulbs. The bulbs are connected in series, so if you break a bulb, all the bulbs on the wire go out. A person can break any lit bulb with equal ...
2
votes
2answers
62 views

In how many ways we could put balls into boxes?

In how many ways we could put $n+5$ indistinguishable balls into $n$ distinguishable boxes and at least $2$ boxes have to be empty? This is my answer: ${n}\choose{2} $$\cdot$$ ...
0
votes
0answers
12 views

Coloring of merged $C_4$ and $C_5$ graph

I'm learning Polya's enumeration theorem and Burnside lemma. I found a task that considers graph $G = C_4 + C_5$ where $C_k$ is $k$-cycle and set of edges is defined like this: all old edges are in ...
0
votes
0answers
88 views

For each pair of functions f1 and f2 in (a) - (h) below, provide functions h1

For each pair of functions f1 and f2 in (a) - (h) below, provide functions h1 and h2 such that f1 = Θ(h1) and f2 = Θ(h2). The functions h1 and h2 should be in one of the following forms: n k logp n or ...
0
votes
2answers
55 views

Identify the error - Discrete math

I'm having problems trying to identify the error in this proof in the question below: Let $u$, $m$, $n$ be three integers. If $u\mid mn$ and $\gcd(u,m) = 1$, then $m = \pm1$. If $\gcd(u,m) = 1$, ...
0
votes
0answers
88 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 ...
0
votes
2answers
46 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, ...
1
vote
1answer
35 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)$, ...
2
votes
2answers
51 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
57 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
34 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
268 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
23 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
64 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
43 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
41 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
57 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
39 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
203 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
44 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
33 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
36 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
44 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$: ...
2
votes
1answer
79 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
61 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$
1
vote
0answers
51 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
55 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
83 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
35 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 ...
1
vote
2answers
47 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
77 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
80 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
159 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
38 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 ...
16
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
77 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
89 views

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

I wonder why The complete bipartite graph K2,5 is planar?
2
votes
1answer
53 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
244 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
93 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
119 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
67 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
74 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
68 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
30 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 ...