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
0 answers

Let A be a set with k elements and P(A) its power set show that the cardinlity of P (A) is $2^k$.

I know it's pretty basic and I feel pretty dumb about asking this question but I can't help myself solving it correctly.
2
votes
1 answer

Shortest Way to Represent Every 3 Digit String

Today, I was thinking about random stuff like I sometimes do. I thought of an interesting question that I have no clue how to solve. It started with me thinking about taking all 3 letter strings ("words"), and putting them through a profanity…
Ryoma
  • 23
2
votes
1 answer

Find six red numbers from 36 (for sure)

Anna colors exactly 30 numbers to red from the numbers $1,2,\dots, 36$. Then Peter is able to choose six numbers from the 36 (this is called a step). After $n$ steps, for each of the steps, Anna tells if all the chosen numbers (the six chosen…
Pet123
  • 1,252
2
votes
1 answer

How would i draw a graph given a specific degree sequence?

For example, I have a degree sequence (4,3,3,1,1,1,1) and I want to draw its graph. I know that it will have 7 edges, put I can't seem to put the graw together. Thanks!
2
votes
0 answers

Are there any formulas that compute the coordinate of the spiral numbers

Just like the title I want to ask about formula for $n \times n$ spiral matrix. In particular, I want to know if there's a formula for a given entry in the matrix, without computing the full matrix. Here is an example of the kind of matrix I'm…
2
votes
2 answers

Direct ceiling proof

I'm stuck on this for quite of few hours now. Can someone please explain me how would I prove this? TIA $\lceil x + n \rceil = \lceil x \rceil + n $ (x is a real number and n is an integer)
2
votes
2 answers

How many solutions for the equation $t_1+t_2+t_3+t_4=6$

How many solutions are there to the equation $t_1+t_2+t_3+t_4=6$ if $t_i\in \{-1,0,1,2,3,4,5,6,7,8,9\}$ for all $i=1,2,3,4$? I know how to answer this problem without the set of numbers $t_i$. But when I should keep the set $t_i$ in mind, I don't…
user530832
2
votes
1 answer

Contradiction and proofs

the problem is verify this statement: $$\lnot ( \lnot p \land q)^\land (p \lor q)=p$$ That turns into $p \lor ( \lnot q \land q)$ - which that last part of the statement is a contradiction and is always false which means now I have $p \lor F…
2
votes
2 answers

How many rounds in a tournament with n players

I am stuck on the following question... Suppose n people are playing in a tournament where n is a power of two so that it creates an even bracket. In the first round each player is paired with another player, only the winner of each pair go on to…
user525203
2
votes
1 answer

Why is $x^2$ surjective from $\Bbb R \to \Bbb R^+ \cup \{0\}$ but not surjective without $0$

I am wondering why $x^2$ is surjective if the domain and codomain is $\Bbb R \to \Bbb R^+ \cup \{0\}$ but not surjective without $0$. If we remove $0$ all the numbers in $y$ would still be in $x$ since $x$ is all reals anyway? So what I mean is,…
user504783
2
votes
0 answers

Path in a directed graph

Let $G$ be a directed graph with $2^k$ vertices where there is exactly one edge between each two vertices. Prove that that regardless of the directions (orientations) of the edges there exist a path in $G$ which goes through $k+1$ unique vertices. I…
jerrieto
  • 133
2
votes
4 answers

All possible solutions for $x_1+x_2+x_3=25$ with conditions for $x_1, x_2$ and $x_3$ ranges

Find all possible solutions for $x_1+x_2+x_3=25$. Numbers have to fulfill the following conditions: $0 \leq x_1 \leq 5, 2 < x_2 \leq 10$ and $5 \leq x_3 \leq 15$. Solutions $(a,b,c)$ and $(b,a,c)$ are considered different. $x_1, x_2$ and $x_3$ are…
Maria
  • 157
2
votes
2 answers

Discrete Math distinct words

I am asked this: "Let m, n, and r be non-negative integers. How many distinct "words" are there consisting of m occurrences of the letter A, n occurrences of the letter B, r occurrences of the letter C, such that no subword of the form CC…
Nick
  • 489
2
votes
1 answer

How many ways can 8 boys and 8 girls be paired

I am trying to figure out how many combinations you can get if $8$ boys are paired up with $8$ girls. I was thinking it could possibly be something like $8!$ or $8! \cdot 8!$. Something with factorials but I'm not sure.
user510622
2
votes
3 answers

one-to-one correspondence between words an numbers

How can I show that the set of all words using the letters a, b, and c are countable? The hint I was given says to establish a one-to-one correspondence with non-negative integers but I am not following the reason why.