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

Discrete Mathematics - Injective Function Justification

Good Evening Stack, I would just like to know whether or not I'm on the right track with this question as I'm having second thoughts about another possible interpretation. Question Define a function f : P({0, 1}) × P({1, 2}) → {0, 1, 2} by f((A, B))…
Liam Gannaway
  • 89
1
vote
0 answers

Does subtracting the sorted-digit version of a number repeatly always reach 0?

$s(x)$ is $x$ with digits sorted in increasing order, e.g. $s(452) = 245, s(604270) = 2467$. $$f(x) = x - s(x)$$ Does applying $f(x)$ repeatedly for any non-negative integer always reach a sorted-digit number? (after which the next step is $0$ as…
Wagner Martins
  • 537
1
vote
0 answers

Reproducing an ordered list of numbers from partial sums

Given a list of (not necessarily distinct) positive integers, $a=(a_1,...,a_n)$, can one reproduce the list (up to reversing the order, i.e. reproduce $(a_1,...,a_n)$ or $(a_n,...,a_1)$) from the underlying multiset, $\{a_1,a_2,...,a_n\}$ and the…
Ishaan Shah
  • 73
  • 6
1
vote
1 answer

How can you prove domains have more points than paths?

If we're given a computer program, how can I prove that there is a greater number of points in the domain than the number of paths? The question I am asked is "Which is larger? The number of paths in a program or the number of points in its…
biohack
  • 111
  • 2
1
vote
0 answers

Not sure how to work with a function which has the same finite domain and codomain.

Here's the problem set: Let A = {1,2,3,4,5,6}. In each of the following, give an example of a function f : A → A with the indicated properties, or explain why no such function exists. (a) f is bijective, but is not the identity function f(x) =…
chrisware
  • 71
1
vote
1 answer

Proof of the relationship between fibonacci numbers and pascal's triangle, without induction

http://s0.goldennumber.net/wp-content/uploads/pascals-triangle-fibonacci.gif I must prove, without induction, the relationship above is: $$\sum _{ k=0 }^{ \lfloor n/2\rfloor}{ \binom{n-k}k } ={F}_{n+1}$$ I understand how the equation works but I…
Justin
  • 13
1
vote
0 answers

Logic puzzle / propositional logic

I have this problem but I am stuck... we have three boxes - on each one, there is an inscription box1 - the magic recipe is here box2 - the magic recipe is not here box3 - the magic recipe is not in box1 assuming that $p,q,r$ are true only when the…
Terma
  • 23
1
vote
1 answer

Strong mathematical induction proof

Can someone please work me through this problem? Let $(f_0, f_1,f_2,...)$ be the Fibonacci sequence, that is, $f_0=0$, $f_1=1$, and $f_n = f_{n−2} + f_{n−1}$ for all $n\ge2$. Prove that $f_n>(5/4)^n$ for all integers $n\ge3$. I appreciate any kind…
time zone
  • 11
1
vote
1 answer

How to turn a piecewise function into a linear polynomial and absolute equation

Original Question Image Help! Does anybody know how to do part b? a) Let $a$ be a real number and consider the function $f:\mathbb R \to \mathbb R$ defined piecewise by $$f(x) := \begin{cases} x-a, & \text{if $x>a$}\\ 0, & \text{if $x\le…
ss7
  • 19
1
vote
1 answer

Find the remainder of 3^3^3...^3 divided by 46

Find the remainder of $3^{{{{{3^3}^3}^3}^3}^\cdots} \text{(2020 copies of 3)}$ by 46 Note that $a^{b^c}$ means $a^{(b^c)}$ not $(a^b)^c$ If there was 2 copies of 3: $3^3\equiv27 (mod 46)$. If there was 3 copies of…
routeRoute
  • 83
1
vote
1 answer

I am confused on how to find a function from a set that is also a 3-to-1 correspondence?

I have a homework problem that asks me to find a function from the set $\{1, 2, \ldots, 30\}$ to $\{1, 2, \ldots, 10\}$ that is a $3$-to-$1$ correspondence, I am confused on how to even derive a function from the sets that also are $3$-to-$1$…
Carrera
  • 11
1
vote
0 answers

Prove function is not onto

Let $f:\mathbb{R}^+ \to \mathbb{R}^+$ be given by $$f(x)=\frac{x + a}{x + b}.$$ The constants $a$ and $b$ must be evaluated to the following: $a$ is the sum of the first 4 digits of your student number $b$ is the product of the last two non-zero…
betty12340
  • 21
1
vote
1 answer

Question regarding set builder notation

I have a pair of variables $A_{i}B_{k}$, where $A_{i} \in \mathcal{A}$ and $B_{k} \in \mathcal{B}$. In the problem I am examining, I want to say that each such pair of variables, $A_{i}B_{k}$, is replaced with a corresponding set of elements, where…
E-O
  • 99
1
vote
2 answers

Prove that $pTq \longleftrightarrow |p| = |q|$ is Equivalence Relation on $A$ set of all point in the plane

I want to prove that this relation is equivalence relation on A $A$ set of all points in the plane $pTq \longleftrightarrow |p| = |q|$ , |p| is the distance from origin. about transitivity, there are counter-examples? for reflexivity is obvious,…
Ofir Attia
  • 3,136
1 2 3
…
99 100