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

In how many ways can I merge $m$ and $n$ items without disturbing the order in each group?

I have two lists having all distinct elements. One contains $m$ elements and other contains $n$ elements. We need to arrange them such that the order of elements of individual lists is not disturbed. ...
3
votes
2answers
48 views

Objects into two bags puzzle

I found a maths puzzle somewhere and a part of it as below: Kelly wants to place n objects $a_1,a_2,⋅⋅⋅,a_n$ into two bags. For each $i=1,2,⋅⋅⋅,n$, the weight of $a_i$ is $w_i$ kilograms. The ...
1
vote
1answer
32 views

How many ways are possible to place k items in n spots such that order of k items is not disturbed

I have k items, need to place them in n spots(n>k). In how many ways can this be done? Example - for k=2 and n=4, these are the possibilities assuming items to be like this [1,2] 12-- 1-2- 1--2 -12- ...
1
vote
2answers
52 views

Does there exist any other function $xi$ that makes the function $f$ continuous on the set of real number $\mathbb R$?

Let's define $\delta:\mathbb R\to \mathbb R$ as follows: $\forall x\in\mathbb R,$ express $x$ as $x=7k+\delta$ with euclidean algorithm, where $\delta$ is the remainder and $7$ is the divisor. We ...
0
votes
1answer
38 views

two place predicate logic

Im trying to prove following,as lecturer did not have time to go through the proof on the lecture, I wonder how to solve at least the first statement $$(\forall x)(\forall y)L(x, y) ≡ (\forall ...
2
votes
1answer
71 views

An idea on the Collatz problem

I am using the T-version of the function: $$ T(x)=\left\{\begin{array}{cl} \text{down}(x)=x/2,& \mbox{x even}\\ \quad\,\,\,\text{up}(x)=(3x+1)/2,& \mbox{x odd}\end{array}\right. $$ I will ...
0
votes
2answers
27 views

Finding a homomorphism

I'm not sure if I'm solving this problem correctly. Can someone verify? Question: Find a non-trivial homomorphism from $[\mathbb{Z}_6, \oplus_6]$ to $[\mathbb{Z}_9, \oplus_9]$ *My solution ...
1
vote
4answers
79 views

Prove or disprove $n^2+41n+41$ is a prime number for every integer $n$

Prove or disprove $n^2+41n+41$ is a prime number for every integer $n$ I started with the base step: $n(0) = 0^2+41(0)+41 = 41$ But I have no idea how to proceed in proving this. Any tips or ...
1
vote
3answers
73 views

Prove that $1+2^1+2^2+\ldots +2^n=2^{n+1}-1$ using induction

For all integers $n\ge 1$ prove the following statement using mathematical induction. $$1+2^1+2^2+\ldots +2^n=2^{n+1}-1$$ The first part of the question ask me to prove the base step: So I set ...
1
vote
1answer
20 views

Maps and the number of elements in a map

So here's the question: Suppose $f: S \to T$ is a map of sets. a. If T is finite & the map is one-to-one, show that $|S|$ is finite and that $|S| \le |T|$. b. If S is finite & the map is ...
0
votes
0answers
56 views

Approach name - Ross Millikan's answer

I want to know the name of an approach (formula) in the first comment of this question (@Ross Millikan's answer) Counting arrays with gcd 1 Thanks
1
vote
2answers
40 views

Identifying if a relation is reflexive, symmetric and/or transitive

I am totally lost on how to identify if a relation is the above. The only thing I know if you have a matrix, and is diagonally symmetric, then it is symmetric, but I do not know why. Could someone ...
2
votes
2answers
19 views

Relations involving division

Can someone explain me how to do it? Let R be a relation on integers such that xRy and iff 3|5x+7y. Show that relation is reflexive ( I am done with it!) and symmetric (I need help with this one).
1
vote
2answers
34 views

Find the transitive closure of a relation

Let the relation $R=\{(0,0),(0,3),(1,0),(1,2),(2,0),(3,2)\}$ Find the $R'$ the transitive closure of R. I honestly don't understand this question at all. Am I being asked to first find $R'$ ...
1
vote
1answer
48 views

Simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph

Why a simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph? In my notes, it says it is easy and leave as an exercise with a hint which want us to show the ...
1
vote
1answer
21 views

Prove the set identity using the laws of set theory

$A\cap(B\cup A')\cap B'=\emptyset$ Using the distributive law I got: $(A\cap B)\cup (A \cap A')\cap B'=\emptyset$ But I don't see any rules to simplify $(A \cap A')$ Any tips in helping me to ...
15
votes
2answers
2k views

There are 10 men, 10 women, and 10 rooms. Each person randomly goes into a room.

What is the expected number of rooms with at least one man and woman? Our prof. gave us the following solution however, I'm confused about the probability portion of the answer (especially the ...
1
vote
0answers
13 views

one to one onto and composition functions [duplicate]

I'm kind of confused about how to prove one to one and onto with functions and composition functions. I am also a visual learner. Could someone tell me step by step how to prove whether or not a ...
1
vote
1answer
18 views

Are two identity functions on different domains equal

This is in my book: EXERCISE: Suppose $f:X→Y$ and $g:Y→Z$ and both of these are one-to-one and onto. Prove that $(g\circ f)^{-1}$ exists and that $(g\circ f)^{-1} = f^{-1}\circ g^{-1}$ SOLUTION: ...
2
votes
1answer
29 views

Getting a full house with exactly 3 suits represented

How many ways can you make a full house with only 3 suits represented in the 5 card hand? My attempt: get the pair first: $$ {13 \choose 1}{4 \choose 2}$$ this allows us to pick any $2$ suits ...
1
vote
2answers
38 views

Prove the relation on $\Bbb N \setminus \{0,1\}$ is a partial order

I'm a bit new to this material and trying understand some problem I'm solving Let $R$ be a relation on the set set = $ \{ N \setminus \{ 0,1\}\} $ that's defined like this: $aRb$ if there is an ...
0
votes
1answer
39 views

Tough second order differential equation2

I have asked similar question before but it turns out that the $E_0$ depends on (r,z). It makes the solution complicated. Any comments appreciated. ...
0
votes
0answers
30 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
0
votes
1answer
44 views

Prove that a preorder is not anti symmetric

Let $\prec$ be a relation on the set $ A = Z \times (N \setminus \{0\}) $ in this way: A. $<a,b> \prec <c,d> $ if $ ad \le bc$ Prove that $\prec$ is a Preorder and show it's not ...
0
votes
0answers
65 views

Simplification problem with discrete mathematics

I am trying to achieve this equation: $$x_1x_4 \lor x_1x_2x_3\lor (¬x_1)x_3(¬x_4)$$ I start with: $$(x_1 \lor (¬x_4))(x_3\lor x_4)((¬x_1)\lor x_2\lor x_4)$$ Then I do simplify in the following ...
0
votes
1answer
24 views

Probability; Coin toss. Discrete Math.

I flip a fair coin, independently, 10 times, resulting in a sequence of heads (H) and tails (T). For each HT in this sequence, you win $3. Define the random variable X to be the amount of dollars that ...
1
vote
1answer
12 views

Finding the size of an intersection of subsets, given several other sizes

I am having trouble with an old exam question that seems to follow a particular format. Essentially you are given a group of X people, some portion of which fall into one category, another portion of ...
1
vote
1answer
21 views

Discreet Math - Given n>= 5 how many times does fib(4) occur?

I have been trying to solve the below problem (and similar problems) but I have no clue how to tackle it. Can please help me tackle this particular problem, and how to attack similar problems? The ...
1
vote
1answer
16 views

Calculating how many elements are in the product of Cartesian multiplication

Let $A = \{1,3\}, B = \{1, 2\}, C = \{1, 2,3\}$. How many elements are there in the set $\{(x,y,z) \in A \times B \times C | x + y = z \} $ ? Two things I'm not familiar with here, First, how ...
0
votes
1answer
9 views

Discrete Math: Probability with subgraphs and coin flips.

Let $K_n$ be the complete graph on $n$ vertices, in which each pair of vertices is connected by an edge. For each each edge $e$ of $K_n$, we flip a fair and independent coin; if the coin comes up ...
0
votes
2answers
21 views

Discrete Mathematics Probability Review Question

Can someone please explain why the following question's answer is (a)? Assume that a newborn baby is a girl with probability p and a boy with probability 1 − p. Also assume that the genders of ...
0
votes
2answers
13 views

Discrete Math Combinatorics Sets and Subsets

Can someone please explain why the following question's answer is (a)? Let S be a set of size 37, and let x and y be two distinct elements of S. How many subsets of S are there that contain x but do ...
0
votes
2answers
30 views

Counting : How many combinations are possible in a sorted set

In a set of n elements, where each element can be any of $ \{0,1,2,3,4,5,6,7,8,9\} $ how many different combinations are possible. Note that all elements are sorted i.e. $\{3,2\}$ is the same as ...
0
votes
2answers
45 views

Probability that a bitstring of length $25$ will contain atleast two $1$s

We choose a bitstring of length $25$ uniformly at random. What is the probability that this string contains at least two $1$s? (a) $1 − \left(\frac12\right)^{25} − 25\left(\frac12\right)^{25}$ (b) ...
1
vote
1answer
30 views

Discrete Math: Combinatorics and recursion

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x and y, but do not contain z? (a) $2^{33}$ (b) $2^{34}$ (c) $2^{35}$ ...
3
votes
2answers
69 views

Integer inequality: $x + y +z> a + b + c$ does not imply $xyz > abc$

Prove by contradiction that for any integers $x,y,z,a,b,c$ greater than $0$ such that $x+y>a+b$, it is not implied that $x\cdot y\cdot z>a\cdot b\cdot c$? Obviously this statement is true. ...
8
votes
4answers
181 views

Help with a recurrence with even and odd terms

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\\ a(2n+1)=a(n)+a(n-1)+1 $$ I don't have much background in solving these things, so I've ...
0
votes
1answer
18 views

Should I repeat the element of a composite of a relation?

Let's say I have to get the composite of a relation: R composite of R. What if the elements in that composite repeat? Should I say it twice? Example: R is a relation. R= { (1,1), (1,2), (1,3), ...
3
votes
2answers
78 views

Finite sum involving Stirling numbers

I am trying to evaluate the following finite sum: $$ \sum_{h=0}^{m}\binom{m}{h}2^{m-h}S(h,k-r)S(m-h,r),\qquad 0\leq r\leq k\leq m, $$ where $S(n,k)$ is the Stirling number of the second kind. Can ...
0
votes
1answer
32 views

probablity review questions.

A jar contains 7 red balls and 9 blue balls. We choose, uniformly at random and without replacement, 5 balls. Let A be the event A = “exactly 2 of the balls are red or exactly 3 of the balls are ...
1
vote
1answer
24 views

Multinomial identity - guidance needed

I need hints on a direction to proove that $$\displaystyle\prod_{k=1}^{n} {{k+1\choose2}\choose k} ={{n+1\choose2}\choose1,2,3.....,n}$$ Any ideas?
0
votes
2answers
37 views

what is the difference between linear transformation and affine transformation?

Recently, I am struglling with the difference between linear transformation and affine transformation. Are they the same ? I found an interesting question on the difference between the functions. But ...
0
votes
2answers
48 views

Find equivalence relations and classes for a given set

Find how many equivalence relations on the set: $\{1,2,3,4,5,6,7\}$ contain the set $\{\langle6,4\rangle,\langle4,7\rangle,\langle3,3\rangle,\langle5,1\rangle\}$ And do not contain the set ...
5
votes
1answer
47 views

Lattice Paths problem

I was assigned to determine the number of "lattice paths" that are in a 11 x 11 square. Recalling that I can only go upwards and rightwards, here is my approach: Note: The red square is the ...
2
votes
0answers
21 views

Need a hint with permutations and pigeonhole-principle question

let $\pi_1,\pi_2,\pi_3\in S_{28}$. Help me prove that there are two sub-sequences of 28 with length 4 $i_1< i_2 <i_3<i_4,\ and\ \ j_1<j_2<j_3<j_4$ so that $\pi_q(i_n)=\pi_p(j_n)$ ...
0
votes
2answers
67 views

Need hint about with pigeonhole principle problem

$a_i$ and $b_i$ are two sequences with $2n$ elements where $\forall i:\ 1\leq i\leq 2n\implies\ 1 \leq a_i , b_i \leq n$ . I need to show that there are two subsets of indexes $I,J\subset [2n]$ so ...
1
vote
1answer
33 views

Counting review(permutations); Discrete Structures [closed]

You are given $6$ distinct books and $5$ identical blocks of wood. How many ways are there to arrange these books and blocks in a straight line? (a) $\dfrac{11!}{4!}$ (b) $\dfrac{11!}{5!}$ (c) ...
0
votes
1answer
31 views

Sets of irrationals whose square contains a rational

Let $S$ be a subset of the irrationals. Also, lets assume that $S$ has infinitely many elements. My very general question is, under what non-trivial conditions does there exist an element $x\in S$ ...
0
votes
0answers
53 views

The cube of at least one irrational number is rational

I am supposed to prove the statement above. Here is what I have so far Suppose that the cube of at least one irrational number $n$, is rational. By definition of rational, there exists ...
2
votes
1answer
23 views

Special Binary Relations/ Empty Relation, Universal Relation And identity Relation?

The universal relation U = A × A. (Correct me if I'm Wrong). I believe that the Universal Relation is an Equivalence Relation The empty relation E = ∅. From my understanding, a Empty relation on a non ...