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
42 views

Discrete Math and non-empty relations

Let $A=\{a,b,c,d\}$ and $B = \{w,x,y\}$, then a non-empty relations on $A$ is: $\{ (b,c), (b,d)\}$ Can someone explain why this is true? I thought that the requirements for any relations of a set ...
0
votes
1answer
50 views

The “sides” of a k-regular bipartite graph are equal?

I was reviewing some lectures notes and noticed that in a proof of a theorem our lecturer stated that the "sides" of a k-regular bipartite graph are equal and that it is trivial to prove it. Anyway ...
5
votes
0answers
63 views

Show that $\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$

Question: Show that $$\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$$ (Here the sum is over all non-empty subsets of the set of the $n$ smallest positive ...
0
votes
1answer
81 views

Solving this recurrence relation

please tell me a way to solve this recurrence $$n\cdot R_n=C_1\cdot R_{n-1}+C_2\cdot R_{n-2}.$$ $C_1$ and $C_2$ are constants.. There is an $n$ there in the left hand side.. it makes mess. I tried ...
0
votes
1answer
42 views

Small remarkable matroids

I'm working on a problem involving matroids $M=(E,\mathfrak{C})$ (here $E$ is the ground set, $\mathfrak{C}$ the set of circuits) with a "small" ground set $E,$ in the sense that $\sharp(E)\leq7$ I ...
3
votes
0answers
43 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 ...
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
112 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
26 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
55 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
203 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
84 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
243 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
70 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
418 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
63 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
179 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
41 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
1k 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
570 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
52 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
64 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
110 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
55 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
51 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
58 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
30 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
1answer
56 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
120 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
376 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
79 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
97 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
vote
3answers
53 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
53 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
63 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
83 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
97 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 ...
1
vote
2answers
366 views

Number of Ways to Draw a Pair in a Poker Deck

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 ...
5
votes
1answer
88 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
65 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
104 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
22 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
78 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
54 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
47 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
37 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
121 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 ...