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

5
votes
3answers
7k views

Expected number of runs in a sequence of coin flips

A coin with heads probability $p$ is flipped $n$ times. A "run" is a maximal sequence of consecutive flips that are all the same. For example, the sequence HTHHHTTH with $n=8$ has five runs, namely H, ...
4
votes
2answers
248 views

Counting the numbers with certain sum of digits.

The question : In how many different numbers between $1$ and $100000000$ have the sum of their digits equal to $45$? I'm thinking about using the stars and bars formula but I'm not sure if it's ...
4
votes
2answers
7k views

Free resources to start learning Discrete Mathematics

Can anyone recommend good, free online articles or books to learn Discrete mathematics? When I google'd for them, I came across few resources..but don't know whether they are good to start learning ...
4
votes
1answer
193 views

How does one prove that $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\leq \frac{1}{\sqrt{3n+1}}?$

I would like to show that $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\leq \frac{1}{\sqrt{3n+1}}$ holds for all natural numbers. I got stuck here: $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{...
4
votes
1answer
412 views

Efficiently evaluating the Motzkin numbers

So I made an error on the question here: $T_N = 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k}$ The correct formula I'm trying to solve is more complicated and as follows: $$T_0 = T_1 = 1 $$ $$T_{N+1} = T_N + \...
4
votes
3answers
2k 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
4
votes
3answers
371 views

Are these two predicate statements equivalent or not?

$\exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y)$ I was told they were not, but I don't see how it can be true.
4
votes
2answers
185 views

If $n$ is squarefree, $k\ge 2$, then $\exists f\in\Bbb Z[x_1,\dots,x_k] : f(\overline x)\equiv 0\pmod n\iff \overline x\equiv \overline 0\pmod n$

Starting from this question, we set $n=k=2$ and use the function $f\in\Bbb Z[x,y]$ where $f(x,y)=x\cdot y+x+y$, then the proofs applied to that question satisfy this case. Note that for $k=1$ the ...
3
votes
3answers
103 views

In how many ways can a $31$ member management be selected from $40$ men and $40$ women so that there is a majority of women?

Here's the question: In an organization there are $80$ people, $40$ men and $40$ women. In how many ways can we choose, from those $80$ people, a $31$ member management so that there is a ...
3
votes
1answer
86 views

Calulating the Ramsey number $R(T, K_{1,n})$ of a tree $T$ and bipartite graph $K_{1,n}$

Let $m,n \ge 2$ be such that $m-1$ is a divisor of $n-1$. Let $T$ be a tree with $m$ vertices. Calculate the Ramsey number $R(T,K_{1,n})$. Thoughts: I'm having trouble approaching this question. I ...
3
votes
3answers
590 views

$x+1/x$ an integer implies $x^n+1/x^n$ an integer

Suppose that $0\neq x\in\mathbb{R}$ and $x + \frac1x\in\mathbb{Z}$. Prove that, for all $n\ge1$, $x^n + \frac1{x^n}\in\mathbb{Z}$. I can't figure out and understand the question. Can you give me ...
3
votes
3answers
467 views

Coloring dots in a circle with no two consecutive dots being the same color

I ran into this question, it is not homework. :) I have a simple circle with $n$ dots, $n\geqslant 3$. the dots are numbered from $1\ldots n$. Each dot needs to be coloured red, blue or green. No ...
3
votes
2answers
89 views

Prove $\sum_{i=1}^n i! \cdot i = (n+1)! - 1$?

Prove the summation: $$\sum_{i=1}^n i! \cdot i = (n+1)! - 1$$ using induction. base case: $n=1$: \begin{align*} \sum_{i=1}^1 i! \cdot i &= (1+1)! - 1 \\ 1 &= 2 - 1 \\ 1 &= 1 \end{align*...
3
votes
2answers
247 views

Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
2
votes
3answers
83 views

Prove that $\frac{1}{1*3}+\frac{1}{3*5}+\frac{1}{5*7}+…+\frac{1}{(2n-1)(2n+1)}=\frac{n}{2n+1}$

Trying to prove that above stated question for $n \geq 1$. A hint given is that you should use $\frac{1}{(2k-1)(2k+1)}=\frac{1}{2}(\frac{1}{2k-1}-\frac{1}{2k+1})$. Using this, I think I reduced it to $...
2
votes
3answers
703 views

Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$

I haven't been able to do this exercise: Let $f: A \rightarrow B$ be any function. $f^{-1}(X)$ is the inverse image of $X$. Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$ where $X ...
2
votes
1answer
204 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
2
votes
3answers
10k views

Sum of digits and product of digits is equal (3 digit number)

My child got a question in school (grade) that is: Find biggest and smallest 3 digits number, which has sum of it's digits equal to product of those digits. Help please since I cannot explain my ...
2
votes
2answers
331 views

$a, b \in\Bbb N$, find all solutions to $2^a = b^2 - 5$ and prove there are no more solutions?

I am currently studying discrete mathematics at uni (in my computer science degree). We have an assignment due tomorrow, and i have been able to do most of it, but one question eludes me. I spoke to a ...
2
votes
1answer
1k views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
1
vote
3answers
482 views

Proving statement - $(A \setminus B) \cup (A \setminus C) = B\Leftrightarrow A=B , C\cap B=\varnothing$

I`m trying to prove this claim and I need some advice how to continue, $$(A \setminus B) \cup (A \setminus C) = B \Leftrightarrow A=B , C\cap B=\varnothing$$ what I did is: $$(A \setminus B) \cup (A \...
1
vote
1answer
113 views

Proving Set Operations

I'm trying to prove that if $A$ is a subset of $B$ then $A \cup B = B$, but I am having trouble trying to proves this mathematically. I know that since $A$ is a subset, then $A$ has an element $x$ ...
1
vote
3answers
4k views

Let A and B be sets. Show that A is a subset of B if and only if for any set C, one has A union C is a subset of B union C.

Can you verify my proof if it is right? Let $A$ and $B$ be sets. (a) Show that $A$ is a subset of $B$ if and only if for any set $C$, one has $A$ union $C$ is a subset of $B$ union $C$. (b) Show ...
1
vote
1answer
274 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, $f:2^{\Omega}\...
1
vote
3answers
109 views

How many positive integers $ n$ with $1 \le n \le 2500$ are prime relative to $3$ and $5$?

I am trying to understand this example from my study guide and am getting no where with it and need some help. Example: How many positive integers $n$ with $1 \le n \le 2500$ are prime relative to $3$...
1
vote
2answers
124 views

Proving a triangle with different edge colors exists in a graph.

This is again some homework translated (hopefully not too badly) from my book The graph $K_{n}$ is colored using $n$ different colors, in a way that each color is used at least once. Prove that there ...
1
vote
2answers
896 views

Matrix exponential of a skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. Question 1) How do I compute $e^{...
1
vote
1answer
249 views

Functions that are sets of all function - proofs

I'm going through the book Proofs and fundamentals, by Bloch, and it doesn't include a solution manual for it's examples. It doesn't have many examples on notation and proof strategy for certain cases,...
0
votes
1answer
44 views

strong induction postage question

Use strong Principle of induction to prove that the amount of postage greater than or equal to $30$ cents can be made using a combination of $10$ cent and $3$ cent postage this is what i have so far:...
0
votes
2answers
1k views

Combinatorics: Number of subsets with cardinality k with 1 element.

Consider the set |n| = {1,2,...,n}. How many subsets does it have of cardinality k and that contain the element 1? I understand that with each element, you can either include it or not to have a ...
0
votes
1answer
104 views

Properties of the greatest common divisor: $\gcd(a, b) = \gcd(a, b-a)$ and $\gcd(a, b) = \gcd(a, b \text{ mod } a)$

Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r). I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) = ...
0
votes
2answers
53 views

Number of functions from n-element set to {1, 2, …, m}

I've gotten stuck at the following exercise; There are m functions from a one-element set to the set {1, 2, …, m}. How many functions are there from a two-element set to {1, 2, …, m}? From a ...
0
votes
1answer
537 views

Discrete Math Counting Question

I need help with one of those question where you have to count the number of ways you can place r objects into n distinct boxes kinds. I was wondering if someone could solve an example in detail. How ...
-1
votes
1answer
76 views

Number of Elements Not divisble by 3 or 5 or 7 [closed]

if A={1,2,...,600} includes all natural numbers between 1 to 600. I want to find number of elements of A that not divisible by 3 or 5 or 7? any hint or idea?
7
votes
8answers
3k views

What is an example of function $f: \Bbb{N} \to \Bbb{Z}$ that is a bijection?

Could you give me an example of function $ f \colon \mathbb N \to \mathbb Z$ that is both one-to-one and onto? Does this work: $f(n) := n \times (-1)^n$? N starts with zero.
7
votes
4answers
139 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
6
votes
2answers
766 views

Distribution of points on a rectangle

Let $R$ be a rectangular region with sides $3$ and $4$. It is easy to show that for any $7$ points on $R$, there exists at least $2$ of them, namely $\{A,B\}$, with $d(A,B)\leq \sqrt{5}$. Just divide $...
6
votes
1answer
574 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
5
votes
8answers
190 views

Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$ I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the ...
5
votes
3answers
339 views

Help with Cartesian product subsets [duplicate]

I want to prove that if $A \subseteq C\,$ and $\,B \subseteq D,\,$ then $\,A \times B \subseteq C \times D.$ I know that $A \subseteq C \iff a \in A \rightarrow a \in C$ and that $B\subseteq D\iff ...
5
votes
3answers
439 views

Generating Functions- Closed form of a sequence

We are given the following generating function : $$G(x)=\frac{x}{1+x+x^2}$$ The question is to provide a closed formula for the sequence it determines. I have no idea where to start. The denominator ...
5
votes
1answer
183 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
4
votes
2answers
151 views

Need a counter example for cycle in a graph

Could anyone give a counter example for that theorem : A graph G has exactly one vertex of degree $1$, then it contains a cycle. I am so confused. I wonder that may I give a counter example ...
4
votes
5answers
4k views

Equivalence relation $(a,b) R (c,d) \Leftrightarrow a + d = b + c$

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
4
votes
3answers
1k views

Definition of a countable set

What is the proper definition of a Countable Set?
4
votes
2answers
155 views

Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$.

For $a,b \in \mathbb{R}$ define $a \sim b$ if $a - b \in \mathbb{Z}$ I don't understand how I'm suppose to prove this: Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$ Also can you ...
4
votes
1answer
2k views

Is there a formula for finding the number of nonisomorphic simple graphs that have n nodes?

As my subject line asks, is there a formula for finding the number of nonisomorphic simple graphs there are with n nodes, outside of trial, error, and enumeration over max degrees of vertices? Thanks ...
3
votes
1answer
3k views

Proof regarding Connected Graphs with even number of vertices.

I'm unsure as to how to go about continuing this proof. I have to prove that for an undirected graph $G = (V,E)$ where $n = |V|$ and $n$ is even, that the graph is connected for all $n \ge 2$, if ...
3
votes
4answers
112 views

Proving for all integer $n \ge 2$, $\sqrt n < \frac{1}{\sqrt 1} + \frac{1}{\sqrt 2}+\frac{1}{\sqrt 3}+\cdots+\frac{1}{\sqrt n}$ [duplicate]

Prove the following statement by mathematical induction: For all integer $n \ge 2$, $$\sqrt n < \frac{1}{\sqrt 1} + \frac{1}{\sqrt 2}+\frac{1}{\sqrt 3}+\cdots+\frac{1}{\sqrt n}$$ My attempt: Let ...
3
votes
1answer
295 views

The number of regions into which a plane is divided by n lines in generic position [duplicate]

Suppose that $n$ lines are drawn on a plane in such a way that no lines are parallel and no three of them intersect at a point. Let $r(n)$ be the number of regions the plane is divided into after ...