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
2answers
77 views

x + y = y + x is not a statement in Discrete Mathematics?

I was reading my notes and i noticed something a little unusual. How is $$x + y = y + x$$ not a statement? The reason that was given in the notes was "we don't know what $x$ and $y$ are, so they ...
3
votes
1answer
24 views

prove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graph

I'm a discrete math student and I've bumped into the following question. I tried to prove it and specifically in first part I thought of two ways of proving it. but in each of the ways the proof looks ...
0
votes
2answers
91 views

Prove that $\log(n!)\leq(\log(n))!$

Prove that $\log(n!)\leq(\log(n))!$ My attempt: I read somewhere that $n\leq\log(n!)\leq(\log(n))!$. But when I used calculator $\log(n!)$ can not be less than or equal to $(\log(n))!$. ...
0
votes
1answer
23 views

Universal and Existential quantifier in Propositional logic

The following paragraph is an excerpt from Discrete Mathematics book of Kenneth Rosen 7edition The restriction of a universal quantification is the same as the universal quantification of a ...
1
vote
1answer
26 views

Closure of a function

"Let $f: A \rightarrow A$ and let $X \subseteq A$. Then, in a ‘top down’ version, the closure f[X] of X under f is the least subset of A that includes X and also includes f(Y) whenever it includes Y. ...
0
votes
4answers
57 views

Prove for all $ n\in \mathbb{N} $ ,$n ≥ 1, a(n)$ is odd.

Prove for all $n\in\mathbb{N}\backslash \{0\}$, $a(n)$ is odd. Consider the sequence defined as followed: $a(1)= 1$ $a(2)= 3$,where $n \in \mathbb{N}$ $$a(n)=a(n-2)+2a(n-1), n ≥3$$ Conjecture: ...
0
votes
0answers
11 views

Give aysmptotic bounds for T(n) in each of following recurrences. Make bounds as tight as possible.

T(n) = T(n-2) + 4 T(n) = 3T(n-1) + 3 T(n) = 2T(n/8) + 4n^2 I can't figure out how to do the first two, none of the examples on google or my lecture slides show how to do solve for anything about "+ ...
2
votes
1answer
55 views

Linear four-parameter recurrence from Concrete Mathematics

In the book Concrete Mathematics, there's an exercise (1.16) where you're asked to solve a general four-parameter recurrence using the Repertoire Method. The recurrence is defined as follows: \begin{...
8
votes
2answers
234 views

I derived a new formula related to arithmetic sequences, I think!

First of all, I am a 12th grader so I don't know how to write research notes. So please forgive me if my writing is not so impressive! I don't know what to do to tell the world about whatever I found....
0
votes
0answers
19 views

Regarding pedigrees

Here's a errrhmm.... a modelling problem. Applied math. Or something. We're given pair of sets $X,Y$ (for notational simplicity, assumed disjoint). Let $T_{X,Y}$ denote the following disjoint union:...
1
vote
2answers
38 views

Is there any formula to find the nth element in a sequence where common difference (d) is varying with a constant rate?

To explain my question, here is an example. Below is an AP: 2, 6, 10, 14....n Calculating the nth term in this sequence is easy because we have a formula. The common difference (d = 4) in AP is ...
3
votes
0answers
54 views

Expectation of Gaussian Ratios

Consider the following expression: $z = \frac{\mathbf{x}^H P \mathbf{x}}{\mathbf{x}^H \mathbf{y}}$, where $\mathbf{y}$ is fixed (not random) and $\mathbf{x}$ is a complex Gaussian vector of zero mean ...
5
votes
1answer
65 views

Sum of nth powers of Fibonacci numbers

Is a closed form for $$\sum_{i=1}^n{F_i^k}$$ (where $F_i$ is the $i^{th}$ Fibonacci number and $k$ is constant) known?
2
votes
0answers
52 views

What is probability that a team reaches final if we know the probabilities of all opponents in the semi-final?

Our Discrete Math professor asked us a question as the Euros are going on. Given the following info, what is the probability that Portugal will make it to the final? Win Probabilities in quarter ...
-1
votes
1answer
60 views

Checkers Board Problem

Here we consider a checkerboard expanded to size 12 × 12 instead of the ordinary 8 × 8 checkerboard. a) How many squares on this board contain more than a third of the total number of dark small ...
2
votes
3answers
74 views

Splitting a file into $m$ pieces of size $1/n$, such that any $n$ pieces allow you to recover the file?

Let's say we have a file (which we could define as a finite sequence of 0's and 1's (or any other two symbols)). For $m > n$, can you create $m$ pieces (which are themselves files), each $\frac 1n$...
3
votes
0answers
89 views

Definition of “Differentia” in Lewis Carroll's Symbolic Logic?

I am reading chapter $2$, and from what I understand, it seems like the differentia of a class is not well-defined. The book gives some definitions: The class "Things" here refers to the class ...
1
vote
2answers
15 views

Number of possible win-loss outcomes per round in an n team round robin tournament

I was thinking of the following problem related to discrete math. Assume that we have n teams scheduled for a round robin tournament. For any given round in the tournament, how many possible win-loss ...
1
vote
0answers
27 views

In graph theory, draw the graph corresponding to the matrix A [closed]

I am studying statistics but decided to have some classes in mathematics. This class is called optimization but apparently, the content is graph theory. This is my first time of taking such class and ...
3
votes
1answer
30 views

Matching in bipartite graph

Every student from a set of students applies for exactly three seminars among the seminars that are offered at their university. Two of the seminars are chosen by exactly 40 students, all others are ...
3
votes
0answers
81 views

Optimal cyclic permutations (Formulate as standard problem)

How can we find cyclic permutations $\prod_i$ to be applied to each of corresponding $i$'th rows of a square matrix $X$ of size $n \times n$ such that a given sum of pairwise costs $\sum_{ij}C\left[\...
-1
votes
1answer
49 views

Relations: How to prove $R^2R^3 = R^5$?

Relations: How to prove $R^2R^3 = R^5$ ? I tried to go by this definition but I'm not quite sure I'm in the right path. $RS = \{(x,y) | \exists z, (x,z) \in R$ ^ $(z,y) \in S\}$
2
votes
3answers
40 views

A number theory proof - how do I use these intuitions to prove $c^2 \mid ab$?

I've just been introduced to number theory and I had to admit it's a very cool math subfield. Solving problems is another matter entirely, however. Here is the problem: For positive $a, b, c \in \...
-1
votes
1answer
44 views

If $G$ and $H$ are two graphs, then what does $G \Delta H$ indicate in graph theory?

I came across this notation in a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen.
4
votes
1answer
69 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 ...
6
votes
2answers
126 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?
2
votes
2answers
63 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
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
88 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
74 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
28 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)$. ...