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
4answers
78 views

Probability formula, a value chosen at random is greater than another chosen value.

Say I have two number ranges, whole numbers only. Range 1: [-3,16] Range 2: [3,22] I choose randomly one number from Range 1 and one number from Range 2. Lets call them x and y. How do I find the ...
0
votes
1answer
22 views

Can rules of inference be used in one side of an implication?

I am trying to understand rules of inference and I am not sure if they can be used in this way. For example, let's say we have the premises: (a) $(p ∧ q) → (r ∨ s)$ (b) $¬s$ Can it be concluded ...
1
vote
3answers
29 views

Discrete math help : $a_n=−3a_{n−1}$ for $n\geq 2$ with the initial condition $a_1=−12$.

I am thoroughly confused , and am not sure how to solve this. Could someone please walk me through this. I have an idea how to do it with an $a_0$ and an $a_1$ , but not this one.
-2
votes
1answer
41 views

What is the probability that exactly $19$ of them get the correct helmet? [closed]

There's $20$ people on a team with helmets. They take them off and the helmets get all mixed up. All $20$ put them back on randomly. What is the probability that exactly $19$ of them get the correct ...
2
votes
2answers
28 views

Discrete math: $a_n=14a_{n−1}−33a_{n−2}$ for $n≥3$ with initial conditions $a_0=−24,a_1=−200$

Can someone please help me understand this? This is what I got but it isn't correct. $a_n=14a_{n−1}−33a_{n−2}$ for $n≥3$ with initial conditions $a_0=−24,a_1=−200$. Solve for $a_n$. $t^2 = -14t+33$ ...
0
votes
2answers
39 views

elementary counting and specify the generating function

Let $k\geq1$, and let $b_n$ be the number of words $\omega=v_1 \cdots v_n$ over the alphabet $\Sigma=\{1,\dots k\}$ such that $v_i\neq v_{i+1}$ for $1\leq i\leq n-1$. I have to show with elementary ...
0
votes
1answer
18 views

Composing the Identity Function

Let $T = \{1, 2, 3\}$ and $S$ be the set of all permutations of $T$. Prove that $I\circ f = f$ and $f \circ I = f$ for all $f \in S$. $I \circ f = I(f(t))$, so $I(f(1)) = f(1), I(f(2)) = f(2), ...
2
votes
1answer
32 views

Characterization of degree sequence of a forest

One problem in Graph Theory: An Introductory course by Bollobas asks to characterize the degree sequence of a forest. How should I solve this problem?
-1
votes
1answer
63 views

Generating function [closed]

Let f(n,m) the number of der path from (0,0) to (n,m) $\in \mathbb{N}^2$ wich consists the steps (0,1), (1,0) and (1,1)and set f(0,0) to 1. Let $a_i = \sum_{n+m=i}f(n,m), i\geq 0$ i) Show that: ...
1
vote
1answer
32 views

Listing elements from set-builder notation, and vice versa

I have trouble translating from a set-builder notation to a "dotted set" $$\{\ldots,v_1,v_2,v_3,\ldots\}$$ and vice-versa. Set-builder to dotted set: $$\begin{align*} A &= \{5a+ 2b : a,b \in ...
0
votes
2answers
56 views

Probability of Poker Hands with Joker

Need help with a homework question: If a five card hand from a standard deck of 52 with an added joker (wildcard) is drawn: What is the probability that a hand contains at least one pair? ...
2
votes
2answers
49 views

Simplify sum $\sum_{i=0}^k(-1)^ii\binom{n}{i}\binom{n}{k-i}$ for $n\geq k\geq 0$

The problem asks us to simplify the following sum: $$\sum_{i=0}^k(-1)^ii\binom{n}{i}\binom{n}{k-i}$$ for $n\geq k\geq 0$. I've tried the following: ...
1
vote
3answers
25 views

Proving the number of leaves is larger by at least two than the number of vertices with a degree of at least 3

Prove that in every tree, the number of leaves is larger by at least two than the number of vertices with a degree of at least 3. Trying induction, I get something that is too short to be right, ...
0
votes
0answers
28 views

How to explain this simplification here?

I can't understand this simplification the book says without explanation. Could someone help me? It is the calculatation/development of the transfer function of a digital system composed by a dac ...
2
votes
0answers
26 views

What determines the number when excluding in Inclusion Exclusion problems

My question might be a bit poorly articulated as I am not sure what I'm asking is actually called. I am faced with an Exclusion/Inclusion problem that goes like this: You have $25$ identical cakes ...
0
votes
2answers
41 views

Why does this inequality stand?

I stand that $\log n=O(n^{\epsilon})$ for any $\epsilon >0$. At a previous example we have shown that $$e^{n^{\epsilon}} \geq \frac{n^{\epsilon d}}{d!}$$ where $d=\lfloor ...
7
votes
1answer
52 views

Partitioning $n$ naturals summing $2N$ into two sets summing $N$

I'm trying to solve this problem: Let $a_1, \ldots , a_n$ be natural numbers such that $a_k \le k$ for every $k = 1,\ldots,n$, and $\sum_{k=1}^{n} a_k=2N$. Show that there exists a partition of ...
3
votes
2answers
72 views

Tangent numbers are divisible by $2^{n}$

Let us consider a $$\tan(z) = \sum_{n=1}^{\infty}{T_{2n-1} \cdot \frac{z^{2n-1}}{(2n-1)!}}$$. So, it can be shown that $$T_{2n+1}=\frac{(-1)^{n} 4^{n+1}(4^{n+1}-1) B_{2n+2}}{2n+2} $$ where $B_{2n+2}$ ...
0
votes
2answers
28 views

Space station, alarms, and malfunction

A space station has a set $A = \{A_1,A_2,A_3,A_4,A_5\}$ of 5 distinct alarms that indicates 3 abnormal conditions (without distinction between them). How many ways can the alarms be associated to the ...
1
vote
1answer
16 views

Prove that in the union of two trees there exist a vertex with degree of at most $3$

Let $T_1=(V, E_1), T_2=(V,E_2)$ be trees on the same set of vertices, and let $G=(V,E_1 \cup E_2)$ be the graph resulting from the union of the two trees. Prove that there exist a vertex with ...
5
votes
3answers
93 views

How can I find this recurrence relation? My approach seem to be wrong.

QUESTION: A string that contains only 0s, 1s, and 2s is called a ternary string. Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s ...
-1
votes
1answer
90 views

Nonisomorphic connected 2-regular graphs

A $k$-regular graph on $n$ vertices is a graph in which the degree of every vertex is $k$. How to show that the number of non-isomorphic connected 2-regular graphs is $\frac {(n-1)!} {2}$
3
votes
2answers
72 views

Logic and proof

I had an assignment from class, to proof for all real numbers $R$, $x$ is subsets of $R$, if $x^2 - 2x\ne -1$, then $x\ne 1$. in contrapositive proof and contradiction. So far with my knowledge, ...
0
votes
2answers
62 views

why is $(0,1) \subseteq$ $\mathbb{R}$ \ $\mathbb{N}$

why is $(0,1) \subseteq$ $\mathbb{R}$ \ $\mathbb{N}$ Sorry it seems very simple but can't get my mind to understand why, I feel like $\mathbb{R}$ \ $\mathbb{N}$ = {all negative numbers and ...
0
votes
2answers
81 views

Prove by induction that $\sum_{i=1}^{n} 2i=(n+1)n$, for every positive integer n. [duplicate]

Can anyone explain the concept behind this? I just don't get how I should proceed with it? Like each step, why and how is it done? Prove by induction that $\displaystyle\sum_{i=1}^{n} 2i=(n+1)n$, ...
0
votes
2answers
58 views

(603 · 6004 + 60005) mod 6 is equal to?

Any help here? i have an upcoming exam, and the question in some of the exercises that im practicing on are (603 · 6004 + 60005) mod 6 is equal I just dont understand how to do it. The way i saw it ...
0
votes
1answer
48 views

How to finish this proof by contradiction?

The Problem: You were planning to study real hard this quarter so you took out n books on algorithms. However you had better planning than execution and you have not read a single book and they are ...
2
votes
1answer
38 views

Prove that if G is a digraph who underlying graph is regular, then then following formula holds.

Prove that if $G$ is a digraph whose underlying graph is regular, then $$\sum_{i=1}^n\operatorname{outdeg}^2(v_i)=\sum_{i=1}^n\operatorname{indeg}^2(v_i)\;.$$ This is a assignment problem, so ...
0
votes
0answers
21 views

Determine complexity of algorithm

I have two pieces of code below. a) sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++ ; b) ...
0
votes
1answer
21 views

$z \cdot \cot(z)$ series

Let us consider an expansion $z \cot(z) = \sum_{n=0}^{\infty}{(-4)^{n} \cdot B_{2n} \cdot \frac{z^{2n}}{(2n)!}}$. How to prove the RHS? I see possible to come to the expansion $\pi \cot(\pi z) = ...
0
votes
0answers
29 views

how many different answer keys are possible?

A professor writes 40 discrete mathematics true/false questions. Of thestatements in these questions, 17 are true. If the questions can be positioned in anyorder, how many different answer keys are ...
59
votes
16answers
11k views

What is the smallest unknown natural number?

There are several unknown numbers in mathematics, such as optimal constants in some inequalities. Often it is enough to some estimates for these numbers from above and below, but finding the exact ...
1
vote
1answer
41 views

Binomial cumulative distribution calculation

I have exercise like this: Given probability of success of 0.8 what's probability that in 1000 trials there was more than 800 successes? So it's quite simple exercise: It's binomial distribution ...
5
votes
2answers
75 views

Are the rules of this tournament fair?

My daughter just took part to a volleyball tournament and she wonders whether the rules of the tournament were fair or not. There are 10 teams, gathered into 3 groups: Group 1 with 4 teams and Groups ...
1
vote
1answer
49 views

How does one construct a rigorous proof?

I know this may sound too vague to be given a thought but I realised that this is a problem I often have when I have to prove a given statement. How does one actually go about setting parameters that ...
2
votes
1answer
46 views

How to find the generating function

What is the generating function for ${a_k}$, where $a_k$ is the number of solutions of $x_1 + x_2 + x_3 = k$ when $x_1,x_2,x_3$ are integers with $x_1 \geq 2$, $0 \leq x_2 \leq 3$, and $2 \leq x_3 ...
0
votes
2answers
35 views

There are 6 candidates. If two refuse to be positioned next to each other, they can be arranged in 480 ways?

True or false. Six candidates for mayor are to participate in a debate. Candidates are lined up on stage behind podiums facing the audience. If two of the candidates refuse to be positioned next ...
5
votes
3answers
86 views

Compass-and-Straightedge Construction

I stumbled upon this question in math class, and I got stuck. The Question: You're are given a circle, and two points. How do you construct a circle that goes through the two points and is tangent to ...
0
votes
2answers
22 views

$R_1$ and $R_2$ are partial orders. What about $R_1 \cap R_2$?

Let $R_1$ and $R_2$ be two partial order relations defined on a set S. Show that $R_1 \cap R_2$ is also a partial order on S. I am struggling to represent $R_1$ and $R_2$ in a way I can operate with ...
3
votes
1answer
119 views

Applications of propositional logic

I'm working on this propositional logic question and I did not understand the book answer at all. The book says the hostess knows to bring back two drinks for the first two professors. When ...
0
votes
1answer
28 views

Scheduling: Moore's algorithm

In scheduling we have Moore's algorithm to minimize the the number of late jobs. Because of the EDD-rule (earliest due date first), I guess this algorithm has complexity $\mathcal{O}(n \log n)$. I ...
1
vote
1answer
59 views

How to find $r$ in an equation like this: $r^3= xr+y$

Can anyone give me an an idea how to solve this and find $r$, where $r^3= xr+y$ and $x$ and $y$ are known numbers?
2
votes
2answers
62 views

Integer partitioning

Suppose we have an integer $n$. I we want to partition the integer in the form of $2$ and $3$ only; i.e., $10$ can be partitioned in the form $2+2+2+2+2$ and $2+2+3+3$. So, given an integer, how to ...
-3
votes
0answers
107 views

Probability of intersection of sticks?

Start with two sticks, one of length $p$ and the other with length $q$. The sticks can be placed horizontally on the $x$-axis. For the first stick, its left end can lie anywhere on $[0 , a]$, and for ...
7
votes
1answer
108 views

$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances ...
2
votes
1answer
50 views

Need a closed formula for the generating function $x/(1+x+x^2)$.

I used partial fractions but the obtained formula is only correct for the first two elements. $\dfrac{x}{(1+x+x^2)}=\dfrac{x}{(1+a_1x)(1+a_2x)}=\dfrac{A_1}{(1+a_1x)+A_2(1+a_2x)}$ $x=\dfrac{-1 ...
2
votes
4answers
61 views

what is the maximum number of edges in a graph with self-loop?

If we have a graph G with n nodes, what is the maximum number of edges in this graph if we allow self-loop, is it n^2 and why, please look at the graph bellow: N=4, is maximum number of edges=16 or ...
1
vote
1answer
23 views

Scheduling: tasks on machines

Consider a one-machine model where we want to minimize $\sum_{j=1} ^{n} T_j$, where $T_j $ is the tardiness of a job. We define $T_j = max(0, L_j)$, with $L_j = C_j - d_j$. $C_j$ is the completion ...
1
vote
0answers
25 views

Show $f_m:=\prod \limits_{i=0}^{m}(1+x^{2i+1})$ forms a cauchy sequence

Let $f_m:=\prod \limits_{i=0}^{m}(1+x^{2i+1})$ Show that: $$(f_m)_{m\geq0} \text{ forms a Cauchy sequence in } \mathbb{C}[[]] $$ $\mathbb{C}[[x]]:={\sum_{n\geq0}a_nx^n \text{ | } a_n\in\mathbb{C}}$ ...
0
votes
2answers
29 views

Is a composite function $g \circ f$ an injection? If so, is $f$ an injection, too?

Let $f: S \rightarrow T$ and $g: T \rightarrow U$. The function $h: S \rightarrow U$ given by $h(s)=g(f(s))$ is the composite function of $g$ and $f$, denoted by $h=g \circ f$. Prove that, if $g \circ ...