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
vote
1answer
382 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 ...
1
vote
1answer
67 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, ...
1
vote
3answers
70 views

Proving two claims about sets and functions

Let X,Y be sets, and let $f:X\rightarrow Y$ be a function. Prove: $f(f^{-1}(B))\subset B$ for every $B\subset Y$. Intuitively I understand why's that, but how do I prove it with formality? For every ...
1
vote
1answer
48 views

8 friends, 7 nights, invite 4 every night, all of the friends must be invited, how many options?

Assume I have 8 friends, I want to invite 4 friends each night for 7 night so everyone will be invited at least once. How many combinations are there to do it? I think I'm supposed to use the ...
1
vote
3answers
86 views

Can someone check the solution to this recurrence relation?

Here's the recurrence relation: $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$ Here's the solution:Write: $$ a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^n + n + 3 \quad a_0 = 1, a_1 = ...
1
vote
1answer
293 views

Triangle tiling proof

How to prove that the number of triangles in the tiling below can be found by the formula $$\left\lfloor\frac{n(n+2)(2n+1)}8\right\rfloor\;,$$ where $n$ is the number of vertical layers? (For the ...
1
vote
2answers
1k views

Finding a solution to a recurrence relation

Find the solution to $$a_n = 5a_{n−2} − 4a_{n−4}$$ with $$a_0 = 3$$ $$a_1 = 2$$ $$a_2 = 6$$ $$a_3 = 8$$ My answer: Observe that the degree of recurrence is 4. Hence, the characteristic equation is: ...
1
vote
2answers
35 views

Im have trouble with this question.

im having a bit of trouble with this problem and and how to go about it. show that: 2^n=O(n!) thanks
1
vote
1answer
118 views

Books/Review material on infinite cardinality for undergrad

You may have noticed me using asking many questions on Infinite Cardinalities on this fine website. Although many of the answers to my questions here were very in-depth and amazing, I just can't help ...
1
vote
1answer
961 views

Topological Sorting in Linear Order for Hasse Diagram

I have come across an exam review question that I am stuck on. The question states: Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram: This is ...
1
vote
1answer
107 views

extended linear codes over the field $\mathbb F_q$

Suppose we extend the $[n,k]$ linear code $C$ over the field $\Bbb F_q$ to the code $C'$, where $$ C' = \{(x_1,\ldots ,x_n,x_{n+1})\in \Bbb F_q^{n+1} : (x_1,\ldots,x_n) \in C \text{ and } ...
1
vote
1answer
616 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
1answer
58 views

How to estimate (if/any) displacement/rotations between 2d line segments taken from 2 data sets

I am having set of pair of line segments (2D). Though each pair should be coincided on top of each other they are not so. I derive these two line sets using image based (e.g. CD) and manual method ...
1
vote
1answer
56 views

Monotone finite sequences

I have a few questions about monotone finite sequences. My motivating problem is the following: Sixteen players participated in a round-robin tennis tournament. Each of them won a different number ...
1
vote
1answer
181 views

Where can I learn about solving Big-Oh problems that are written in algebra? [duplicate]

Where can I learn about solving Big-Oh problems that are written in algebra? Such as this $$\sum_{i=1}^{n} (3i + 2n) = O(n^2)$$
1
vote
1answer
478 views

How do you write a recursive function in a way that it will be easy to compare it to another while doing a proof by induction?

How would you write the following recursive function in such a way that it will be easy to compare it to another while doing a proof by induction? Base Case: $F(0) = 0; F(1) = 1$. Recursive Step: $ ...
1
vote
1answer
97 views

Having an issue with this problem with an assignment

Suppose that an algorithm uses $2n^2+3^n$ bit operations to solve a problem of size $n$. Suppose that your machine can perform one bit operation in $10^{-9}$ seconds, how long does it take your ...
1
vote
1answer
99 views

Counting Boys and Girls in a Team

There are 12 children and are being divided into two teams to play a game. $(a)$ In how many ways can you divide 12 children, 6 boys and 6 girls, into two teams to play a game, if the teams are called ...
1
vote
1answer
594 views

How many permutations of this set can be made?

How many permutations of the set of seven letters (A,B,C,D,E,F,G) have the two vowels before the five consonants? I'm wondering here if we use the set of 7! - 2! since they can only occupy the first ...
1
vote
1answer
114 views

Set of natural numbers, for which the reunion of the sums of all subsets is a set

My math is weak so I'll try to clarify my question with an example. Consider the set $\{1,2,4\}$ for which the powerset $\{ \{\}, \{1\}, \{2\}, \{4\}, \{1,2\}, \{1,4\}, \{2,4\}, \{1,2,4\} \}$. Now, ...
1
vote
1answer
59 views

Pointers about the concept of 'division extensionality'?

When working a bit on another question (If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$), I discovered the following, which seems to be valid: $$ a = b \;\;\equiv\;\; \langle \forall d :: d ...
1
vote
1answer
70 views

Montmorts Problem on random arrangements

So given A = "neither student 1 nor student 2 gets put in their own desk" X = indicator function for A Y = the number of students do not get put back on their own desk part 1 lets assume n = 10 ...
1
vote
2answers
141 views

Discrete math: Is the survey accurate?

A library has conducted a survey of its readers. The survey asked its $10,000$ readers about their reading habits and the number of books that they have borrowed from the library in $2012$. It has ...
1
vote
1answer
144 views

Discrete Math: Set Theory

Can anyone help me check if my solution is correct? Link here, sorry it kinda look too messy when i tried to paste d) A class has 175 students. The following table shows the number of students ...
1
vote
1answer
120 views

Define a $1$-$1$ onto function with domain $A$ onto the set $\{1, 2, … n\}$

Let $A = \{x^2 : x \in \mathbb{N} \text{ and } 0 \leq x^2 \leq 90\}$. Define a 1-1 onto function with domain $A$ onto a set of the form $\{1, 2, \ldots, n\}$ to show the cardinality of $A$ is $n$. ...
1
vote
2answers
486 views

Total Orders and Minimum/Maximum elements

How can I prove that for any given Poset $(A,\preceq)$, $\preceq$ is a total order implies that $\forall a\in\preceq$, if a is a maximal, then a is maximum? Same goes for minimal/minimum.
1
vote
3answers
109 views

Combine two given Elliptic Curves

I want to combine two Elliptic curves such $E_p$ (defined in the field $F_p$) and $E_q$ (defined in the field $F_q$) i.e to find $E_n$ where $n=pq$. Is there any method to do it?
1
vote
1answer
164 views

How many different names can be created by using the letters…?

Consider the name: AABBC DEF ACK I want to find how many different name combinations with 3 words I can come up with. I know there exists $\frac{11!}{3!2!2!}$ different permutations. But, what is the ...
1
vote
1answer
70 views

Finding two highest peaks in a chunk of samples

Supose I have a list of 600 samples of numbers, and the histogram of the samples looks like the following: As can be seen, there are two 'mountains' of values around 16 and 48, and a outlier in 95. ...
1
vote
1answer
317 views

Probability that a team will win

Two teams A and B compete in a "best-of-5" competition. This means they play each other until one team has won 3 games. Suppose that for any of the games, the probability that A beats B is ...
1
vote
1answer
162 views

How do we show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$

Basically I'm wondering how I can show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$. Any ideas? Thanks a lot!
1
vote
1answer
356 views

Finite state machine to report when the last 4 inputs were 1011

Suppose you want to construct an FSM containing one input and one output. Consider the example: The machine should assert the input (set to 1) when the last four bits taken in as input match the ...
1
vote
1answer
50 views

Controlling vote

Setting Suppose $n$ students plan to go $m$ tourist spots $s_1, \cdots, s_m$ together. But it turns out that the schedule is tight. So they decide to go $(m - 1)$ tourist spots instead. To determine ...
1
vote
1answer
36 views

Finding specific sets

I'm trying to calculate these particular sets given that: $$A=\{a,c,e,h,k\}$$ $$B=\{a,b,d,e,h,i,k,l\}$$ $$C=\{a,c,e,i,m\}$$ $$A \cap B$$ $$A\cap B \cap C$$ $$A \cup B \cup C$$ $$A-B$$ ...
1
vote
1answer
275 views

Show that an equivalence relation is equal to the union of its equivalence classes

Given an equivalence relation $\sim$ with equivalence classes $C_1,\dots,C_n$, show that $$\mathbin{\sim} = \bigcup_{i=1}^n(C_n\times C_n)\;.$$ I could use a hint on where to start approaching this ...
1
vote
2answers
552 views

generating functions for pennies and nickels

We will use generating functions to determine how many ways there are to use pennies and nickels to give n cents change. (i) Write the sequence Pn for the number of ways to use only pennies to change ...
1
vote
3answers
931 views

How to solve for the amount of arrangements of books on a shelf?

Having a little bit of trouble with this question, but I don't necessarily want the answer, I'm looking for an explanation on how to do it, and if my theory is correct. How many ways are there to ...
1
vote
1answer
157 views

Proving this language is not regular

Let $$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$ I have been trying to get a start on this proof for a long time now with no success. What would ...
1
vote
1answer
894 views

nested quantifiers

In the domain of integers, $P(x,y)$. predicate "$xy = 12$" I'm not sure why $(\forall x)(\exists y)P(x,y)$ is false statement. "For all $x$, there are some $y$, such that $xy = 12$". ex.: ...
1
vote
1answer
38 views

Order of a cycle containing four vertices of degree two in $G\Box H$

Suppose the undirected graph $G$ has a vertex $g$ adjacent to the vertices $g_1$ and $g_2$ of degree one and another undirected graph $H$ has a vertex $h$ adjacent to the vertices $h_1$ and $h_2$ of ...
1
vote
2answers
42 views

How do i apply multinomial laws in this question?

the Question is i assume i have 15 students in class A grade obtain probaiblity = 0.3 B grade obtain probability =0.4 C grade obtain probability = 0.3 and I have this question What is the ...
1
vote
1answer
241 views

approximating a discrete function with a continuous one

Let $f:[0,1]\rightarrow \mathbb{R}$ be a continuously differentiable function that reaches a global maximum at $x^*\in(0,1)$. Now, consider its 'discrete' counterpart. That is, consider the collection ...
1
vote
1answer
144 views

reversible integer transform

Let be x, y two natural integers. Define the following transform: X=x+(x-y). Y=y-(x-y). If the difference d=x-y tends to 0, we have X=x and Y=y. The above transform has the property that is reversible ...
1
vote
2answers
179 views

Solving the recurrence relation $p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$ where $p(1,m) = m$

I am trying to solve the following recurrence relation $$p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$$ $$p(1,m) = m$$ $$p(0,0)=0$$ Any hints or ideas? (Not a homework assignment) Edit: n ...
1
vote
1answer
48 views

How to get range of 1 to 10 by index?

I have a collection of lessons divided by levels Each level has 10 chapters. ...
1
vote
3answers
105 views

Finding recurrence and an algorithm to represent it

You find yourself in a country with integer coin denominations $c_1 < c_2 < ... < c_r$, where $c_1 = 1$. Unfortunately, the greedy algorithm is not guaranteed to find the optimal way to ...
1
vote
5answers
622 views

How do we deal with recurrence relation characteristic equations that are not quadratic or have imaginary roots?

Suppose we have $$H(n) = H(n-1)-H(n-2) \rightarrow x^2-x+1 \rightarrow r_1 = \frac{1+\sqrt{-3}}{2}, r_2 = \frac{1-\sqrt{-3}}{2}$$ or $$H(n) = H(n-1)+H(n-2)+H(n-3) \rightarrow x^3-x^2-x-1=0$$ In ...
1
vote
2answers
51 views

Logic - Will a second parameter value inherit negation if the first parameter is false?

Will a second parameter value inherit negation if the first parameter is false? Like: (~A & B) → X Is B false? Would it ...
1
vote
3answers
1k views

Can floor functions have inverses?

R to R $f(x) = \lfloor \frac{x-2}{2} \rfloor $ If $T = \{2\}$, find $f^{-1}(T)$ Is $f^{-1}(T)$ the inverse or the "image", and how do you know that we're talking about the image and not the ...
1
vote
1answer
754 views

How to find the Greatest lower bound/Lower Upper Bound in a poset with sets as elements

I've been thinking about the following hypothetical problem given in a discrete math textbook (with no explanations), but don't know if I'm going in the right direction. Given the poset: ⟨{{A}, {B}, ...