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

Finding the coefficient of a polynomial

I want to find the coefficient of $x^{12}$of the following expression: $$(1+x^{2}+x^{4}+x^{6}+x^{8}+x^{10}+x^{12})(1+x^{4}+x^{8}+x^{12})(1+x^{6}+x^{12})(1+x^{8})(1+x^{10})(1+x^{12})$$ The question is: how can I do that without expading this…
Thiago
  • 698
  • 2
  • 8
  • 16
3
votes
2 answers

Proof By Counterexample, pigeonhole

This is from a discrete math homework question. I really don't know where to begin, except that I understand the concept of a proof by counterexample, just not how to get to it. In the statement of the pigeonhole, we argued that…
Marla
  • 153
3
votes
1 answer

Can you help me with this question about permutation?

Example: A garden has 4 types of flowers: roses, lilies, tulips and sunflowers. Flowers of the same type are considered identical. In how many ways can we make a bouquet of 10 flowers, if we must have at least 2 roses and 1 tulip? my answer:…
HWK
  • 33
  • 3
3
votes
1 answer

Concrete Mathematics: Josephus Problem for $J(n) = n/2$

On page 25 of the second edition I am at the section revisiting the initial guess of a closed form solution for the Josephus Problem. This initial, and incorrect, guess was that the solution is $n/2$. To lead us into this renewed discussion the book…
Friedrich 'Fred' Clausen
  • 387
  • 2
  • 12
3
votes
3 answers

Calculate the sum: $C_{2n}^n+2C_{2n-1}^n+4C_{2n-2}^n+...+2^nC_n^n$

Calculate this sum:$$C_{2n}^n+2C_{2n-1}^n+4C_{2n-2}^n+...+2^nC_n^n.$$ What I tried: $$ C^n_{2n}=\frac{(2n)!}{(n!)^2}$$ $$ 2C^n_{2n-1}=\frac{2(2n-1)!}{n!(n-1)!}=\frac{2n(2n)!}{n!n!(2n)}=\frac{(2n)!}{(n!)^2}$$ $$…
Belen
  • 568
3
votes
3 answers

Can there exists three sets: $A \subset B$, $B \in C$, $A \in C$

Can there exists three sets: $A \subset B$, $B \in C$, $A \in C$, if not, why not?, if yes, give an example. My example: A={$a,b$} B={$a,b,c$} C={{$a,b$},{$a,b,c$}} Is this all? It seems this is a tricky question and there's something I'm missing.…
Belen
  • 568
3
votes
2 answers

Determining the size of power sets

A very elementary question: Let $|A|=a$, and $|B|=b$. What's $|\mathcal P(\mathcal P(\mathcal P(A \times B \times \varnothing)))|$? So how I got stuck on it: I'm not sure what's the number of pairs that a generic $A \times B$ gives, and what's $A…
ohad
  • 243
  • 2
  • 8
3
votes
5 answers

There exists a prime $p$ such that $p \mid n$ for all $n \in\mathbb N$, $n > 1$

My textbook asks these following true or false questions but provides two different answers even though, in my opinion, the questions are asking the exact same thing. Could someone explain how the questions are different? True or False? (a) For all…
Liam
  • 29
3
votes
3 answers

Find G. C. F. of $(8n^3 + 8n, 2n+1)$

I'm stuck with this problem, I divided $8n^3 + 8n$ by $2n+1$ and obtained $5$, so now my G. C. F is $\gcd(2n+1, -5)$. What's next? I can't divide $2n+1$ by $-5$.
John
  • 51
3
votes
0 answers

Prove that $\mathcal{P}(A)\cap\mathcal{P}(B)\subseteq\mathcal{P}(A\cap B)$ for all $A, B$

Problem. Prove that $\mathcal{P}(A)\cap\mathcal{P}(B)\subseteq\mathcal{P}(A\cap B)$ for all $A, B$ This is what I have so far but not sure if it's right. Let $X \in \mathcal{P}(A \cap B)$. Then each element of $X$ is an element of $A$ and $B$,…
michael
  • 41
3
votes
1 answer

$\sum_{x=0}^{\infty}\frac{(r+x+m-1)!}{(r+m-1)!x!}(1-p)^{x}$

How to simplify given series $$\sum_{x=0}^{\infty}\frac{(r+x+m-1)!}{(r+m-1)!x!}(1-p)^{x}$$ My solution: $y=r+m-1$ $q=1-p$ $$\sum_{x=0}^{\infty}\frac{(y+x)!}{y!x!}(1-p)^{x}$$ $1+(y+1)q+\frac{(y+2)(y+1)q^2}{2}+......$ $(1-q)^{-(y+1)}$
TLE
  • 1,025
3
votes
3 answers

Cardinality of Cartesian Product where (a,b) are elements of A x B

I'm having issues with a question regarding the cardinality of a cartesian product. Question: Let $A=\{0, 1, 2, 3, 4, 5, 7\}$ and $B=\{0, 2, 4, −1, 12\}.$ How many elements are in $\{(a, b) ∈ A × B \; | \; a < 7 \text{ and } b < 4\}$? I want this…
Metal Mike
  • 33
3
votes
2 answers

Trying to convert 34.2111 (decimal) to binary in a faster way

I tried this before here Convert 34.2111 (decimal) to binary and now I am trying again in a different way. When you have to convert base a to b where b is a^n you know that n digits of the number in base a = 1 digit in base b. In this case 10 isn't…
SilenceOnTheWire
  • 419
3
votes
4 answers

Determine whether (¬p ∧ (p → q)) → ¬q is a tautology.

The answer is not a tautology. I know the answer based on the true table, however I wanna try another method. Here is my method: (¬p ∧ (p → q)) → ¬q ≡ ¬(¬p∧(¬p∨q))∨¬q ≡p∨(p∧¬q)∨¬q ≡((p∨p)∧(p∨¬q))∨¬q Which part am I wrong?Thanks for your explanation!
Peter Hsieh
  • 75
3
votes
1 answer

Discrete math -- equivalence relations

I've been learning about equivalence relations in my discrete math class. I understand that equivalence relations are relations that are symmetric, reflexive, and transitive. I also learned about the equivalent class and the quotient set. However,…
Frodo Baggins
  • 89
1 2 3
…
99 100