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

0
votes
1answer
23 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
54 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?
0
votes
1answer
71 views

Generating function

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
121 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
131 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? ...
3
votes
3answers
77 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
51 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
35 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
34 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
42 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
60 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
81 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
33 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
44 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 ...
6
votes
3answers
146 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
130 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
91 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
65 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
1answer
86 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
76 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
60 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
47 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
34 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
43 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
1answer
257 views

How many different answer keys are possible?

A professor writes $40$ discrete mathematics true/false questions. Of the statements in these questions, $17$ are true. If the questions can be positioned in any order, how many different answer keys ...
74
votes
15answers
12k 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
49 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
137 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
54 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
68 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
215 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 ...
4
votes
3answers
109 views

Compass-and-Straightedge Construction [closed]

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
34 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
425 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
121 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
65 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
88 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 ...
6
votes
1answer
134 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
55 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
835 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
30 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
27 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
41 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 ...
0
votes
1answer
143 views

Turing machine that accepts even length strings

Can someone help me with some tips on how to create a turing machine that only accepts even length strings with an input alphabet of {0,1}?
2
votes
1answer
88 views

Find number of solutions of this equation using generating function

I'm given an equation $x_1 + x_2 + x_3 + x_4 + x_5 = 24$, with a restriction that all of $x_i > 1$ and 2 of them are odd, the rest are even natural numbers. I can solve this using the following ...
2
votes
1answer
63 views

Writing a sentence that is true in one model and false in the other

Let $Σ=(R)$, where $R$ is a binary relation. Write a sentence that is true in $\mathcal M_1$ but false in $\mathcal M_2$: $$\mathcal M_1=(P(N),⊂)$$ $$\mathcal M_2=(N,<)$$ I've been ...
3
votes
0answers
34 views

Joint distribution of degrees of Erdös Renyi random graph

The marginal degree distribution of any particular vertex is $$Bin(n-1,p)$$ in an Erdös Renyi random graph G(n,p). Denoting the degrees of the n vertices as d1,d2,...,dn, can you please let me know ...
0
votes
3answers
120 views

Associative, but non-commutative binary operation with a identity and inverse [closed]

Can there really be an associative, but non-commutative binary operation with a identity and inverse?
1
vote
1answer
49 views

Mathematical proof for approximated equation basing on sets

Given $n$ sets i.e., $A_1, A_2,\dots, A_n$ where $|A_i|$ is the number of elements in the set $A_i$, let $U=A_1\cup A_2\cup\dots\cup A_n$. Can anyone prove that for sequences ...
2
votes
0answers
41 views

${n \choose m}$ on periodic lattice (Bravais)

How can I generate all symmetry-inequivalent selections of m sites on a periodic 2d (Bravais) lattice with n sites? Are there some general results or theorems which may be useful in this type of ...