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

average no. of color matches per position.

I've a problem whose solution is also stated below. I can't understand the explanation. There are two disks ,one smaller than the other, are each divided into 20 congruent sectors. In the larger disk,10 of the sectors are chosen arbitrarily and…
spectraa
  • 1,775
2
votes
1 answer

Average no. of objects in a box,when m objects are filled in n boxes.$(m>n)$

The formula for the average no. of objects in a box,when m objects are filled in n boxes $(m>n)$ is given by $[m/n]$ ,if $(m/n)\in \mathbb Z$ and $[m/n]+1$,if $(m/n)\notin \mathbb Z$ . The thing I can't understand is why in the second case did we…
spectraa
  • 1,775
2
votes
5 answers

Using Direct Proof. $1+2+3+\ldots+n = \frac{n(n + 1)}{2}$

I need help proving this statement. Any help would be great!
John
  • 57
  • 2
2
votes
2 answers

How many boolean functions $F(x, y, z)$

Question:How many boolean functions $F(x, y, z)$ are there so that $F(\bar{x}, y, z) = F(x, \bar{y}, z) = F(x, y, \bar{z})$ for all values of the Boolean variables $x, y,$ and $z$? I'm at loss on where to start.
Joey Andres
  • 143
2
votes
1 answer

Discrete Structures: Bit Strings

So my professor gave us an HW assignment which includes this question: "How many bit strings consist of 1 through 5 bits. (Note 10 and 00010 are considered distinct even though they are both representations for 2)" My answer is 62. Is this correct?…
user1069076
  • 21
2
votes
0 answers

What is the total number of magic squares for given N?

A magic square is a layout of the numbers $1,2, ..., n^2$ in a square of size n where the total of each row, column and diagonal is equal to $n(n^2+1)/2$. In the book 'The Zen of Magic Squares, Circles and Stars' by C. Pickover, on page 4, I read…
nilo de roock
  • 2,749
2
votes
1 answer

Expected Values

Let X be the number appearing on the first die when two fair dice are rolled, and let Y be the sum of the numbers appearing on the two dice. Show that E(X)E(Y) does not equal to E(XY). I found E(X) and E(Y) but I don't know how to find E(XY). The…
aralc
  • 35
2
votes
1 answer

Proof of series expansion of $f(k) = {r - sk \choose n}$ in Concrete Mathematics book by D. Knuth, et. al.

Please help me prove this equation in page 190 of Concrete Mathematics 2nd Ed. book by D. Knuth: $f(k) = {r - sk \choose n} = {1 \over n!}(-1)^n s^n k^n + ... = (-1)^n s^n {k \choose n} + ... $ I believe this is the Newton series of $f(k)$ since…
acegs
  • 258
2
votes
2 answers

What are $10^k \pmod 3$ and $n = \overline{a_ka_{k -1} \ldots a_1a_0}$?

I feel like I should know these concepts, but I don't.
Erbolat
  • 61
2
votes
1 answer

How many ordered pairs of integers $(a, b)$ are needed to guarantee that there are two ordered pairs $(a_1, b_1)$ and $(a_2, b_2)$ such that $\dots$

Question:How many ordered pairs of integers $(a, b)$ are needed to guarantee that there are two ordered pairs $(a_1, b_1)$ and $(a_2, b_2)$ such that $a_1 \bmod 5 = a_2 \bmod 5$ and $b_1 \bmod 5 = b_2 \bmod 5$? This is my first time with pigeon…
JoeyAndres
  • 1,269
2
votes
3 answers

Each user on a computer system has a password, which is six to eight characters long,$\dots$

Question: Each user on a computer system has a password, which is six to eight characters long, where each character is an upper-case letter or a digit. Each password must contain at least one digit. How many possible passwords are there? I'm in…
JoeyAndres
  • 1,269
2
votes
3 answers

Basic induction proof methods

so we're looking to prove $P(n)$ that $$1^2+2^3+\cdots+n^3 = (n(n+1)/2)^2$$ I know the basis step for $p(1)$ holds. We're going to assume $P(k)$ $$1^3+2^3+\cdots+k^3=(k(k+1)/2)^2$$ And we're looking to prove $P(k+1)$ What I've discerned from the…
Mike
  • 51
  • 2
  • 5
2
votes
1 answer

Minimum score for winner and maximum score for loser in a round-robin tournament.

I have just correctly solved this programming problem. The problem is the following: $N$ teams play a round-robin tournament, i.e. each pair of teams plays exactly one game and the winner gets 3 points, the loser gets 0 points, and both teams get 1…
Armen Tsirunyan
  • 869
2
votes
1 answer

Let $a_1=1$, $a_2=3$ , and for $n \ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < \left(\frac{7}{4}\right)^n$ for all natural numbers.

Let $a_1=1$, $a_2=3$ , and for $n \ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < \left(\frac{7}{4}\right)^n$ for all natural numbers. I assume I'm supposed to use induction. base step is easy. I'm stuck on how to form the inductive step. Any…
clay
  • 2,713
  • 23
  • 34
2
votes
1 answer

Which of the following 5 statements are true?

I am having trouble finding which of the following statements are true: Which of the following statements are true? [a] Pizza does NOT have mushrooms [b] Pizza does have mushrooms AND bacon [c] Pizza does have mushrooms OR bacon [d] Pizza does…
Eugen Mihailescu
  • 175
  • 1
  • 2
  • 8
1 2 3
…
99 100