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.

learn more… | top users | synonyms

-1
votes
1answer
16 views

Show that $a$ is minimum

If $(A,<)$ totally ordered, show that if $a$ is a minimal element of $A$ then $a$ is minimum. Could you give me a hint how we could do this? Definitions: Let $(A, \leq)$ be an ordered set. We say ...
0
votes
1answer
9 views

Reachability relation set

How can i define reachable relation set of R for a given di-graph below?
1
vote
1answer
18 views

Combinations - no repetition for mirrors?

My question is, if there is a simple explanation as to why mirrors aren't counted twice with binomials such as it is in the case it's not a mirror? Here is an example: Consider the elements {1, 4}. ...
1
vote
1answer
12 views

Find #committee of 8 from 3 freshmen, 4 sophomores, 4 juniors, and 5 seniors contain at least one of each class

The question: A student council consists of three freshmen, four sophomores, four juniors, and five seniors. How many committees of eight members of the council contain at least one member from ...
2
votes
2answers
36 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
3
votes
0answers
39 views

Number of functions from domain to codomain

Let A and B be finite sets. Let a be the size of A. Let b be the size of B. Assume 0 < a < b. (a) How many functions are there with domain A and co-domain B? (b) How many one-to-one functions ...
2
votes
1answer
48 views

Probability for having consecutive success in an experiment

A friend asked me the following question: "In an experiment, we are tossing a fair coin 200 times. We say that a coin flip was a success if it's heads. What is the chance for having at least 6 ...
-1
votes
1answer
51 views

Hasse diagram question about relations

I have the following Hasse diagram below, the question is given specific generalised quantifiers I have to list the subsets of {a,b,c,d} which the quantifier corresponds to. I have completed the ...
2
votes
1answer
29 views

Derivatives defined on a discrete state space

Ive been looking at certain economic papers, and optimal control papers. They define a state variable, $\omega$, which follows a discrete time Markov Chain. Then they define a utility function ...
0
votes
2answers
56 views

Probability that n people collectively occupy all 365 birthdays

The problem is quite simple to formulate. If you have a large group of people (n > 365), and their birthdays are uniformly distributed over the year (365 days), what's the probability that every day ...
1
vote
1answer
51 views

How does the function work? [on hold]

Could you explain me the function of the following two algorithms? ...
0
votes
1answer
8 views

Is there a closed form expression for the Taylor series of (1- a X - b Y - c XY )^ (-1)?

Is there a closed form expression for the Taylor series of f(X , Y ) = (1- a X - b Y - c XY )^ (-1) ? a, b and c are constants X and Y are thank you
1
vote
2answers
83 views

An exercise from Knuth's book - Proving a formula by induction

I would like to find a formula for this sum: $$ \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4} $$ The answer given (Knuth's book, The Art of ...
0
votes
1answer
25 views

Creating equation for a given recurrence relation

I'm studying discrete math in the university, and we are given questions and answers for some problems, and I dont understand most of them. So I need help understanding one of them... Appreciate the ...
3
votes
1answer
36 views

Triangulation of hypercubes into simplices

A square can be divided into two triangles. A 3-dimensional cube can be divided into 6 tetrahedrons. Into what number of simplices an n-dimensional hypercube can be divided? (For example, a ...
2
votes
0answers
33 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
1
vote
0answers
19 views

Calculate year for a provided yield

\$146.25 will yeild \$46.25 at 7.5% per annum. How to get the number of years? Answer is 6 but how do you get it? What is the formula?
5
votes
0answers
18 views

Discrete analogue of Green's theorem

Following formula concerning finite differences is in a way a discrete analogue of the fundamental theorem of calculus: $$\sum_{n=a}^b \Delta f(n) = f(b+1) - f(a) $$ We can think about the Green's ...
11
votes
4answers
916 views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change ...
1
vote
1answer
20 views

Directed Multigraph or Directed Simple Graph?

I have the following two questions in my book: Question # 1 Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more ...
-3
votes
2answers
70 views

How many integers from 1 to 100,000 contain the digit 6 at least once? [on hold]

How many integers from 1 to 100,000 contain the digit 6 at least once? I have no idea how to solve this, can somebody help me out?
0
votes
2answers
28 views

Repeated squaring method

How do I use the repeated squaring method to calcualte 2^176 (mod 177)? I'm not sure, but is there something about the fact that 177 is 1 greater than 176 that makes this a problem?
0
votes
2answers
53 views

Show that a function from a set is non-conservative [on hold]

So I have this question There exists some set A = (a,b,c,d), we have a function H from Powerset(A) into Powerset(A) -> {T,F} given by H(X)(Y) = True iff |X|<|Y| I need to show some ...
0
votes
0answers
29 views

how to show a function is non-conservative? [on hold]

So I have this question ...
0
votes
2answers
11 views

Expressing n mod m in terms of floor values?

I'm trying to prove the expression: $$\left\lceil\frac{n}m\right\rceil = \left\lfloor n+m-\frac1m\right\rfloor\;,$$ where $n,m$ are integers` So I've come across this article (PDF) which gives a ...
1
vote
3answers
59 views

Why is this combinatoric solution not correct?

I'm trying to solve the following problem: Balls of the colors red, orange, yellow, green, blue, indigo, violet (7 colors, 1 ball per color) are placed into 4 different boxes A,B,C,D so that no box ...
0
votes
2answers
35 views

Solve the recurrence relation (using iteration?)

$a_n = a_{n-1} + 1 + 2^{n-1}\\ a_0 = 0$ Not sure how to iterate with the exponent term. Here's what I got: $= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-1} = a_{n-2} + 2 + 2(2^{n-1})\\ = (a_{n-3} + 1 + ...
0
votes
0answers
32 views

Boolean algebra and boolean subalgebra

I have to prove that set of all dividers of number 210 with appropriate operations forms a Boolean algebra. And describe these operations and create a Hasse diagram. In the secondd part I have to ...
0
votes
0answers
12 views

Inverse of a discrete trasformation

I have defined the discrete transformation-like relationship: $$ Y(k)=\sum_{n=0}^{N-1} \frac{A(n)}{1+j \frac{w(k)}{p(n)}} $$ with $w(k)$ the k-th element of the vector $w$, $p(n)$ the n-th element ...
0
votes
1answer
24 views

Recurrence relation advice

$t_n=5t_{n-1}+6t_{n-2}$ Is the characteristic equation of this correct? This is what I have: $x$- 5$x$ -6=0 Is this correct?
1
vote
2answers
34 views

tips and tricks for understanding induction proofs in discrete structures.

I have my discrete structures exam tomorrow, and right now i am practicing mathematical induction, specially proofs. while proving, i just get confused because i don't understand what should i add or ...
-1
votes
0answers
32 views

Difference between two expressions for combinations with repetition.

While attempting to solve problems that compute the number of combinations with repetition (ie, a store has 4 flavors of ice cream and you are picking 3 with repetitions allowed, how many ways can you ...
0
votes
3answers
50 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
0
votes
1answer
37 views

S is a finite set show that $|P(S)|$ is $2^{|S|}$. [duplicate]

If $S$ is a finite set, show that $|P(S)| = 2^{|S|}$. So I know that $|P(S)|$ means the number of elements in the power set of $S$, but I don't understand the relation between the power set and ...
1
vote
2answers
36 views

Order of $f(n) = 4n + 6n^3 - 8n^5$

If a function $$f(n) = 4n + 6n^3 - 8n^5$$ then the order of $f$ is: The answer I have is $\log(n)$, but I'm not sure if it's right.
1
vote
1answer
34 views

Proving the upper bound of edges in a convex polyhedron

The question is the following: Suppose Every face of a convex polyhedron has at least $5$ vertices and every vertex has degree $3$. Prove that if the number of vertices is $n$, then the number of ...
2
votes
1answer
42 views

Hierarchy of Mathematics Breakdown

Can you provide me with a hierarchical breakdown on Discrete Math as it applies to computer science? By this I mean a breakdown on topics that fall under the study of discrete numbers, specifically ...
1
vote
3answers
33 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
1
vote
0answers
26 views

Phase trasition of $f(x)$ on random graph $G(n,p(n))$

Random graph $G(n,p(n))$ and graph $H$, which shown below, are given. I'm in need to find $f(x) : f(x) > 0$, such as: if $lim_{n \to \infty}p(n)f(n) = 0$, then asymptotically almost surely G ...
2
votes
1answer
73 views

Solve the recurrence relation: $2a_n = 7a_{n-1} - 3a_{n-2}; a_0 = a_1 = 1$

$2a_n = 7a_{n-1} - 3a_{n-2}\\ a_0 = a_1 = 1$ My attempt: $2t^2 - 7t + 3 = 0\\ t = -\frac{1}{2}, -3\\ \\ U_n = b(-\frac{1}{2})^n + d(-3)^n\\ b+d = 1 = -\frac{1}{2}b-3d\\ b = \frac{8}{5}, d = ...
0
votes
1answer
16 views

How to determine whether a given relation on a finite set is transitive?

On $R = \left \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(4,5),(5,5) \right \}$ Not reflexive because (3,3) and (4,4) are missing? Not symmetric because (2,1) ,(3,2), (4,3), (5,4) are missing? Not ...
0
votes
2answers
23 views

Counting bitstrings of length 10 [on hold]

a) How many bitstrings of length 10 have exactly 6 zero's? b) How many bitstrings of length 10 have as many 0's as 1's?
1
vote
1answer
16 views

guessing particular solution of a recurrence equation

Please I need help on this recurrence equation .. I have tried googling but couldn't find much on this... The recurrence equation is $a_n - 2a_{n-1} = (n+1) 2^n $ I can find the homogenous ...
3
votes
1answer
38 views

Ways of getting three of a kind in a 52 card deck

This question has probably been asked before, but just to be clear here, I am NOT asking for the answer, I know the answer. What i want to know is why my solution is not equivalent to the actual ...
1
vote
2answers
22 views

Total $3$-digit odd number combinations from $1,2,3,4,5,6$

How many three digit numbers can be formed from the digits $1,2,3,4,5$ and $6$, if each digit can only be used once? How many of these are odd numbers? How many are greater than $330$? I've ...
4
votes
1answer
35 views

Number of ways to choose 6 books out of 20 books such that no 2 are adjacent books

I was trying to do the following question: Describe a bijection between ways of choosing 6 books out of 20 books so that no two adjacent books are selected and a 15-bit sequence with exactly 6 ...
0
votes
0answers
30 views

AoPS Intermediate Algebra vs. Higher Algebra by Hall and Knight? And some more questions about learning math.

Ok. I'm learning algebra at the level of AoPS algebra 2, and I want to quickly progress through math. Allow me to explain the situation. I am highly interested in artificial intelligence/computer ...
0
votes
1answer
32 views

Discrete math: Need help understanding these problems

Find a function in the list $n^2$, 1, $n^3$, $n \log n$, $\log n$, $n^4$, $2^n$, $n!$, $n$, $\pi^n$, $n^5$ that has the same order as: (a) $f(n) = 3n^4 + 6n^2 - 8n - 5 $ (b) $f(n) = 5$ (c) $f(n) = ...
-2
votes
2answers
45 views

Please help prove this summation problem for me [on hold]

Prove that for all integers n greater than or equal to 1, $\sum_{k=1}^{3n} (4k+3)=3n(6n+5)$.