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
4
votes
2 answers

Discrete math: How many solutions are there?

I wrote a prolog program to print out all of the possible solutions for the following problem: You have eight colored balls: 1 black, 2 white, 2 red and 3 green. The balls in positions 2 and 3 are not green. The balls in positions 4 and 8 are the…
iltp21
4
votes
5 answers

is the sum of the square of two real numbers greater than or equal to twice the product of the two real numbers?

I'm learning how to write proofs and cant seem to figure out how to do this one. Specifically Im interested if it is possible to prove the inequality by contradiction, contraposition, or by a direct proof; or if its possible at all.
Curtis
  • 73
4
votes
1 answer

what is the possible number of commutative binary operations that can be defined on a set of n elements?

Please guide the approach , If we have to find commutative operations , then what will the cardinality of the set which would be mapped to a set with $n$ elements ,since for calculating total no of binary operations we have a mapping defined from…
radhika
  • 361
4
votes
3 answers

Prove $\{\varnothing \} \neq \varnothing$

I know this statement $$\{\varnothing \} \neq \varnothing$$ is true because { $\varnothing $} $\subsetneq \varnothing$ since $ \varnothing \notin \varnothing $. Is this true?
Lily
  • 395
4
votes
2 answers

Find largest dividing integer within range

Is there a neat way to find the largest integer that divides another integer fully, within a range. As an example, I would like to find the largest integer smaller than 1131 that divides 3500 completely. So far I have just tried by breaking up 3500…
Filip Nilsson
  • 111
4
votes
1 answer

Proving that every product of $n$ consecutive integers contains its prime factors at least as many times as $n!$ does

In response to a request by @Ari for a proof by induction that the product of $n$ consecutive integers is divisible by $n!$, I attempted what I thought was an argument more plain and direct. Taking a product of $n$ consecutive integers…
Edward Porcella
  • 3,940
  • 2
  • 11
  • 15
4
votes
2 answers

Classic Hand shake question

I am asked the following question: My wife and I were invited to a party attended by four other husband-wife couples, making a total of ten people. As people arrived, there was some hand shaking. No one shook their own hand, and there were no…
Nick
  • 489
4
votes
3 answers

Russell's paradox: a set cannot contain its own powerset

I've been trying to challenge myself but with no luck. Maybe one of you will have a better idea. How can it be proven that there can't be a set which contains its own powerset, using only russell's paradox? I've managed to prove it with other…
Discreter1203
  • 109
4
votes
2 answers

Show the coefficient of $x^3$ in the expansion of $(1+x+x^2+x^3)(1+x^2)(1+x^3)$ is the same as the number of partitions of $3$

(let a partition of $n \in \Bbb N, n>0 $ be a sum of positive integers) How would you show that the number of different partitions of $3$ is the coefficient of $x^3$ in the expansion of: $(1+x+x^2+x^3)(1+x^2)(1+x^3)?$ My attempt: since there are…
Desmoz
  • 362
4
votes
1 answer

Creating a McCarthy 91 function that returns values other than 91?

The McCarthy Function is the following: $M\left(n\right)=\left\{n-10\:\:\:\:\:\:if\:n\:>100\:\right\}$ and $M\left(n\right)=\left\{M\left(M\left(n+11\right)\right)\:\:\:if\:n\:\le 100\:\right\}$ For any integers $n\:\le 100$, $91$ is returned. It's…
Chris T
  • 813
4
votes
2 answers

Prove that $n! + k$ is a composite number

Recall that if $n$ is a positive integer, $n! = n(n-1)\cdots 3\cdot2\cdot1$. a) Let $n$, $k$ be positive integers with $1< k \le n$. Prove that $n! + k$ is composite. b) Using part a, find $100$ consecutive integers all of which are composite. c) In…
math
  • 49
4
votes
3 answers

How many functions are there from $\mathbb Z$ to $\mathbb Z$?

Repeating the question, How many functions are there from $\mathbb Z$ to $\mathbb Z$? A function $f \colon A \to B$ is a subset of $A \times B$ satisfying $$(a,b) = (a,c) \qquad \Rightarrow \qquad b = c,$$ so it's enough (maybe) to look at subsets…
user369210
  • 1,339
4
votes
1 answer

What does mean weaker and stronger terms in logic?

I want to understand what does mean the terms stronger and weaker which I'm reading in Programming: The Derivation of Algorithms: When $[P\Rightarrow Q]$ holds then $P$ is called stronger than $Q$ and $Q$ is called weaker than $P$. For example,…
InfZero
  • 875
4
votes
1 answer

Is the set of all trees currently on earth finite, countably infinite, or uncountable?

I'm not sure how to prove this as my professor has not shown any proofs involving real world objects, but I believe that it is finite since we know that there exists an integer k = the number of trees on earth. So we can call set B = {1, 2, 3, 4,…
ComputerScience1994
  • 103
4
votes
2 answers

What are the differences between empty set, zero set and null set?

What are the differences between empty set, zero set and null set? If i'm right empty set and null set is the same which is {} but zero set is {0} ?
mika
  • 857
1 2 3
…
99 100