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

If $n$ is an integer then $n^2$ is the same as $0$ or $1\pmod 4$?

I have been stuck on this problem for awhile. How would i go about solving it, an explanation would be helpful as well. Show that if $n$ is an integer then $n^2 \equiv 0$ or $1 \pmod 4$?
aaron
  • 71
2
votes
1 answer

a Maximum of Discrete Function 2

I have asked a question about a maximum of discrete function yesterday at a Maximum of Discrete Function. I want to generalize the question. Let $X=\{(x_1,\ldots ,x_n)\mid x_i=\pm 1,1\leq i\leq n\}$. Fix $\vec{a}_1,\cdots,\vec{a}_m\in X$. Consider…
gaoxinge
  • 4,434
2
votes
0 answers

Bijective function between lists and sets

How many eight-bit strings have exactly three $1$’s? The answer is $8\choose 3$. Since we count subsets here, how can we set up a one-to-one correspondence between any $8$bit list with only three $1$s and some set? Consider the list $11100000$.…
Ace
  • 23
2
votes
2 answers

Discrete math: $a_n=14a_{n−1}−33a_{n−2}$ for $n≥3$ with initial conditions $a_0=−24,a_1=−200$

Can someone please help me understand this? This is what I got but it isn't correct. $a_n=14a_{n−1}−33a_{n−2}$ for $n≥3$ with initial conditions $a_0=−24,a_1=−200$. Solve for $a_n$. $t^2 = -14t+33$ $r_1=-11$ $r_2= -3$ $n_0 = M(-11)^0 + N(-3)^0 =…
user3395349
  • 69
2
votes
1 answer

Need a closed formula for the generating function $x/(1+x+x^2)$.

I used partial fractions but the obtained formula is only correct for the first two elements. $\dfrac{x}{(1+x+x^2)}=\dfrac{x}{(1+a_1x)(1+a_2x)}=\dfrac{A_1}{(1+a_1x)+A_2(1+a_2x)}$ $x=\dfrac{-1 \pm\sqrt3i}{2}$ Then let $a_1=\dfrac{-1+\sqrt3i}{2}$…
jjstef
  • 21
2
votes
1 answer

Spread out the zeros in a binary sequence

Suppose I have a machine that processes units at a fixed rate. If I want to run it at a lower rate, I have to leave gaps in the infeed. For example, if you want to process 3/4, then you would feed in 3, leave a gap, then repeat. This could be…
wxffles
  • 319
  • 2
  • 9
2
votes
2 answers

Show that the average depth of a leaf in a binary tree with n vertices is $ \Omega(\log n)$.

Let $T$ be a tree with$n$ vertices, having height $h$. If there are any internal vertices in $T$ at levels less than $h — 1$ that do not have two children, take a leaf at level $h$ and move it to be such a missing child. This only lowers the average…
ZWHmepsy
  • 29
2
votes
2 answers

Given a set S of ten positive real numbers whose product is 32, show that S contains six numbers whose product is at least 8.

Given a set $S$ of ten positive real numbers whose product is $32$, show that $S$ contains six numbers whose product is at least $8$? I tried to prove it, but it seems that the question is ambiguous. Say, consider a set of six numbers. If their…
anand konjengbam
  • 21
2
votes
1 answer

Show that if n and K are poitive numbes then

Show that if $n$ and $k$ are positive integers, then $ {n+1 \choose k}= \frac{(n+1) {n \choose k-1} }{k}$ I am most likely doing this wrong, but here is what I have: There exist integer $a$ such that $2a$ is positive; $ {2a+1 \choose 2a}=…
Bobshark
  • 25
2
votes
1 answer

Prove that a number with 30 digits cannot have more than 100 prime factors.

I know that the a number with more than 100 prime factors must be larger than $2 ^ {100}$, so it must have more than 30 digits but i am having trouble with proof. I was given Hint: every prime number is $≥ 2$. Can someone help me connect the two…
user240650
  • 21
2
votes
1 answer

Find the union of of the following family or indexed collection

this question was posted but I did not understand the solution. For each natural number n, let An = {5n, 5n+1, 5n+2,...,6n}. And let A = {An: n is an element of the natural numbers}. Here is where I am: An = {5, 6, 7, 8, 9, 10,...} So U An = {5, 6,…
user224758
  • 33
2
votes
1 answer

Determining matrix for relationship: reflexive, symmetric, transitive.

I have two matrices below and need to determine if R is (a) reflexive, (b) symmetric, and (c) transitive. $M_R = \begin{pmatrix} 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1\end{pmatrix}$ ; $M_R = \begin{pmatrix} 1 & 1 & 1 & 1\\ 0…
PeaceKing
  • 67
2
votes
1 answer

Defining n-fold Composition of f with itself.

This is a question on the test review packet I have for discrete mathematics. Given: $f = \{(a, b), (b, a), (c, b)\}$ a function from $X = \{a, b, c\}$ to $X.$ (a) Write $f \circ f$ and $f \circ f \circ f$ as sets of ordered pairs. (b) Define $f^n…
wazy
  • 127
2
votes
1 answer

Infinite Pigeonhole Proof?

Suppose we arrange finitely many pigeons in infinitely many pigeon holes. How do I use the Infinite Pigeonhole Principle to prove that there are infinitely many pigeonholes that contain no pigeons.
Ray
  • 21
2
votes
1 answer

proving property of polynomial that is composite

Show that $a^m+1$ is composite if $a$ and $m$ are integers greater than 1 and $m$ is odd. [$Hint:$ Show that $x+1$ is a factor of the polynomial $x^m+1$] So I tried doing it and got a result which seems erroneous. let $m = 2k+1$, so $a^m+1 =…
demalegabi
  • 421
1 2 3
…
99 100