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

2
votes
1answer
14 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{...
6
votes
2answers
85 views

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

First of all, I am a 12th student 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 let the world know about whatever I ...
0
votes
0answers
10 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
31 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
1answer
33 views

Prove that $\frac{n}{x}=\sum_{i=1}^∞ \frac{n}{(x+1)^i}$ [on hold]

Can you please show me how to prove that $$\frac{n}{x}=\sum_{i=1}^∞ \frac{n}{(x+1)^i}$$ is real for any n,x ϵ ℕ* . I think that is has something to do with limits but I am not entirely sure. I am a ...
3
votes
0answers
27 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
49 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
28 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 ...
0
votes
1answer
42 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 ...
0
votes
1answer
26 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$...
2
votes
0answers
51 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
13 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
20 views

In graph theory, draw the graph corresponding to the matrix A

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
20 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 ...
1
vote
0answers
20 views

Formulate as standard problem: Optimal cyclic permutations

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
43 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
38 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 \...
0
votes
0answers
11 views

Can fourier transform be considered as a sum of a discrete series? [on hold]

For a non periodic function in x domain, I think the difference between fourier transform and fourier series lies in the coefficients ,if I don't pull T out of the coefficient which makes it dw in ...
-1
votes
1answer
31 views

If G and H are two gaphs 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
116 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
3answers
54 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
33 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
37 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
42 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
17 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
87 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
30 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
60 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?
2
votes
1answer
27 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
1answer
69 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
67 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
22 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
16 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
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
50 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
30 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
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 ...
6
votes
3answers
88 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
21 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
33 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
25 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
203 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
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 ...
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
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$...