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
1
vote
1 answer

Matrix invertible or not?

Given the matrix $A\in M_3(\mathbb{Z_6})$ $$ \begin{matrix} 5 & 3 & 3 \\ 1 & 4 & 1 \\ 3 & 5 & 1 \\ \end{matrix} $$ Is it invertible? $det(A)=4$ but $4$ is not invertible in $\mathbb{Z_6}$ so the matrix is not invertible, right?
user530133
  • 27
  • 3
1
vote
2 answers

Set of all symmetric and not reflexive relations

Let A be A={1,2,3}, let K be the set of all symmetric and not reflexive relations of A. Is K $$ K=\{(\phi,\phi)\quad((\phi,\phi),(1,2),(2,1))\quad ((\phi,\phi),(1,3),(3,1))\quad…
Arthur Losnikov
  • 83
1
vote
3 answers

Prove $xRy$ if $\exists \space k \in \mathbb{Z}(y+x=2k)$ is an equivalence relation

Given the binary relation $xRy$ defined in $\mathbb{Z}$ such that $\exists \space k \in \mathbb{Z}(y+x=2k)$. To prove that the relation $R$ is an equivalence relation, I must prove that $R$ is symmetric, reflexive and…
user24047
1
vote
1 answer

partial order, maximal but not greatest

How do I create a R over {a,b,c,d} such that a is maximal but not the greatest element? I know that something like R{(a,a)(b,b)(c,c)(d,d)}, all the element are maximal.
CJ408
  • 21
1
vote
1 answer

Number of non-equivalent five-digit numbers

Suppose that any two $n$-digit numbers are considered equivalent if it contains the same digits, but in a different order (eg. 34068, 03468 and 86304 are equivalent) How many five-digit numbers are not equivalent (leading digits allowed)? Given…
wybkqqnob
  • 75
1
vote
0 answers

A question about an antisymmetric relation.

A relation on the set $\{1,2,3,4\}$ is defined as: $$\{(1,1),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,3),(3,4)\}$$ We're supposed to determine whether or not this relation is reflexive, symmetric, antisymmetric and/or transitive. I concluded that this…
Mathijs Moonen
  • 29
1
vote
3 answers

Could anyone explain my prof's proof here for the induction of every natural number is congruent modulo 9 to the sum of its digits?

I don't get where the + 99...9dk + part comes from especially.
Doug Smith
  • 1,015
1
vote
1 answer

Composite function ...

Given the two functions: $$f: x \in \mathbb{Z} \to 4 - x \in \mathbb{Z}$$ $$g: y \in \mathbb{Z} \to |y| + 3 \in \mathbb{N}$$ The composite function is: $$g \circ f: |4 - x| + 3$$ Please tell me if it's correct, thanks.
Jon D
  • 63
1
vote
4 answers

Negating the statement

Suppose $a$ is a real number and that $f(x)$ is a real-valued function. In calculus, the statement "$f(x)$ is continuous at a" means that for every positive real number $E$, there exists a positive real number $\sigma$ such that for every…
merry-go-round-one
  • 220
1
vote
2 answers

Can someone explain what this paragraph is saying more clearly?

In the last bullet, it says l must be even and provides an explanation. I don't understand the explanation, however. Why does it have to be even?
Doug Smith
  • 1,015
1
vote
2 answers

Proving that $m^p-m$ is divisible by $p$

Let a prime number $p$ and a natural number $m$. Prove that $m^p-m$ is divisible by $p$. We were given a hint to use a multinomial coefficient. But I'm not really sure how it helps me. If I say that $m=1+1+...+1$ I get…
Nescio
  • 2,426
1
vote
2 answers

X ways to choose R objects in generating functions

I'm currently doing generating functions, and the purpose of those functions is to find how many ways there are to choose an x amount of objects. I just don't understand how they get to the final conclusion. Take for example this exercise: You have…
O'Niel
  • 239
1
vote
2 answers

Injection from $\mathbb{N}\to\{0,1\}$ to the set of all monotonic decreasing functions from $\mathbb{N}\to\mathbb{Z}$

I'm trying to think of such an injection, and unfortunately all of those I've thought about are not strictly decreasing. I would love to get some help or clues. Thank you :)
Noy
  • 777
1
vote
1 answer

Event and Sample Space - Discrete Math

Background information: I am studying events and subspaces, and I have a question about Events being a subset of the subspace. I am new to discrete mathematics, so sorry if I couldn't word my question more professionally. Logical Question:…
Agent 0
  • 669
1
vote
1 answer

How many ways are there in which you can put in order $10 A's$,$6 B's $ and $5 C's$ without having two successive B's alone

How many ways are there in which you can put in order $10 A's$,$6 B's $ and $5 C's$ without having two successive B's. When i say in order i mean something like that,example : AAAAAAAAAABBBBBCCCCCB.And what we dont want is to have any pairs of two…
Dimitris Papadimitriou
  • 95
1 2 3
…
99 100