Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
0answers
21 views

Simplification of a dervived binary tree with n nodes [duplicate]

hi I need help with this problem how do simplify this equation and what are the steps and approaches to this problem
1
vote
2answers
407 views

Monotonic Lattice Paths and Catalan numbers

Can someone give me a cleaner and better explained proof that the number of monotonic paths in an $n\times n$ lattice is given by ${2n\choose n} - {2n\choose n+1}$ than Wikipedia I do not understand ...
0
votes
4answers
113 views

the probability of guessing a number [closed]

Choose any natural number. For example I would choose: 3852011231231280130218920382342312420234801232321241231212131234 (and so for for another few bilions of digits) What's the probability that ...
0
votes
1answer
86 views

Graph with 5 vertices - # of spanning trees

If a graph has 5 vertices, all of them connected to each other vertex, how many different spanning trees exist? I'm thinking the answer might be $4*3*2$, because the first point has 4 options to go ...
0
votes
3answers
43 views

Prove that the set of all arithmetic progressions is a countable.

I just didn't have an idea of how to solve this problem. Prove that the set of all arithmetic progressions is a countable. Thanks in advance for any assistance.
1
vote
1answer
112 views

Prove that a countable set of parabolas $\alpha (y-\beta)^2+\gamma=x$, for $\alpha, \beta, \gamma \in \Bbb R$, doesn't cover the entire $xy$ plane

A question I found hard to solve. Prove that a countable set of parabolas $\alpha (y-\beta)^2+\gamma=x$, for $\alpha, \beta, \gamma \in \Bbb R$, doesn't cover the entire $xy$ plane Thanks in ...
1
vote
1answer
90 views

Generating functions of partition numbers

I don't understand at all why: \begin{equation} \sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1} \end{equation} Where $p_n$ is the number of partitions of $n$. Specifically ...
1
vote
2answers
383 views

Prove logical equivalence

\begin{gather} (p \to q) \equiv (\lnot p \lor q) \\ \lnot(p \land q) \equiv (\lnot p \lor \lnot q) \end{gather} Can these be proven without truth tables?
-2
votes
1answer
130 views

How to write a recursive algorithm?

Write a recursive algorithm SUM(A,k) that can be used to calculate the summation $\sum_{k=0}^na_k$ , where $\{a_0,a_1,a_2,…,a_n \}$ is an arbitrary (given) sequence of numbers stored in array A. Use ...
0
votes
0answers
32 views

Expected number of generations

Consider the following simplistic model of transitions between social classes as defined by Sociologists. Only males are considered, and by assumption every male has exactly one son. Let Xn denote the ...
0
votes
2answers
123 views

Domain of a Relation from A to B

The latest versions of Susanna S. Epp's Discrete Mathematics book (both the First Brief Edition, and the full Applications 4th edition) define a relation from $\mathcal{A}$ to $\mathcal{B}$ as a ...
1
vote
1answer
55 views

How do i find the matrix iteration sequence?

Matrix: $$ A=\left(\begin{matrix} 25 & 8 \\ 10 & 30 \end{matrix}\right) $$ Iteration sequence: $$ \begin{align*} x_{n+1}&=Ax_n, & x_0 &= \left(\begin{matrix} 1 \\ 90 ...
3
votes
2answers
78 views

Probability distribution of product of integers

I have a scoring system based on 5 factors with integer values from 1 to 5: Score = A * B * C * D * E So the Score can range from 1 to 3125. Each of the factors ...
2
votes
2answers
77 views

Is there a tutorial that uses english to form an example of a proof, or a very simple way to show how a proof works?

I am in a discrete math in college and would like to understand proofs. I had to prove the fundamental theorem of calculus in Calc 1, and did horribly in Linear algebra because of proofs. How does one ...
1
vote
2answers
161 views

Function - Test of Transitivity

Relation R in the set N of natural numbers defined as R = $\{(x, y): y = x + 5 $and $x < 4\}$ We can make set : (1,6)(2,7)(3,8) Is this a transitive function please guide..
0
votes
1answer
50 views

Random variables and permutations [duplicate]

I'm trying find the number of ordered triples of non-negative integers $a, b, c$ whose sum $a + b + c$ is a given positive integer $n$. I've related it to the concept of distinguishable balls in ...
2
votes
1answer
138 views

Ackermann’s function $A(m,n)$

Please show the shortest steps possible. thanks. \begin{align*} A(0, n) &= n + 1,\ n \geq 0;\\ A(m, 0) &= A(m − 1, 1),\ m > 0;\ \text{and}\\ A(m, n) &= A(m − ...
3
votes
6answers
1k views

Arithmetic with Large modular exponent and repeated squaring, such as $10^{221}$ (mod $13$).

How would you compute $10^{221}$ mod $13$ by repeated squaring? I just started studying discrete mathematics and I think this would help me in the future. I looked at this example Computing large ...
1
vote
3answers
192 views

Computing large modular numbers

How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, ...
3
votes
2answers
173 views

Seating Multiple People at Multiple Tables

In how many ways can we seat 100 people around 20 different circular tables in such a way that there are five people per table? Am I right in assuming that we're only considering unique ...
3
votes
2answers
58 views

Modular Exponentiation

Give numbers $x,y,z$ such that $y \equiv z \pmod{5}$ but $x^y \not\equiv x^z \pmod{5}$ I'm just learning modular arithmetic and this questions has me puzzled. Any help with explanation would be ...
2
votes
2answers
100 views

Probability of Choosing a Card from a Deck

There were quite a few deck of cards probability problems and I went through a few but couldn't find anything close so please forgive me if this is a repeat. The question is as follows: Two cards ...
0
votes
2answers
49 views

How to Count Possible Orderings of Digits with Required Substrings

The question is as follows: How many orderings of the digits from 1 to 8 contain the sub-strings 12, 23 or 34? For example, 57238614 is one such ordering since 23 appears, and 12345678 works, ...
1
vote
2answers
81 views

How can be done by the method of mathematical induction?

We are given that $P(x+1)-P(x)=2x+1$ We also know that $P(0)=1$ We want to prove that $P(2004)=(2004)^2 +1$ Can someone explain how can be solved with mathematical induction? Thank you in advance!
2
votes
3answers
91 views

Solve for $x$: $4x = 6~(\mod 5)$

Solve for $x$: $4x = 6(mod~5)$ Here is my solution: From the definition of modulus, we can write the above as $ \large\frac{4x-6}{5} = \small k$, where $k$ is the remainder resulting from ...
1
vote
2answers
122 views

Strategies to solve congruence problems

Which strategy is best to use when solving problems of the following sort? $$x^{29} \equiv 3\pmod {184}$$
1
vote
2answers
39 views

Do not understand what this question is asking… or the notation, Discrete Structures/Relations

Let X = {1,2,....,10} Define a relation R on X x X by (a,b)R(c,d) if a + d = b + c I lose track of what it is asking on the part italicized. I have a similar question that ends in ad = bc as well ...
0
votes
1answer
57 views

Proving recurrence relations

So, I initially proved the theorem that if $a != b^d$ and $n$ is a power of $b$, then $f(n) = C_1n^d + C_2n^{log_b a}$, where $C_1 = b^dc/(b^d − a)$ and $C_2 = f(1) + b^dc/(a − b^d )$. This is seen ...
2
votes
1answer
117 views

Permutation Formula

I am having difficulty with one minuscule detail of the permutation formula: $$n(n-1)(n-2)\cdots(n-r+1)$$ I understand that if we proceed with an $r$-permutation, then we have $r$ amount of slots, ...
1
vote
2answers
68 views

Ordinary generating functions - I can't understand this

I'm trying to understand ordinary generating functions. I've been looking for any tutorial or some explanations about the topic but I haven't found anything useful and - what's more important - well ...
1
vote
1answer
265 views

how discrete mathematics is related to computerscience

I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of ...
3
votes
3answers
167 views

Discrete Math, anagram combinatorics

Find the number of anagrams for the word "ALIVE" so that the letter "A" is before the letter "E" or the letter "E" is before the letter "I". By before we mean any letter previous, not just immediately ...
1
vote
1answer
72 views

Modular Arithmetic: $ 291-118 \pmod 4\;$?

How do you work out: the value of $ 291-118 \pmod 4\;$? Thanks
2
votes
1answer
74 views

Showing a bijection with a contraction

I have the function $F(x) = x + f(x)$ where $f(x)$ is a contraction: $|f(x)-f(y)| \leq \alpha|x-y|$ for some $0 < \alpha < 1$ and all $x, y \in \mathbb{R}$ I want to show that $F$ is a ...
0
votes
1answer
57 views

Using The Pigeon-Hole Principle

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n. Here is the solution: Let $a,~a+1,...,a+n-1$ be the integers in the sequence. ...
0
votes
0answers
258 views

What is the algorithm to sort 5 elements in 7 binary comparisons?

I'm tasked with finding the algo that sorts 5 elements in 7 binary comparisons. (The 7 is derived from ceilingFunction(log 5!), which our text states is the minimum number of comparisons required for ...
0
votes
0answers
34 views

Help with functions, confirming if I'm correct.

Let $\mathscr F$ denote the set of all functions from {1, 2, 3, 4} to {1, 2, 3, ... , 10}. a) Find and simplify the number of functions $f \in \mathscr F$ so that f(1)=1 and f(2)=2. b) Find and ...
0
votes
1answer
51 views

Help proving and counting functions.

Let $\mathscr F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$. a) Of the two following statements, one is true and one is false. Prove the true statement. Write out the ...
4
votes
2answers
119 views

“Tricky” wording on Congruence Modulo Question?

I'm asked for all possible values, but I can only see one. The question on my practice exam reads: Consider the equivalence class [3] for the equivalence relation "congruence modulo $7$" on $\Bbb Z$. ...
1
vote
1answer
2k views

Relational Sets for Reflexive, Symmetric, Anti-Symmetric and Transitive

I just want to brush up on my understanding of Relations with Sets. Specifically with this set: $\{ 1, 2, 3 \}$ I understand Reflexive, Symmetric, Anti-Symmetric and Transitive in theory. But if ...
3
votes
3answers
55 views

Representing the statement using Quantifiers

I want to represent the statement "Some numbers are not real " using quantifiers. I have been told by my teacher that the correct way to represent this is num(x) : x is a number real(x) : x is real ...
2
votes
2answers
2k views

How many bit strings of length 8 start with 00 or end with 1?

How many bit strings of length 8 start with 00 or end with 1? I know about product rule and sum rule but I'm unsure how to ...
1
vote
1answer
58 views

Discretization of Continuous Mathematics

I am currently taking a course involving the use of numerical methods to solve partial differential equations. I have not yet been exposed to such a technique and as an aspiring computer scientist, ...
2
votes
1answer
101 views

Short proof of Hall's theorem

Studying the proof of Hall's theorem in my book I started to wonder if there is a shorter way to prove it. Following is an attempt that I think works but (being short) makes me wonder if I made a ...
3
votes
2answers
569 views

Solving two simultaneous recurrence relations

If we have the two recurrence relations $$a_n = 3a_{n-1} + 2b_{n-1}$$ $$b_n = a_{n-1} + 2b_{n-1}$$ with $a_0 = 1$ and $b_0 = 2$. My solution is that we first add two equations and assume that $f_n = ...
-1
votes
1answer
562 views

Semigroups, monoids, & groups!

I need help determining if these are semigroups, monoids, or groups? a) $\mathbb Z ^+$, where $\#$ is defined as ordinary multiplication b) $\mathbb Z ^+$, where $a \# b$ is defined as $\gcd(a,b)$ ...
1
vote
3answers
207 views

Strings and Substrings

So here is one of the last homeworks we are doing in my Discrete math class. It seems like it should be simple but I am really stuck. Any help would be greatly appreciated. Find the ordinary ...
2
votes
2answers
80 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
2
votes
3answers
541 views

Trees whose complement is also a tree

I am searching for those graphs $G$ where $G$ is a tree and its complement is also a tree. I came out with one such graph $P_4$. Are there any other too? I am not getting any other example. thanks
1
vote
2answers
275 views

Odd or even permutation with matrices

I know that the number of transpositions would determine the parity of a permutation like: A = (1,2,3,4,5) = (1,5),(1,4),(1,3),(1,2) = even But how would that apply to a matrix? Example: 1 2 ...