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
3
votes
1 answer

Is my method for proving this implication correct?

My professor put up the lecture slides from today's lecture and I decided to go over the proof again since I didn't quite catch it in class. I think I found something wrong with her proof. Please let me know if mine is correct or if I am…
Cherry_Developer
  • 4,239
3
votes
1 answer

Help with set builder notation

I want to express the following set using set builder notation: '{x | x is the square of an integer and x < 100}', My attempt : $\{ a \in \mathbb Z \mid x = a^2 \land x < 100 \}$. Is this correct?(I don't know how to type the epsilon and and symbol…
Carefullcars
  • 527
3
votes
1 answer

$m$ and $n$ are two integers. Prove $mn+n$ is odd if and only if $m$ is even and $n$ is odd

I get that this has to be solved as a by conditional. So first I would just solve directly: $m$ is even and $n$ is odd, so $m = 2k$ and $n = 2j+1$. Therefore $mn+n = 2(2kj+k+j)+1$, which is odd. This is where I'm getting confused. Next when you…
user3915992
  • 63
3
votes
1 answer

Question about subset and elements.

Let $A = \{3,4\}$ be a subset of $S = \{1,2,\ldots,6\}$. Or $A \subseteq S$ and $n \in A$, what is $n \notin A$? Would $n \notin A$ be $\{1,2,5,6\}$? Does that question even makes sense? Help! Trying to solve a proof question but I'm confused with…
misheekoh
  • 799
3
votes
2 answers

Prove the binomial coefficient equation

Prove the equation. I'm not sure where to begin $$ \sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} = \frac{n+1}{n+1-m} . $$
allen
  • 47
3
votes
1 answer

Let $p \neq \pm 1, 0$ be an integer. Prove that $p$ is prime iff for all $a \in \mathbb Z$, either $p \mid a$ or $(a, p) = 1$.

I'll try in $\to$ direction; Nothing divides the prime $p$ but $\pm1, \pm p$. If $a = \pm p$ or $a = \pm 1$ then $p \mid a$. Assume $p = 2$ . If $a$ is even, then $p \mid a$ and if $a$ is odd, then $(a, p) = 1$. Suppose $p > 2$. If $a$ is even,…
user266485
  • 31
3
votes
3 answers

solving negative linear congruences

OK so I know how to solve linear congruences when they're positive but negative is a different story.. I have $$ 200x\equiv 13 \pmod {1001} $$ I got the inverse as $$ -5 $$ and then I multiply both sides with the inverse to get: $$ -1000x \equiv…
Rickz0rz
  • 71
  • 6
3
votes
2 answers

Algebra Word Problem: Distributing Juice

I am thinking through a word problem, which proceeds as follows: Mom distributed $L$ liters of juice among her $N$ sons. The first son distributed the contents of his pail evenly to the pails of the other $N-1$ sons. The second did the same, and…
Margaret
  • 33
3
votes
4 answers

a natural number that is both a perfect square and a perfect cube is a perfect sixth power?

I really can't get a grasp on how to prove this, because if $x$ = $\sqrt[6] n$ for some $n$, then $x^2$ = $a$ and $x^3$ = $b$, with $a$ and $b$ being different natural numbers right? Any help?
user3467433
  • 105
3
votes
1 answer

Big O Notation basics

Having some problems with big O notation question... getting confused on how to figure this out. I'm working on a problem (exam coming up so doing extra ones) where it asks us to arrange the functions in a list so that every function is big-O of the…
matthew
  • 31
3
votes
1 answer

a Maximum of Discrete Function

Define a set $$X=\{(x_1,\ldots ,x_n)\mid x_i=\pm 1,1\leq i\leq n\}$$ Fix $a$, $b\in X$. Consider the discrete function $$F(x_1,\ldots,x_n)=(x_1a_1+\cdots+x_na_n)^2+(x_1b_1+\cdots+x_nb_n)^2$$ $(x_1,\ldots,x_n)\in X$. I want to find when the function…
gaoxinge
  • 4,434
3
votes
1 answer

Empty set question

$$ | \{ \{ \} \} | = 0. $$ Is this true or false?
Betty
  • 107
3
votes
3 answers

Falling factorial counts permutations, what does rising factorial count?

Rising factorial example: Let $x = 7$ and $r = 4$. Then $7^{(4)} = 7(8)(9)(10) = 5040$. If we divide $7^{(4)}$ by $4!$ it counts multisubsets. But what kind of combinatorial problem does rising factorial solve on its own?
Kyle
  • 95
3
votes
5 answers

Prove that $ a^2-4b \neq2$ if $ a,b \in \mathbb{ Z}$

My solution : We suppose that is true. Then by contradiction: $a^2-4b-2=0$ $a^2=4b+2$ $a=2(b+1/2) ^{0.5}$ then $(b+1/2)$ is fraction and rooted by $0.5$ so the square root of any fraction $+$ any-Integer will give fraction so then $a$ must be…
Tandee Holwa
  • 319
1 2 3
…
99 100