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

Proofs by induction

Let $R$ and $S$ be relations such that $R \subseteq S$. Prove that $R^n \subseteq S^n$ for all positive integers $n$. If $ R$ be a symmetric relation. Prove that $R^n$ is symmetric for all positive integers $n$. This just seems strange…
Dimitri
  • 1,287
1
vote
2 answers

Determine how many seating arrangements are possible using discrete math

There are 10 students in the class and 10 seats in the classroom, and each student sits in the same seat during every lesson. However, the teacher insists that no student sit in their "usual" seat during an exam. How many different seating…
user3003255
  • 107
  • 1
  • 1
  • 4
1
vote
2 answers

Integer solutions to $c=a^2-b^2$

I have been working on the following problem: For a given $c\in \Bbb Z^+$, find $a,b \in \Bbb Z^+: c=a^2-b^2$. I have already figured out and proved a number of things: A way to directly determine if a particular instance is solvable: $\exists…
AJMansfield
  • 1,025
1
vote
5 answers

How many different combinations of pennies, nickels, dimes, quarters, and half dollars can a piggy bank contain if it has 20 coins in it?

How many different combinations of pennies, nickels, dimes, quarters, and half dollars can a piggy bank contain if it has 20 coins in it?
aaaashasha
  • 243
  • 3
  • 6
  • 12
1
vote
1 answer

How many spanning trees are contained in $G$?

Find the number of spanning trees contained in $G$. The graph $G$ has vertex set $V = \{v_1,\ldots,v_8\}$ and edge set $E = \{e_1,\ldots,e_{10}\}$, where $e_1 = \{v_1, v_2\}$, $e_2 = \{v_2, v_3\}$, $e_3 = \{v_2, v_4\}$, $e_4 = \{v_3, v_4\}$, $e_5 =…
user3003255
  • 107
  • 1
  • 1
  • 4
1
vote
1 answer

discrete mathematics problem

How many ways are there for 10 women and six men to stand in a line so that no two men stand next to each other? [Hint: First position the women and then consider possible positions for the men.]
ali
  • 147
  • 1
  • 3
  • 9
1
vote
5 answers

Prove $13|19^n-6^n$ by congruences

I am trying to prove $13|19^n-6^n$. With induction its not so bad but by congruences its quite difficult to know how to get started. Any hints?
Mark
  • 335
1
vote
1 answer

Determine the equivalence relation on {1, 2, 3, 4}

If the relation is an equivalence relation, list the equivalence classes. $$\{(x, y) : 4 \mid x - y\}$$ I have no clue how to solve this. What I have tried is: To know its an equivalence relation, it has to be reflexive, symmetric and transitive. So…
user3000730
  • 11
1
vote
1 answer

Closed-form formula

Show (not by giving a $(c,k)$ pair but in some other way) that the sum of the squares of the first $n$ odd positive integers is of order $n3$. I.e. is that sum $\Theta(n3)$? Hint: Try to find a closed-form formula for that summation. That will take…
user111557
  • 19
1
vote
1 answer

Boolean functions with $3$ variables

Is it true or false that the total number of boolean functions with $3$ variables is $255$? ${2^2}^3$ is $256$ so this statement is false.
Kevin
  • 35
1
vote
2 answers

Solution Check: Union/intersect complement

This a true/false question. For set operations, we always can replace Union by intersection and complement operation. I think what it is saying is that if A U B, you can swap U with intersect and complement that so they are equal which is obviously…
Kevin
  • 35
1
vote
1 answer

recursive formula for bit binary strings

Find a recursive formula for the number of n bit binary strings that contain the substring 10. How many such strings of length 8 exist? Find a closed form for the number of n bit binary strings that contain the substring 10. i know i have to count…
lahela
  • 11
  • 3
1
vote
1 answer

Proving harmonic statement with induction

So I learnt induction just last week and now practicing, and I have run across a question that has stumped me. Prove that ($2$ is really small, sorry for improper formatting) $H_{2^k}\geq k+1$; I had started with basis step where for $k=1$ was true,…
user7349
  • 143
  • 1
  • 1
  • 5
1
vote
1 answer

Symmetric and Antisymmetric Relations

I'm trying to figure out how a relation can be both antisymmetric and symmetric simultaneously. And how is antisymmetric different from NOT symmetric. Is the easiest way to answer this is by graphing? I'm trying to come up with such a relation but…
Dimitri
  • 1,287
1
vote
1 answer

Discrete Mathematics/SETS

Consider $G$ be an abelian group with $A$ and $B$ are subsets of $G$. Consider $$A + B = \{a + b: a\in A, b \in B\},\quad A - B = \{a - b: a\in A, b\in B\}$$ If $A = B$, we have $A + A = \{a + a': a, a'\in A\}$ and $A - A = \{a - a': a, a'\in A\}$.…
Gandhi
  • 575
1 2 3
…
99 100