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
0answers
41 views

Does there exist Latin square critical sets for which deleting any entry results in arbitrarily many completions?

For those familiar with Latin squares terminology, I'll get straight to the point: Q: For all $N \geq 2$, does there exists a critical set $C$ (for a Latin square of any finite order) such that ...
0
votes
0answers
39 views

How to generate a Poincare section for discrete particle trajectory?

I'm a novice when it comes to generating Poincare sections, and I can't seem to get it right. I have a particle moving in a 3D periodic field, and I wish to generate a Poincare section of its ...
1
vote
1answer
48 views

Prove that there are $12 + n = 4k_1 + 5k_2, k_1, k_2 \in \mathbb{N}, n \in \mathbb{N}^+$

Question: Prove that there are $12 + n = 4k_1 + 5k_2, k_1, k_2 \in \mathbb{N}, n \in \mathbb{N}^+$ The question above is taken from the following: Prove that every amount of postage of 12 cents or ...
1
vote
0answers
39 views

Linear model for data that follow gaussian distribution

I have a question about linear regression. We have the linear regression of input data $(X,Y)=((x_1,y_1),(x_2,y_2)...(x_n,y_n))$ is $$F=aX+b$$ a,b are factors of the linear line, $y_i$ is {-1,1}. ...
1
vote
1answer
94 views

Expected value over many trials

I am a poker player and was talking to my friend about expected value. He claimed that if you play far enough above your bankroll, expected value can be negative, even if you have a skill edge. I ...
0
votes
0answers
23 views

discrete cosine transform

For what sort of 1-D signals (single variable, mathematical functions), DCT does not do 'energy compaction'? Surely, if you take 'all-ones' signal and take 1D-IDCT you would get the answer. That ...
1
vote
0answers
50 views

The sum of palindromes from 100 to 900

I'm working with palindromes from $100-999$. I'm having trouble with the step highlighted in red. Can someone explain the algebra to me? Taken from: Discrete and Combinatorial Mathematics: An ...
1
vote
2answers
174 views

Prove or disprove that there are $n$ consecutive odd positive integers that are prime

Question: Prove or disprove that there are $n$ consecutive odd positive integers that are prime. If my answer for the question above is correct, then a new question arises. My Attempt: Odd numbers ...
0
votes
0answers
74 views

Prove that alteast one of the real numbers $a_1, a_2, \dots , a_n$ is greater than or equal $\dots$

Question: Don't declare this as duplicate, the duplicate question is just the first part of a two part question. 49.) Prove that alteast one of the real numbers $a_1, a_2, \dots , a_n$ is ...
2
votes
3answers
229 views

Wheel of Fortune Problem

The Summation formula is $$\sum_{i=1}^ni =\frac{n(n+1)}2$$ How is it that we know the integers $1,2,...36$ appear exactly $3$ times. And why do we multiply the sum by $3$ in the last part of the ...
1
vote
2answers
69 views

$\lfloor \sqrt{\lceil x \rceil} \rfloor = \lfloor \sqrt{x} \rfloor, \forall x \in \mathbb{R}$

Question: $\lfloor \sqrt{\lceil x \rceil} \rfloor = \lfloor \sqrt{x} \rfloor, \forall x \in \mathbb{R}$ My Attempt: Let $a = \lfloor \sqrt{\lceil x \rceil} \rfloor$ $$a \leq \sqrt{\lceil x \rceil} ...
1
vote
1answer
296 views

How can I divide 30 people into 6 different groups of 5 people in 6 ways so that no two groups share two people?

I have a group of 30 people that I need to divide into 6 groups of 5 people in 6 different ways, however I do not want the same people to be together twice. I already have 5 ways written down, but I ...
0
votes
2answers
61 views

Graph Theory, with algorithms like kruskal and something more

The new government of the archipelago of Sealand has decided to join six islands by bridges to connect them directly. The cost of building a bridge depends on the distance between the islands. This ...
1
vote
2answers
140 views

Discrete math and recursion problem.

I was recently reading up examples on recursion and how it relates to induction and there's this question I am not sure about. Q: Let $$b_1=3$$ $$b_n=n(n+2)$$ From that question I wanted to do the ...
0
votes
1answer
39 views

Maximum value of function involving factorials

Define $$g_{(k,j)} = \frac{a^{n-k}b^k(k+n)!x^{k+n-j}}{k!(n-k)!(k+n-j)!}$$, where $n,k,j \in \Bbb{N}$ are fixed such that $(0 \leq x \leq a/b ),(b<a),(0 \leq k \leq n ),(2 \leq j \leq 2n),(0 \leq ...
-1
votes
2answers
760 views

What is the efficient way to calculate number of divisors of N that are divisible by 2?. [closed]

For example if a number is given let say 8 then its factors are 1,2,4,8 hence total numbers of divisors which are divisible by 2 are (2,4,8) that is 3.
0
votes
1answer
29 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
1
vote
1answer
536 views

Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5. Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there ...
6
votes
1answer
51 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
3
votes
2answers
60 views

Use a proof by cases to show that $\lfloor n/2 \rfloor$ * $\lceil n/2 \rceil$ = $\lfloor \frac{n^2}{4} \rfloor$ for all integers $n$.

Question Use a proof by cases to show that $\lfloor n/2 \rfloor$ * $\lceil n/2 \rceil$ = $\lfloor \frac{n^2}{4} \rfloor$ for all integers $n$. My Attempt: I can only think of two cases, $n/2 \in ...
1
vote
1answer
63 views

Mapping a range of real numbers to a range of integer numbers.

I have a set of real numbers within the range [-1.0, 1.0], and I want to map them to set of integers in [-2, 2]. What is the simplest mathematical formula to achieve this?
0
votes
2answers
51 views

Discrete math equation: True or False

Hello I am having an issue with this problem. it goes like this: There exists an n for all m such that m*n = n. I am confused on how to approach this problem. ...
0
votes
0answers
47 views

Reversible smoothing of a two dimensional function (or an image)

Smoothing of an image, or a two dimensional function is quite easy, there are many methods to achieve it, using average of near elements. But how to make it reversible? Maybe DCT (discrete cosine ...
1
vote
1answer
57 views

Film Festival, with intersections graphs

I encourage you to read this problem. I have a doubt, have films 1 and 2 the same type? I read the problem and I think that films {1,3,5}, {2,4,6}, {3,4} and {5,6} are grouped, but not is the case ...
1
vote
1answer
28 views

Draw a graphic only passing one time

I would like to know when I can draw a graph, without lifting the pencil and passing once for each edge? What theory is behind that? Thanks for your time
0
votes
0answers
28 views

What is correlation kernel and compare with gaussian kernel

I read a paper that said about correlation kernel that defined: $$W(x-y)=(α/1+d(|y − x|))$$ where $α =  (\int(1+d(y − x)dy)^{-1}$, $(d(|y − x|))$ is spatial Euclidean distance from the central ...
0
votes
1answer
51 views

Making a Graph having edges

V is the set of those two-letter words built over {w, x, y, z} whose first letter is y or z. The graph G = (V, A) is defined so that two words of V determine an edge of A if they differ in exactly one ...
2
votes
1answer
118 views

About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
2
votes
2answers
319 views

Binary relation, reflexive, symmetric and transitive

I have a question regarding an image. I'm currently studying binary relations and the following image confused me: What got me confused is that the page from which I got the link ...
-1
votes
1answer
75 views

Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
5
votes
2answers
96 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
-1
votes
1answer
61 views

prenex equivalence problem [closed]

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
1
vote
3answers
52 views

Functions for boolean operators, that return 1 or 0

Are there any purely mathematical expressions that are equivalent to boolean operators and return $1$ or $0$? For example: $a > b$ Is there any $f(a, b)$ for which if $a>b$, $f(a,b)=1$ and if ...
2
votes
1answer
52 views

The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$: What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be ...
1
vote
1answer
60 views

Fibonacci numbers identity - proof by induction

$\displaystyle F_{k-1} F_{k+1} - F_k^2 = (-1)^k$ I have done the base step for $k=1$ and it works. I realize we need to prove for $k+1$, so: $$F_k F_{k+2} - F_{k+1}^2 = (-1)^{k+1}$$ Could ...
0
votes
1answer
70 views

Sumatory formula

Anybody knows the formula for this, because I don't know how to write it from the basic formula of $$\frac{n(n+1)}{2}$$: $$\sum _{i=1}^{n}{ \sum _{j=1}^{ n}{ \sum _{ k=1 }^{ n }{ \sum _{ h=1 }^{ n ...
1
vote
3answers
94 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
0
votes
1answer
158 views

How to calculate the number of combinations of getting a pair in a deck of 52 cards?

I am confused over calculating the number of ways in which I can select a pair out of a deck of 52 cards, this is how I go about solving the problem, following the definition of a pair in card games, ...
5
votes
1answer
80 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
1
vote
1answer
61 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
101 views

Big Mathematics Challenge on Set and Summation? [closed]

please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$ if we have: ...
0
votes
1answer
21 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
72 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
1
vote
3answers
50 views

Problematic Permutation Problem

i see a problem without any definition. would you please help me? i want to calculate the number of permutations of 1,2,...,1392 that 696 numbers be in the natural positions (from all numbers, 696 ...
0
votes
2answers
45 views

How do I know if a function has x roots on x-axis?

I am currently studying Newton Raphson Method. Now I am kind of having a question that how I know if the function ever has a x-root or roots on x-axis? Please let me hear your advice. I am sorry if I ...
4
votes
1answer
43 views

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin.

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin. $P(\text{H}) = p$. $P(\text{T}) = 1 - p = q$. I came up with the following two-roll ...
0
votes
3answers
35 views

Equivalence Relation with multiples

How can I prove the equivalence of this relation, and how can I calculate the equivalence class of (4,8)? On the set the relation R is definded by (a,b)R(c,d) ⇔ ad=bc. Find out if this is an ...
4
votes
1answer
98 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
0
votes
2answers
51 views

Reliability Probability problem

What is the Probability that at least one close path is formed from A to B where each switch has a Probability of close = p and each switch acts independent of the other Proposed Solution Let ...
0
votes
3answers
145 views

Proving that $aRb \iff a^2-b^2=a-b$ is an equivalence relation

Could you help me with that, I don't know how to prove if the relation is an equivalence and the class of 5? On the set of integers, the relationship is defined by $aRb \iff a^2-b^2=a-b$. Find out ...