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

how many x contain atleast one y

Description A group of 5 animals is to be chosen from 6 cats and 4 dogs. Question how many groups contain at least one dog? Working Out There are at most 4 dogs, so a group of 1 dog and 4 cats meet the condition as does a group of 2 dogs and 3 cats,…
1
vote
2 answers

Discrete mathematics: meaning of "g" in finite-state machines with output

I'm looking on an example from my book of discrete mathematics and I've been reading a lot about these finite-state machines with output, however there is one thing I just still can't figure out. The example is here: When looking at the first state…
Peterrr
  • 13
1
vote
1 answer

arrangement of numbers so that a condition is satisfied...

In how many ways can we arrange the numbers $1,2, \dots, 3n (n \geq 1)$, so that, at the positions that are multiple of $3$, there are only numbers that are multiple of $3$? I thought that the answer is: $$\binom{3n}{n} \cdot n! \cdot (2n)!$$ Could…
evinda
  • 7,823
1
vote
4 answers

Discrete math and integer solutions problem

How do we find the number of nonnegative integer solutions of the inequality: $$x_1 + x_2 + \cdots + x_6 < 10\text{ ?}$$ Answer is $5005$, can someone elaborate and show me the steps required to solve this discrete math problem?
Ash
  • 31
1
vote
1 answer

What is a strictly increasing sequence in discrete math?

Consider selecting $3$ objects from the set $A = \{ 1,2,3,4,5,6\}$, how many strictly increasing sequences can be chosen from $A$? Answer is $C_3^6$, but my problem is that I don't know what it means by strictly increasing and how to get the answer…
Joe
  • 13
1
vote
1 answer

Number of nonzero intersections with translated sets

Suppose we have two finite sets $A,B\subset\mathbb Z$. I am interested in an upper bound on the number of translations of $B$ by integers that have nonzero intersections with $A$ i.e. $$T(A,B):=\lvert\{k\in\mathbb…
Dominik
  • 434
  • 2
  • 11
1
vote
2 answers

Discrete Mathematics: Pigeonhole principle?

Problem: The squares in the $3$ (columns) by $7$ (rows) grid are colored black and white. Can we guarantee that the board contains a rectangle (of size $n \times 2$ or $n\times 3$, with $n >1$) whose four corner squares are all black or all…
1
vote
0 answers

Prove Equivalence relation and Finding Equivalence classes

Let A = {1,2,3,4,5,6,7,8,9,10,11,12} and let R be the relation on set A defined by for any elements m and n in A, m R n iff m is congruent to n (mod 5). 1/ Why is R an equivalence relation? 2/ Find the equivalence classes determined by R. My…
1
vote
2 answers

Proof about sets, Cartesian Product

Can someone please explain this answer to me with a graphical representation or just a have a better explanation than this? I would really appreciate it, please, Thanks
1
vote
1 answer

Problem of monkey and leaves

There are $n$ leaves placed in a circle. A monkey travels around it in a peculiar manner. On his $1^{st}$ jumps he skips one leaf and lands on the other. On the next jump he skips two. Then he skips three and so on. Prove that if he has to land in…
Ruddie
  • 436
1
vote
1 answer

Prove irregularity of language using Myhill-Nerode Theorem

I am having trouble proving the irregularity of the following language: $L_2 = \{a^n | n \text{ is not a prime}\}$ I understand that since regular languages are closed under complementation, L_2 isn't regular if it's complement isn't regular. I'm…
1
vote
2 answers

Discrete Mathematics-Relations

How can I test the properties of the following relation: R={((a,b),(c,d)): ad=bd } where a,b,c and d real numbers. We used to test the properties for only two variables!! Please anyone have any idea??? Thank you.
user149143
1
vote
1 answer

Recurrence Relation for binary sequences

How can I find the recurrence relation with a) no block of 2 consecutive 0's and b)no block of 3 consecutive 0's. Please help me understand this material, detailed explanation will be much appreciated, Thanks
1
vote
1 answer

Recurrence Relation Poker Chips

I am assuming that the recurrence relation for a) would be $a_n = a_{n-1} + a_{n-2}+ a_{n-3}$. Correct me if I'm wrong. And I have no idea to what the answer for B is. I would really appreciate it if you provide a detailed explanation on how this…
1
vote
1 answer

Recurrence Finance Relation

A student visits an ice cream store once a day. During each visit he buys either a banana split for three dollars or a frozen yogurt in one of two possible flavors for two dollars. Find a recurrence relation for the number of ways, to spend n…