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
votes
1answer
38 views

MAthematical notation for sorting submatrix and replacing it back

I need help in expressing the following paragraph in mathematical form as much as possible. I have a matrix $A$ which is $N\times M$. For each element of $A$, $A(i,j)$, I consider a submatrix of $A$ ...
1
vote
3answers
48 views

Is $B$ finite, countably infinite, or uncountable? $B = \{ x \in \mathbb{R} \mid \mathrm{floor}(x)=5) \}$

$B = \{ x \in \mathbb{R} \mid \mathrm{floor}(x)=5) \}$ I'm assuming this is the interval $[5,6)$. My first idea of a proof is the Cantor's Diagonalization Argument. But I'm not sure if that is the ...
1
vote
2answers
45 views

Compound propositions as assertions?

According to comments on my previous question, compound propositions are not assertions; i.e. the statement "$p \vee q$" does not mean "$p$ (is true) or $q$ (is true)", and it does not mean "$(p$ or $...
0
votes
1answer
74 views

Binomial coefficient paths?

Here's a problem and my attempt to answer it: We want to get a binomial coefficient identity depending on grid walking. Starting from the bottom left corner and going to the top right corner. You can ...
1
vote
2answers
29 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
2
votes
5answers
89 views

How to find remainder when $ 975^{40153}$ is divided by $14$? [duplicate]

I still find tricky this kind of problems. I tried to do solve it by factoring $14$ in $2*7$. Then, with Fermat's Little Theorem, I find that: $975^6\equiv 1\pmod 7$ $975^1\equiv 1\pmod 2$ How can ...
0
votes
0answers
16 views

Compute the time it would take to solve the Traveling Salesman Problem for a graph with 12 vertices…

I need to compute the time it would take to solve the Traveling Salesman Problem for a graph with 12 vertices where it takes 10 minutes to compute the length of a single Hamilton Circuit. A ...
-1
votes
1answer
34 views

Construct a weighted graph under the following conditions:

I need to construct a weighted graph of which neither of the Greedy Algorithms produces a correct answer to the Traveling Salesman Problem. Greedy Algorithms 1) Nearest Neighbor Works as ...
1
vote
1answer
63 views

binomial coefficients difference? [closed]

I need a difference of 2 binomial coefficients that would be equivalent to the following sum: $12\choose5$+$11\choose5$+$10\choose5$+$9\choose5$+$8\choose5$ How to answer this?
2
votes
1answer
28 views

Can I use negations in the rules of inference?

For example, modus ponens is $p \land (p → q) \therefore q$. If I had $¬p$ and $¬q$, could I do $¬p \land (¬p → ¬q) \therefore ¬q$?
8
votes
2answers
95 views

Probability that a clumsy boy eats $k$ out of 20 candies

A week or two (or maybe more) ago, the following question was posted and then deleted just as I was getting to the end of my solution. Unfortunately I have now forgotten what my solution was going to ...
2
votes
4answers
75 views

How do you prove that $p → q$ is equivalent to $p \lor q ↔ q$?

I gotta draw $p \lor q ↔ q$ from $p → q$, logically. not by a truth table. While it seems obvious, I cannot find a formal proof. This is how far I came up to: $\quad p \lor q$ $\equiv (p \land T) \...
1
vote
0answers
25 views

Statistical calculation of value of coins in a box

I woke up from a dream today that made me consider the following scenario: A grocery store has an electronic donation box. Good Samaritans slide coins into the donation box, and the donation box ...
0
votes
1answer
18 views

How can I translate this sentence into predicates and quantifiers?

sentence : Every cube is larger than something else. My Working: P(x) = x is larger than something else ∀xP(x) But the answer is something completely different. ∀x (A(x) → B(x)) : the answer ...
1
vote
1answer
19 views

Find union and intersection of family or index

For each $n∈ℕ$, let $βn = \{\ldots, -3n, -2n, -n, 0, n, 2n, 3n,\ldots\}$, and let $β=\{βn:n∈ℕ\}$. My attempt: For union, it would be all integers. As for intersection, $βn1=\{\ldots, -3, -2, -1, ...
1
vote
2answers
54 views

Proof/Reasoning why the sgn function which counts inversions has the following property?

$\mathrm{sgn}(\pi\circ\sigma)=\mathrm{sgn}(\pi)\cdot \mathrm{sgn}(\sigma)$ I am familiar with how to count inversions and any insight for why this formula holds true would be very helpful.
1
vote
1answer
27 views

Indexed Family of Sets Union and Intersection

So I have a problem with understanding indexed family of sets. The problem is: For each number $n$, let $\beta n=\mathbb N-\{1,2,3,\ldots,n\}$ and let $β=\{βn:n∈ℕ\}$. I need to find the union and ...
0
votes
0answers
32 views

Is the determinant of the following class of matrices non-zero?

For a positive integer $n$, let $c$ be the number of ordered integers tripartitions $(a_j,b_j,c_j)$ of $n$. Now consider the $c \times c$ matrix $M$ in which the value of the $M[i,j]$ is $M[i,j]={(...
0
votes
1answer
37 views

Would these witnesses satisfy this big-O function?

I'm trying to determine if $f(x) = \lceil x/2 \rceil$ is $O(x)$. I know that this is true, and the textbook answer is: $|\lceil x/2\rceil|\leq |(x/2)+1| \leq C|x|$ for all $x > 2$, with ...
6
votes
3answers
94 views

Probability of choosing $n$ numbers from $\{1, \dots, 2n\}$ so that $n$ is 3rd in size

We uniformly randomly choose $n$ numbers out of $2n$ numbers from the group $\{1, \dots, 2n\}$ so that order matters and repetitions are allowed. What is the probability that $n$ is the $3^{\text{rd}}$...
1
vote
1answer
26 views

How can I find a DNF and Minimal Form for this boolean expression?

$Q(x,y,z)=(y′\vee z′ \vee 0\vee x′)\wedge1\wedge(z\vee x′\vee 0\vee y\vee z)′\wedge(z′\vee x\vee y\vee z′)$ I'm not supposed to use tables but only proprieties like De Morgan ecc. EDIT: So I ...
1
vote
2answers
35 views

Find an example such that $X$ with the lexicographic order is not well-ordered.

Let $\{A_n\}_{n\in\Bbb N}$ be a collection of well-ordered sets. $X$ is defined by $X=\prod_{n\in\Bbb N}A_n$. Find an example such that $X$ with the lexicographic order is not well-ordered. I know ...
0
votes
1answer
29 views

Is $R$ an equivalence relation?

Let $X,Y$ be infinite sets. Define $F$ as $F=\{f:X\rightarrow Y\}$ . We define a binary relation $R$ on $F$: $fRg$ if there is no countable $S\subseteq X$ such that $\forall x\in S \ f(x)\neq g(x)$. ...
6
votes
2answers
206 views

Cardinality of the set of all infinite monotonically decreasing sequences of naturals

Find the cardinality of the set of all infinite monotonically decreasing sequences of naturals. I think it's $\aleph_0$. I marked this set in $A$, and said that $\forall n\in\Bbb N \ (n,n,n,...)\in ...
0
votes
0answers
15 views

Fourier Transform of delta(2n)

So if I have the function h[n] = delta[2n] How can I find its Fourier Transform? How does FT behave in general when the input function is downsampled (i.e. x[n]->x[2n])? I know that I can get the ...
0
votes
1answer
26 views

Definition of $0^\underline{m}$ for $m\leq0$

Using the general definition of falling powers for negative exponents, I was able to derive $$0^{\underline{m}} = \frac{1}{(-m)!}, m\leq0$$ However, I can't reconcile this with the product formula $$0^...
1
vote
1answer
30 views

Counting the number of subsets with at least one specific element.

Let $X = \left\{x_1, \dots , x_n \right\}$. I'd like to count the number of subsets of $X$ that have at least one of $k$ elements from $X$. For example, how many subsets of $X$ contain $x_1$, or $x_2$...
0
votes
2answers
28 views

Relations, Discrete Structures

Looks like this question was worded a bit different than my previous questions I've worked through, and understand. I'm having issues determining what S is. Given the set A = {1, 2, 3} and the set S =...
1
vote
3answers
86 views

How to get the correct angle of the ellipse after approximation

I need to get the correct angle of rotation of the ellipses. These ellipses are examples. I have a canonical coefficients of the equation of the five points. $$Ax ^ 2 + Bxy + Cy ^ 2 + Dx + Ey + F = 0$...
1
vote
1answer
33 views

Cantor's diagonal argument: Prove that $|A|<|A^{\Bbb N}|$

Let $A_1\subseteq A_2\subseteq A_3\subseteq...$ be a raising series of sets such that $\forall n\in \Bbb N \ |A_n|\lt |A_{n+1}|$. We mark $A$ as $A=\bigcup_{n\in\Bbb N}A_n$. Prove that $|A|<|A^{\...
0
votes
1answer
19 views

A $3$-chain is a monotonic subsequence of $3$ integers. Show that any sequence of $5$ distinct integers will contain a $3$-chain

Define a $3$-chain to be a (not necessarily contiguous) subsequence of three integers, which is either monotonically increasing or monotonically decreasing. We will show here that any sequence of five ...
0
votes
2answers
38 views

How to apply Chinese Reminder Theorem to this congruence system?

\begin{align*} 17x & \equiv -15 \pmod{5}\\ -11x & \equiv 5 \pmod{3}\\ 23x & \equiv 15 \pmod{7} \end{align*} $5$, $3$, $7$ are coprime, so the system has solution mod $105$. I'm not sure ...
2
votes
2answers
42 views

Enumerate elements of the following relations from the set A

Literally the first homework question, and I seem to be struggling. There doesn't seem to be any examples in our book, so I'm hoping someone might help walk me through it. I'm guessing it's pretty ...
2
votes
4answers
20 views

Simplifying number of sets in a relationship

Got this monster set ((A∩B) ∪C ) ∪ (A∪(B∩C)) I'm trying to reduce the number of sets to be as small as possible using set identities Set Rules All I can think of is to apply distribution law ((C∪...
5
votes
3answers
36 views

Any undirected graph on 9 vertices with minimum degree at least 5 contains a subgraph $K_4$?

Let $G$ be simple undirected graph with degree of every vertices is at least 5. Prove or disprove that $G$ contains subgraph $K_4$. I came up with this question when I were trying to find Ramsey ...
3
votes
2answers
33 views

Counting Problem (Sums of a set from 1 to 100)

In how many ways can you select two distinct integers from the set {1, 2, 3, . . . , 100} so that their sum is: (a) even? (b) odd? I'm studying for a discrete midterm this coming Monday and saw ...
1
vote
2answers
37 views

How to draw a lattice for the divisors of big numbers?

An exercise ask to find atoms and join-irreducible elements for the set of divisors of 360. I know how to find them by drawing the lattice but it seems difficult in this case. Is there another way to ...
2
votes
3answers
42 views

Finding the possible positions of chess knight mathematically relative to a given position

From this website I found the following question: A chess board’s 8 rows are labelled 1 to 8, and its 8 columns a to h. Each square of the board is described by the ordered pair (column letter, ...
2
votes
2answers
31 views

Write the expression(I don't know understand the question)

Write the expression (p^ ~q) ^ r, using only the operators v and ~. The question meant the ^ operator with v operator?
0
votes
2answers
38 views

The cardinality of all the infinite binary sequences that don't contain 010

Find the cardinality of all the infinite binary sequences that don't contain 010 I think it's $\aleph_0$. I marked the set all infinite binary sequences that don't contain 010 in A, and the set of ...
2
votes
6answers
103 views

Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
0
votes
2answers
23 views

Recurrence relations - walk on a graph

given the following undirected graph: I need to find a recurrence relation that describes the number of possible walks starting at point A. Well, naive me Iv'e defined $ a_n $ and tried to find ...
0
votes
1answer
29 views

Which one of the following is true of this relation?

Consider the set of A all the people who are living down Italy."x lives in the same house as y" is a relation on the set A.Consider the following properties of a relation on a set: a)Symmetric b)...
1
vote
1answer
22 views

What is $(A∪C)-(B∩D)$, when $A=[3,8),B=[2,6],C=(1,4),D=(5,∞)$

So the problem is asking for $(A∪C)-(B∩D)$, when $A=[3,8),B=[2,6],C=(1,4),D=(5,∞)$ My try at this: $A∪C = (1,8)$ $B∩D = (5,6]$ $(1,8)-(5,6] = (1,5)∪(6,8)$ Would this be correct? Edit: There's ...
0
votes
2answers
20 views

Equivalence Relation, transitive relation

Reading about Equivalence Relation, I understand that for a equivalence relation of a set, it must be reflexive, symmetrical, and transitive, but i'm still a little fussy on transitive to be honest! ...
2
votes
7answers
78 views

$x$ is odd if and only if $3x+6$ is odd

Prove the following proposition. Let $x\in\Bbb Z$. Then $x$ is odd if and only if $3x+6$ is odd. I'm currently not seeing a way to transform $3x+6$ into the format of $2k+1$ in order to prove odd. ...
0
votes
0answers
53 views

How many strings of 12 lowercase letters with repetitions

Consider strings of 12 lowercase letters, such as aksdjmnuuyio. How many strings either are a repetition of 2 strings of 6, such as aksdjmaksdjm, or a repetition of three strings of 4, such as ...
0
votes
0answers
16 views

Show by any method of construction that the language $A = \{a^i b^j\}$ is regular.

Show by any method of construction that the language $A = \{a^i b^j\}$ is regular. restrictions: 1) $i$ is a multiple of any given integer $n$ 2) $j$ is a multiple of any given integer $m$ 3) $n,...
1
vote
3answers
85 views

Is there a possible mathematical solution for this? [closed]

I have what might be considered an odd question. I want to see if I can find a formula/equation to help me with the following. I'm working in a software package that we are using to calculate fees. ...
0
votes
0answers
21 views

Is there a faster way of computing the probability of a sum $S$ when $n$ dice are rolled? [duplicate]

So far, I've only had to deal with $2$ dice or $3$ dice problems. For example, if the problem asks to find the probability that a sum of $8$ will be achieved from rolling $3$ dice, I just list all the ...