Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-mathematics]

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.

Discrete mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous objects require real numbers.

Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter −

  • Sets, Relations and Functions
  • Mathematical Logic
  • Group theory
  • Counting Theory
  • Probability
  • Mathematical Induction and Recurrence Relations
  • Graph Theory
  • Trees
  • Boolean Algebra

For an overview, see the Wikipedia entry on Discrete mathematics.

and http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Consider using a more specific tag instead, such as: , , , , , , , , etc.

32903 questions
2
votes
2 answers

Why is the number of elements in a union of 3 sets that?

In my maths notebook, it says that if $A$, $B$, and $C$ are finite sets then: $$ n(A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ C) $$ However I don't know how this works properly. It does seem to work based on the…
Apoqlite
  • 321
2
votes
2 answers

Multinomial theorem member that does not contain an irrational number

Hey I am supposed to solve the following problem: Specify a development member that does not contain an irrational number: $$\left (\sqrt{5} - \sqrt[3]{2} +2 \right )^{6}.$$ So I used multinomial…
user714814
2
votes
1 answer

List all injective relations between two sets

$A=\{1,2\}$ $B=\{2,3\}$ List all injective relations $F: A \rightarrow B$ This is what I came up with: $$F_1(1)=2$$ $$F_1(2)=3$$ $$F_2(1)=3$$ $$F_2(2)=2$$ Is that all? It seems to me that I'm missing something here. Can you also have an element in…
Belen
  • 568
2
votes
3 answers

Surjective function: Discrete Maths

How to know whether this function is surjective or not? I know that we have represent x in terms of y and then substitute some value of y for which the domain of x is not satisfied, but for this sum, how to represent x in terms of y?
Turing101
  • 201
2
votes
4 answers

I have a number that represents 40%. How do I get the whole?

I know 8,000 represents 40% of X and I'd like to figure out X. I can start by doubling 8,000 and that gets me 80% of the total. 10% of the 8,000 is 1,000 and I can add that twice to get the remaining 20%. If 8,000 is 40% of X, then X is 18,000. Is…
user721825
2
votes
3 answers

Prove by induction help?

I'm trying to study for a test and one of the practise questions is very confusing and not sure what to do: Prove by induction that $$\sum_{i=1}^n \frac{3}{4^i} < 1$$ for all $n \geq 2$ The furthest I'm able to get is getting rid of the…
Abushawish
  • 627
2
votes
0 answers

Application of congruences

All books are identified by an International Standard Book Number (ISBN), a 10–digit code $x_1,x_2,\cdots,x_{10}$, assigned by the publisher. (This system was changed in 2007 when a new 13–digit code was introduced.) These 10 digits consists of…
kyla
  • 29
2
votes
1 answer

Operator precedence for integer division

What will be the answer for x for the following x = 27 * 24 \ 4 /2 is it 81 or 324 - considering that there is an integer division(/) which is said to have lower precedence than (/,*) Your help in this regard will be much appreciated
user2206576
  • 23
2
votes
1 answer

$f$ is bijective, but is not the identity function $f(x) = x$.

For the problem: Let $A = \{1, 2, 3, 4, 5, 6\}$. Give an example of a function $f : A → A$ such that $f$ is bijective, but is not the identity function $f(x) = x$. Is this valid example: $f=\{(1,2), (2,1), (3,3), (4,4), (5,5), (6,6)\}$. ? If…
Dani Che
  • 503
2
votes
1 answer

Total number of integer solutions with constraints

Find the number of ways 5 dices can be rolled to get a sum of 25. While solving this question, the way we solve it is $x_1+x_2+x_3+x_4+x_5$ $=25$ where $1<=x_i<=6$ So we replace $x_i$ by $y_i =6-x_i$ , which is $x_i=6-y_i$ substituting $x_i$…
Turing101
  • 201
2
votes
1 answer

How many subgraphs of $K_{n}$ are isomorphic to $K_{a,b}$

This is the solution to the question. But I don't get why's that when a=b, "the same subgraph will also be selected by interchanging A and $A^{'}$", but it's not the case when a not equal to b? From my understanding, $K_{a,b}$ is a bipartite…
Joshua Leung
  • 555
2
votes
2 answers

Logical evaluation of construction

∀x(¬Qx → Px) ∃x¬Px ∴ ∃xQx For the above argument, is it possible to construct a counter-model to show that the argument is invalid? If not, what is the reasoning that it is valid. For example, through trial and error, creating a Domain {1,2}…
D.Ronald
  • 540
2
votes
2 answers

Prove that sum of the $k$ numbers in the $k$th group = ${\frac{1}{2}\left(k(k^2+1)\right)}$.

Consider an arrangement of the positive integers, grouped as shown, so that the $k$th group has $k$ elements: $(1),(2,3),(4,5,6),(7,8,9,10), \ldots$. The expression for the sum of the $k$ numbers in the $k$th group turns out to be…
K.Hu.1106
  • 71
2
votes
4 answers

Are there integer solutions such that the sum of the roots of x and y equal the root of a prime p?

How could one prove whether or not integer pairs (x, y) exist such that $\sqrt{x} + \sqrt{y} = \sqrt{p}$, where p is prime? `
ROS
  • 191
2
votes
1 answer

Is there a theorem related to 0 xor 1 xor 2 xor ... xor 1000000 = 1000000?

While testing for a program, I found that 0 xor 1 xor 2 xor ... xor 1000000 = 1000000 and it is true for the numbers in this form except for 10: 1 1 true 10 11 false 100 100 true 1000 1000 true 10000 10000 true 100000 100000 true 1000000 1000000…
nonopolarity
  • 495
1 2 3
…
99 100