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
0answers
16 views

Selection of distinct (positive factors) of 50

The selection of how many distinct (positive) factors of 50 will guarantee that at least two of them have a product of 50? Explain.
0
votes
1answer
12 views

Is my solution consider as a proof of inclusion-exclusion for $k=3$

This is my solution but I don't know if I can consider it as proof??? Here let $A$ , $B$ , and $C$ are sets
0
votes
1answer
19 views

Find $c$ in modular mathematics

Suppose that $a$ and $b$ are integers, $a\equiv 11(\mod19)$ and $b\equiv3(\mod19)$ . Find the integer $c$ with following properties. $0\le c\le18$ $c\equiv 7a+3b(\mod19)$ $c\equiv2a^2 ...
0
votes
1answer
24 views

Can the function y=5 be injective or surjective for all x ∈ integers?

I have a practice exam and I get kind of confused about: Is the constant function y = 5 , ∀ x ∈ Z [All integers] Is this function Injective or Surjective?
1
vote
2answers
48 views

Proving $n^a-n^b$ is divisible by 10

Let $n$ be positive integer. Prove that there exists positive integers $a$ and $b$, with $a \neq b$, such that $n^a-n^b$ is divisible by $10$. I have tried using mathematical induction and logs but I ...
0
votes
1answer
12 views

Use induction to figure out the number of handshakes in a party

Every arriving guest shakes hand with everybody else at a party. If there are n guests in the party, how many handshakes were there? Proof by using induction. My approach to this problem was to write ...
1
vote
2answers
32 views

How would you go through this combination/ permutation problem

A market has 30 different pants and 12 different hats. You want to to get 3 different pants and 2 different hats. How many ways can you make this purchase? I assume this is a combination, but stuck ...
0
votes
0answers
20 views

Turning a recurrence relation into a characteristic equation

I have the following recurrence to solve: bn = 13bn-1 - 22bn-2 , n > 1            Subject to b0 = 3 , b1 = 51 I've figured it out until b4: b2 = ...
2
votes
0answers
15 views

computing characteristic polynomial of hyperplane arrangement

The following problem comes from Richard Stanley's $\textit{Enumerative Combinatorics}$ vol. 1, 2nd ed. It is problem 114 (c) in Chapter 3. Let $\mathcal{A}$ be a hyperplane arrangement in ...
0
votes
3answers
14 views

determining which graphs are bitpartite/2-colorable and which are not

I am having trouble understanding bipartite/$2$-colorable graphs. I was hoping someone can guide me through this question. For the graphs given above, either prove that they are bipartite by showing ...
0
votes
1answer
9 views

Is this relation P an equivalence relation or a partial order relation?

I am having trouble with partial order and equivalence relations. I was wondering if someone can guide me through this problem. Let $Σ$ be the set of letters {$a, b, . . . z$}. Let $Σ^∗$ be the set ...
1
vote
2answers
25 views

Prove that the sum of two positive real numbers is equal or greater than the square root of their product.

Trying to prove this: A and B are positive real numbers. A + B ≥ √ AB  This is what I wrote: Proof by Contradiction A + B < √ AB  (A + B)2 < AB A2 + AB ...
-2
votes
1answer
37 views

Can anybody help me for this counting question? [on hold]

Peter has $12$ pairs of socks and $6$ pairs of gloves in different colors. His socks are in green, yellow, black, and grey ($3$ pairs each). Peter's gloves are either blue, black, or red ($2$ pairs ...
-3
votes
0answers
21 views

How to determine whether injective or surjective over this functions [duplicate]

G : N×N given by G = 2x+5 ∀x ϵ N H : Z×Z given by H = 10 ∀x ϵ Z I got an idea whether injective or surjective but don't know how to go through. And finally, are these functions? I think they are ...
-1
votes
1answer
19 views

How to go towards this functions and defining whether injective or surjective

G(x) : N×N given by G(x) = 2x+5 ∀x ϵ N H(x) : Z×Z given by H(x) = 10 ∀x ϵ Z I am not familiar with this notations. However, I got an idea whether injective or surjective. And finally, are ...
2
votes
2answers
28 views

Probability of a pair of red and a pair of white socks among five chosen [on hold]

In the box are seven white, five red and three black socks. Socks are considered to be a pair if they have the same color. Five arbitrary socks are selected at random from the box. Find the ...
0
votes
0answers
25 views

proof that some expected value equal to $\theta (\log n - \log k)$

So here is the problem - Given the following equation: $(c_2\cdot \log n) - (c_1\cdot \log k)\le E(X)\le 1+ (c_1\cdot \log n) - (c_2\cdot \log k)$ When $c_2,c_1\gt0$ and also $c_1\gt c_2$ In ...
0
votes
1answer
23 views

How can I draw a Hasse Diagram divisibility?

We just started learning graphs and I wanted to know how can I draw the Hasse diagram for divisibility on the sets: {$6, 10, 14, 15, 21, 22, 26, 33, 35, 39, 55, 65, 77, 91, 143$} In class we ...
0
votes
0answers
15 views

How to find a specific SLOPE at a point [on hold]

The question is to find a slope of 1;0;-2 in f(x) = x^2 the point doesn't matter You can also discard the function and use variables so I can do it for all exercices like this. Thanks in advance
-3
votes
0answers
64 views

Puzzle to puzzle you:image [on hold]

Suppose 3 1D Signals x(t), y1(t) and y2(t) are given as x(t)=sin(40*pi*t); y1(t)=.5*sin(40*pi*t) and y2(t)=x(t)+y1(t). Left side =Right side Here,values of x(t)and y1(t)i.e.(Right side) are given ...
0
votes
1answer
27 views

Determining a relation if reflexive, symmetric, and transitive

I just get stuck in this relation and need to find if this relation is Reflexive/ Irreflexive or Neither, Symmetric/ Antisymmetric or Neither, Transitive or Not. $$W_1 = \{(a , b) \in \mathbb ...
2
votes
2answers
55 views

What is the probability of a randomly chosen bit string of length 8 does not contain 2 consecutive 0's?

Just what the title says, I'm trying to determine the probability of a randomly chosen bit string of length $8$ containing $2$ consecutive $0$'s. I've determined the total number of possible bit ...
2
votes
2answers
46 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
-1
votes
1answer
43 views

What does this $TS \models P$ mean in relation to set theory. [on hold]

In set theory, what does it mean when you have $TS \models P$ Rationale: when dealing with Linear Temporal properties for transition system, you can have a safety property $P$ and a transition ...
2
votes
1answer
22 views

Combinatorics/Probability unordered lists

I don't really understand these unordered lists problems such as... Q: John goes to a store and buys 10 pieces of fruit from the selection of apples, bananas,peaches and pears at random. What is the ...
2
votes
1answer
15 views

number of weak compositions modulo prime $p$

For $n\in \mathbb{N}$ and some prime $p$, consider $(\mathbb{F}_p)^n$. Is it known how many weak compositions $$x_1+x_2+\ldots +x_n\equiv 0 \pmod p$$ in $\mathbb{F}_p$ there are, where $(x_1, \ldots, ...
3
votes
4answers
94 views

Solve the recurrence of the alternating sum $R_n=R_{n-1}+(-1)^{n}(n+1)^{2}$

I have been trying to solve this recurrence for a few hours, but I haven't been able to find the solution yet: $R_0=1$ $R_n=R_{n-1}+(-1)^{n}*(n+1)^{2}$. I have been trying to substitute ...
0
votes
1answer
25 views

Induction Mathematics and Factorials

\usepackage{amsmath} Evaluate the sum $\sum_{k=1}^{n} {k\over (k+1)!}$ $\sum_{k=1}^{1} {1\over (1+1)!} = {1\over 2}$ $\sum_{k=1}^{2} {2\over (2+1)!} = {5\over 6}$ $\sum_{k=1}^{3} {3\over (3+1)!} ...
0
votes
1answer
30 views

Which discrete mathematics book do you think is better between Epp's and Rosen's for a clueless self-learner?

I am a programmer, and I want to become a machine learning researcher and a good software engineer. I dabbled with calculus, linear algebra, and real analysis for a few months when I was enrolled in a ...
0
votes
2answers
33 views

Proofing Induction Mathematics

I have just started to cover induction mathematics in my Discrete Mathematics class and I'm a little confused as to where to go with this problem. Am I on the right track? Prove that 9 divides (n^3 ...
2
votes
1answer
33 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
2answers
21 views

Does this recurrence relation run in $ \Theta(n) $?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
0
votes
0answers
6 views

what is the total number of ways Company can advertise meeting its minimum cost strategy

There are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money). Company strategy is that, they ...
-1
votes
1answer
28 views

Covering relation over functions

F is a group that includes all functions from N to N K is relation over F. For f,g ∈ F: (f,g) ∈ K iff ∀ n∈N, f(n)≤g(n). Obviously K is Partially ordered set and not Total Order. My problem is with ...
0
votes
1answer
18 views

Uniqueness in Mantel Theorem

In Mantel's Theorem: I know that $K_{\lceil n/2 \rceil , \lfloor n/2 \rfloor} $ achieves the maximum number of edges without having a triangle. But why is it the unique example?
0
votes
1answer
20 views

Calculating edge count of non standard shape(?)

So basically, I want to have a map of any size/proportion (locking it down to integers). e.g. $4 \times 4$ $\begin{matrix} 2 & 3 & 3 & 2\\ 3 &4 &4 &3\\ 3 & 4& ...
4
votes
1answer
59 views
+150

The graph has an Euler tour iff in-degree($v$)=out-degree($v$)

I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2) A simple ...
-1
votes
0answers
8 views

how to use recursive version of MinSort,selection sort [on hold]

following algorithm is a recursive version of MinSort, or selection sort, which takes as input an array A of n integers and returns an array with the elements of A sorted from smallest to largest. ...
-1
votes
1answer
26 views

Prove that the given algorithm is correct for various cases. [on hold]

The following algorithm determines whether a word is a palindrome; that is, if the word is the same read left to right as right to left. Palindrome($s = s_1s_2s_3 \ldots s_n$) (a string of length ...
-4
votes
0answers
19 views

How to find recursive formaula for a ternary string [on hold]

A ternary string $12210021$ of length $8$. Let $T(n)$ be the number of ternary strings with the property that there is never a $2$ appearing anywhere after a $0$. For example, $12120110$ has this ...
-2
votes
1answer
27 views

how to find recursive formaula for airplane seats [on hold]

An airplane seat can either accommodate one person or two people, if one of them is an infant under the age of two. Seats can also be empty. An arrangement of people in a row of an airplane is a ...
-1
votes
2answers
28 views

How to find out the recursive formula for tromino tiling of a 3 × n rectangle

Say you are tiling a 3 × n rectangle with L-shaped tiles of area 3 (trominoes). (To tile the rectangle is to cover it with tiles so that no tiles overlap, no tiles are hanging off the edge of the ...
0
votes
1answer
33 views

Partition and equivalence relation

Consider the equivalence relation between non-empty subsets $A , B$ of $\{ 1,2,3, 4,\dots,100\}$ defined by the condition: the greatest element of $A$ is the same as the greatest element of $B .$ ...
0
votes
0answers
19 views

give the recursive structure of the following problems

A) When you cut a pie, you cut along a diameter of the pie. Let $P(n)$ be the number of slices of pie that exist after you have made $n$ cuts, where $n \geq 1.$ Write a recurrence for $P(n).$ B) In ...
1
vote
1answer
34 views

This question is from my discrete math. So far i have no idea how to solve it. Can anyone help me with this? [duplicate]

Let n be a prime. 1. If (G,+) has order 2n, prove that every proper subgroup of (G,+) is cyclic. 2. If (G,+) has order n^2, prove that (G,+) has a subgroup of order n.
0
votes
3answers
45 views

Number of elements in a set.

i am just getting started with discrete mathematics and set theory and i came across this question which would seem like an elementary problem. I would appreciate any help on this : Suppose $m$ and ...
2
votes
0answers
33 views

Inversion of a pairing function

I was reading this question on this site and I saw that the following pairing function was mentioned (a modified version of Cantor function): $$\langle x, y\rangle = x * y + ...
0
votes
1answer
16 views

find transitive clouser of a matrix [on hold]

Find transitive closure of R if M_R is $$\begin{bmatrix}1 & 0 &0 \\0 & 1 & 1 \\1 & 0 & 1 \end{bmatrix}$$ I tried doing it like this M_R * M_R * M_R but could not get the ...
-3
votes
0answers
20 views

Bit String Probability [on hold]

Given a bit string of length 8 begins with a 0, find the probability that it contains exactly three 0's. How many bit strings of length 8 contain an evan number of 0's? How can permutations and ...
-4
votes
2answers
54 views

Proof By Induction [on hold]

I am trying to prove the Following, However, I dont understand what to do at the Inductive Step: Any Help would be appreciated!