Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

1
vote
3answers
40 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
31 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 ...
0
votes
1answer
47 views

Fibonacci Induction Proof

$\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
53 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
84 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
0answers
27 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, ...
4
votes
1answer
42 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
42 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
98 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
17 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
42 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
33 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
43 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
40 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
27 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
39 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
24 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
92 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 ...
0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
0
votes
2answers
51 views

Sets and Relations in Math

I have not knowledge about relations, could you help me to solve this excercise step by step, to use in futures excercices? Thanks for your time. Given the set $A = \{1, 2, 3, 4\}$ and $B = \{1, 3, ...
0
votes
0answers
25 views

Use the Chinese Remainder Theorem to show that an integer $a$, with $0 \leq a < m = m_1*m_2* \dots *m_n$, …

Question: Use the Chinese Remainder Theorem to show that an integer $a$, with $0 \leq a < m = m_1*m_2* \dots *m_n$, where the integers $m_1, m_2, \dots, m_n$ are pairwise relatively prime integers ...
1
vote
3answers
73 views

Counting valid tickets

I think my question is very easy but I need to understand. The problem is, I have a ticket with 2 numbers from 1 to 10. The first number cannot be greather than the second number. How many valid ...
1
vote
0answers
20 views

How do I prove this equality involving ceilings and max?

For all $T \in \mathbb{N}$ the following holds, with $k \in \mathbb{Z}$ and $m, n \in \mathbb{N}$: $$\left \lceil \frac{k \cdot m}{n} \right \rceil + T - 1 = \max_{0 \leq i < T} \left \{ i + T ...
0
votes
0answers
27 views

Mathematical Modeling for the Mapping Relationship

I have encountered a problem in my research and have no idea how to model the problem. To simplify the description, I tell a game with the same rule instead of the original problem. Consider two set ...
1
vote
1answer
27 views

Alternatives to absolute error?

Let me explain my scenario in which I need to calculate absolute error. Lets say the X is the actual value. And X' is the value of X with some error 'e'. So X' = X + e'. Lets say i = 1 to 10000. I ...
1
vote
0answers
46 views

A models or papers on (semi) automatic generation of impossible figures?

I myself was able to find only few papers on this subject: "Torus Figure Generating System Based on Graph Theoretical Representation and Topological Analysis" This one is fine. You provide a flat ...
1
vote
0answers
25 views

Either or in compound statement

I think this might be a silly question, but I'm confused. Please help me to understand it. Statement is: Randy studies German on either Tuesday or Friday. How should I write this as compound ...
0
votes
2answers
48 views

Constructing a formule

Could you help me with that? \begin{align} 1 &= 1 \\ 1 - 4 &= -(1 + 2) \\ 1 - 4 + 9 &= (1 + 2 + 3) \\ 1 - 4 + ...
3
votes
5answers
580 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
2
votes
3answers
36 views

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct [closed]

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct. for when does this not continue to hold up ( ie instead of 12 , its ...
0
votes
4answers
58 views

Math expression with potencies always 13 multiple

Hello my question is simple: How can I prove that $$4^{2n+1}+3^{n+2}$$ is always divisible by 13? Thanks for your time ;)
1
vote
1answer
34 views

Determining the different number of subsets (counting, permutations, combinations)

Given that any fixed integer n>0, let S={1,2,3,4,...,n}. Now a Red-Blue subset of S is called T. Every element of T is given a colour (either red or blue). For instance {17 (red)}, {1 (red), 5(red)} ...
2
votes
3answers
466 views

Fibonacci Numbers Proof

Prove the following fibonacci sequence, which appear in Pascal's Triangle. I am not sure where to start on this, any pointers? $$ f_n = {n\choose0} + {n-1\choose1} + ... + {n-k\choose k}$$ where ...
1
vote
1answer
43 views

Permutations, Combinations, and Counting

A group of 63 people are camping together. They have two 6-person tents, three 4-person tents, five 3-person tents, and three 2 person tents. 18 people will sleep outside of the tents under a tarp. ...
2
votes
1answer
49 views

How many answers can be created using the elementary arithmetic operators?

If I gave you an amount of $n$ numbers, how many anwswer will you be able to create using the elementary arithmetic operators ($+, -, \times, /$)? These are the rules: All numbers ...
0
votes
2answers
31 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
1
vote
1answer
32 views

Convert adjacency matrix to graph

Is there any online service that can provide possible graphs (the simplest one) when I give a sequence of integers (node degrees) as input (or reject the input) -based on Erdős-Gallai formula? Thanks ...
-1
votes
1answer
55 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
0answers
14 views

Solution of definite integral of product of bessel function and exponential

I have an integral $I=\int_{\theta} \int_r J_m(k_1r)e^{-j[P_x r \cos(\theta)+P_y r \sin(\theta)]} r dr d\theta$ $0\leq\theta\leq2\pi; r<\infty$ is there any method to solve this?
0
votes
1answer
20 views

Find a formula for the integer with smallest absolute value that is congruent to an integer $a \bmod m$, where $m$ is a positive integer.

Question: Find a formula for the integer with smallest absolute value that is congruent to an integer $a \bmod m$, where $m$ is a positive integer. My attempt: I don't completely understand the ...
0
votes
1answer
51 views

What is the derivation of A not being a proper subset of B?

The exact question is actually "Derivation A ⊄ B", and I am assuming that derivation in this case means to prove and give an example of when this is true? If it is then A is not a proper subset of B ...
0
votes
2answers
32 views

Use the Binomial Theorem to show that $0 = \sum_{k=0}^ n (-1)^{k} {n \choose k }$ [closed]

Use the Binomial Theorem to show that "$$0 = \sum_{k=0}^ n (-1)^{k} { n \choose k}$$".
0
votes
1answer
35 views

$a \equiv b(\bmod m) \iff a \bmod m = b \bmod m$

$a \equiv b(\bmod m) \iff a \bmod m = b \bmod m$ My attempt: $a \equiv (\bmod m) \Leftarrow a (\bmod m) = b (\bmod m)$ $\exists q_1, q_2\in\mathbb{R} | (a = m*q_1 + r) \wedge (b = m*q_2 + r)$ ...
1
vote
1answer
31 views

Discrete math and rules of inference

I recently did this rules of inference/logic question and the method I used was different from the textbook so I was wondering if my work was correct?
0
votes
1answer
40 views

How to derive this formula about the bracket function?

Is there a direct way of proving that $$ [nx] = [x] + [x+\frac{1}{2}] + [x+\frac{1}{3}] + \ldots + [x+ \frac{1}{n}]$$ for each real number $x$ and for each positive integer $n$? My effort: Let ...
4
votes
2answers
34 views

Proving Induction $(1\cdot2\cdot3)+(2\cdot3\cdot4)+…+k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4$

I need a little help with the algebra portion of the proof by induction. Here's what I have: Basis Step: $P(1)=1(1+1)(1+2)=6=1(1+1)(1+2)(1+3)/4=6$ - Proven Induction Step: ...
2
votes
2answers
71 views

Solving the equation $n\log n = 10^9$

This seems very basic (I guess my calculus needs brushing up). Is there a way to find n without a calculator in this one? $10^{9} = n\log(n)$ My Attempt (log is base 2 base on the book convention.) ...
1
vote
1answer
63 views

The relationship between each harmonic numbers

In Knuth's "Concrete Mathematics" in chapter about numbers below equality is given $$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{\epsilon_n}{120n^4} $$ where $0 < \epsilon_n < ...
2
votes
1answer
80 views

First Order Logic Consistency Big Problem

as i read some tutorial material on First Order Logic, i deduce that the following formula was consistent in FOL except the third one. am i right? i have doubt about the first one. any idea? thanks to ...
0
votes
2answers
69 views

Show that $\binom{n}{k}< \binom{n}{k+1}$ if and only if $k < (n-1)/2$ [closed]

Show that $\binom{n}{k} < \binom{n}{k+1}$ if and only if $k < \frac{n-1}{2}$ and then use this to deduce that the maximum of $\binom{n}{k}$ for $k=0,1,\dots,n$ is $\binom{n}{\lfloor ...