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

3
votes
1answer
50 views

Is the set of all trees currently on earth finite, countably infinite, or uncountable?

I'm not sure how to prove this as my professor has not shown any proofs involving real world objects, but I believe that it is finite since we know that there exists an integer k = the number of trees ...
0
votes
2answers
415 views

Determine the number of positive integer x where x<= 9,999,999 and the sum of the digits in x equals 31.

Determine the number of positive integer x where $$x\le 9,999,999$$ and the sum of the digits in x equals 31 How do you approach this question? TEXTBOOK SOLUTION: Let x be written in base 10. ...
5
votes
2answers
70 views

probability of sorted array with duplicate numbers

Suppose I have a sequence of n numbers {a1,a2,a3,...an} where some of the numbers are repeated. What is the probability that the sequence is sorted?
1
vote
1answer
28 views

Different kind of infinitesimals or zeros

If there are different kind of infinities (aleph0 aleph1 and so on) then are there different kind of infinitesimals? Or should I consider zero the "opposite" of infinity if there is such a thing and ...
-1
votes
0answers
23 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
43 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 ...
0
votes
1answer
28 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 ...
0
votes
1answer
28 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 $...
1
vote
5answers
80 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
2answers
15 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?
0
votes
1answer
24 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 ...
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 ...
0
votes
1answer
15 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 ...
2
votes
1answer
68 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
1
vote
1answer
54 views

binomial coefficients difference? [on hold]

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? Here's my attempt: ...
0
votes
1answer
36 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 ...
1
vote
0answers
21 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$?
2
votes
4answers
62 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) \...
8
votes
1answer
57 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 ...
1
vote
0answers
21 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
15 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 ...
6
votes
3answers
87 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
17 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
48 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
25 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
29 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]={(...
1
vote
3answers
77 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$...
6
votes
2answers
200 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 ...
1
vote
2answers
32 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 ...
1
vote
1answer
26 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$...
2
votes
1answer
339 views

Find the minimum number of tickets to guarantee the win of a n-bit binary lottery?

Here's the problem. I just don't know how to approach it. If the 'one error tolerance' were removed, then this would be a simple binomial distribution problem. But now I can't figure it out. In ...
0
votes
1answer
24 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)$. ...
0
votes
0answers
24 views

Find the autocorrelation of y[n]=x[2n] in terms of the autocorrelation of x

Given that the autocorrelation of x is: $R_{xx} = $sin($\frac {\pi}{2}n)/(n\pi)$ I've tried to find the autocorrelation sequence but got confused about how to deal with the extra factor of 2 in the ...
1
vote
6answers
89 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
27 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 =...
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^...
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 ...
7
votes
2answers
126 views

Prove that if fewer than $n$ students in class are initially infected, the whole class will never be completely infected.

During 6.042, the students are sitting in an $n$ × $n$ grid. A sudden outbreak of beaver flu (a rare variant of bird flu that lasts forever; symptoms include yearning for problem sets and craving for ...
1
vote
1answer
32 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^{\...
2
votes
2answers
38 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 ...
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 ...
-1
votes
0answers
29 views

Use quantifiers to express each of these statements. [on hold]

Let $L(x,y)$ be the statement “$x \space\text{loves}\space y$,” where the domain for both $x$ and $y$ consists of all people in the world. Use quantifiers to express each of these statements. There ...
2
votes
7answers
75 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. ...
2
votes
3answers
36 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, ...
3
votes
2answers
30 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 ...
2
votes
4answers
19 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∪...
0
votes
2answers
36 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 ...
0
votes
0answers
31 views

What is the graph called? [on hold]

I want to recreate graph shown here. I cannot find on excel, please help me understand the maths behind this graph.
5
votes
3answers
34 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 ...
0
votes
1answer
485 views

Principle of Inclusion and Exclusion

Annually, the 65 members of the maintenance staff sponsor a “Christmas in July” picnic for the 400 summer employees at their company. For these 65 people, 21 bring hot dogs, 35 bring fried ...