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

2
votes
2answers
50 views

Question on connected graphs

Is it true that if for each partition of a graph G's vertices into two non empty sets there is an edge with end points in both sides then G is connected? Intuitively this seems true to me. But I ...
1
vote
0answers
52 views

Showing that two given graphs are homeomorphic

I won't to verify whether the two graphs given above are homeomorphic. I am not sure of the method to verify this. I would much appreciate if anyone could give some assistance. Thanks
0
votes
0answers
60 views

Is an isolated vertex a component of a graph?

I want to know if an isolated vertex can be considered as a component of a graph. Answers will be appreciated.thanks
0
votes
2answers
562 views

In a survey of 270 college students, it is found that 64 like brussels sprouts

In a survey of 270 college students, it is found that 64 like brussels sprouts, 94 like broccoli, 58 like cauliflower, 26 like both brussels sprouts and broccoli, 28 like both brus- sels sprouts and ...
1
vote
1answer
136 views

A marketing report concerning personal computers/Inclusion–Exclusion

A marketing report concerning personal computers states that 650,000 owners will buy a printer for their machines next year and 1,250,000 will buy at least one software package. If the report states ...
1
vote
0answers
48 views

Finding the diameter of a graph with a complex structure

I know the diameter of the above graph is 6. But I don't know a formal way of doing this. However I know it is possible to draw a matrix considering the minimum distance between the vertices but ...
2
votes
2answers
197 views

Mantel's Theorem proof verification

I found the following proof for Mantel's proof. I cannot understand the equality that I have highlighted in the image was arrived at. I would appreciate some assistance thanks
0
votes
0answers
27 views

Prove Eulerian directed path on a digraph

In an undirected and connected graph $G$, replace each edge by a pair of directed edges (round trip). How can I prove that the resulting digraph has an Eulerian directed path?
0
votes
1answer
66 views

Calculating a union of 2 relations

I have 2 relations: $$ xSy \Leftrightarrow y = 2x$$ and $$ xTy \Leftrightarrow y = 3x$$ The problem I have is calculating $$x(T \cup S)y$$ and $$xS^+y $$ Could you please help me?
0
votes
1answer
47 views

probability ratio question

From n men and n women one wants to select k male and k female candidates, to create either a committee or a ballot. In a ballot the members are fully ranked (first, second, ...); in a committee they ...
0
votes
2answers
164 views

Graph theory people at a round table problem

So I have this problem: There are 20 people at a party and each one of them is friends with at least 10 of the people. They all sit at a round table. Prove that there is a way to place the people on ...
0
votes
3answers
329 views

Book on modular arithmetic

I am searching for some good book which section is devoted to modular arithmetic. I am self learner so I strongly prefer that book has exercises best with answers or solutions. I have CS background ...
0
votes
2answers
505 views

The number of non-decreasing sequences of digits

What's the numer of n-digit natural numbers, in which digits are in non-decreasing order? I know the answer is $ n+8 \choose 8$, but I don't understand how to get this score - could anyone try to ...
7
votes
1answer
176 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
0
votes
1answer
72 views

How to show or prove equivalence relation?

I have this relation : for all integers m and n so : m R n ⇔ m ≡ n mod(3) How can I show that R is an equivalence relation
0
votes
2answers
56 views

How to concisely express the idea that one value of several in a set can make the values of all others moot.

I've been trying to find a way to write this all day. I've learned a lot of math in the process, but still haven't found anything especially concise. I'm trying to express the idea that if you have ...
2
votes
2answers
311 views

Finding the diameter of a n-cube

Is there a general method that can be used find the diameter of a n-cube? In particular what if I want to find the diameter of a 4-cube can someone suggest me a method or hint. I would much appreciate ...
2
votes
1answer
259 views

How to check the validity of this argument using the rules of inference?

I have this argument : I play basketball and football. If today isn't Saturday, then I play basketball and football. If today is Friday OR today is Saturday, then I don't play football. Therefore, ...
2
votes
2answers
101 views

Clarifying Dirac's theorem

Theorem : If $G$ is a simple graph with $n$ vertices with $ n ≥ 3$ such that the degree of every vertex in G is at least $ n/2$, then $G$ has a Hamilton circuit. In this if $n$ is odd, should I ...
1
vote
1answer
49 views

find all subcartesian products of $S_4$ and $D_{12}$

The following exercise is from [Cameron, Permutation Groups]: Find all permutation groups of degree 10 which have orbits of length 4 and 6 and act on these orbits as the symmetric group $S_4$ and ...
1
vote
0answers
33 views

Necessary and sufficient condition for an Euler circuit

I have come across the theorem A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. I just want to know whether the same holds ...
1
vote
0answers
69 views

Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
0
votes
2answers
121 views

3-dimensional cube shortest path question

Let Q be the graph consisting of vertices and edges of a 3-dimensional cube. Two relations are defined on the vertices of Q. • R1={(v,w):the shortest path from v to w has an odd number of edges}. ...
1
vote
2answers
61 views

Single error correcting binary code of length $16$ and size $2^{12}$

Consider there is a 12 bit data, and we want to add 4 check bits, such that 1-bit errors can be detected and corrected. How can this be done ? Consider the data as : b15 b14 b13 b12 b11 b10 b09 b08 ...
0
votes
2answers
92 views

Math basic five properties question.

We define a relation $R\subseteq\mathbb Z\times\mathbb Z$ where $(a,b)\in R$ exactly when $a+2b$ is divisible by $3$. Determine how many of the basic five properties of reflexivity, symmetry, ...
2
votes
1answer
99 views

Concrete Mathematics Reducing sums to closed form

In reducing the sum $S_n = \sum_{1\leq j<k\leq n}(\frac{1}{k-j})$ to a closed form, the authors start by replacing $k$ with $k+j$, such that $S_n = \sum_{1\leq j<k+j\leq n}(\frac{1}{k})$. The ...
1
vote
2answers
61 views

A $C_3$ free graph, degrees inequality

If $G$ is a $C_3$ free graph, for any edge $(x,y)$ of $G$ I need to prove that $$\deg(x)+\deg(y)<|V(G)|+1.$$Any hints/answers will be much appreciated. Thanks
0
votes
1answer
135 views

Composition of three functions [duplicate]

If $f:W\rightarrow X$, $g:X\rightarrow Y$, and $h:Y\rightarrow Z$, does $h \circ (g \circ f) = (h \circ g) \circ f$? How can I justify this?
0
votes
1answer
103 views

Permutations of word 'mathematics'

How many arrangements are there of MATHEMATICS with both T's before both A's or both A's before both M's or both M's before the E ? Can someone also point to some online resource that has such ...
1
vote
3answers
231 views

could not able to understand Project Euler 18. “Maximum path sum I”

According to question, By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. ...
1
vote
2answers
58 views

Combinatorics Question: Alphabet of $16$ letters, $8$ slots, arbitrary blanks

If I have an alphabet of $16$ characters and $8$ slots that are filled with any combination of characters (no duplicates except blanks), how do I calculate the total number of combinations? Edit for ...
-1
votes
1answer
125 views

Sum of digits of a number raised to a power

Let $f$ be a function such that it takes a non-negative integer in decimal representation and gives the sum of its digits raised to $2001$ (e.g. $f(327)=3^{2001} + 2^{2001} + 7^{2001}$). Prove that ...
1
vote
1answer
140 views

Convert algebraic formula to CNF

Consider the following test: $$\sum_{i=1}^n{a_ib_ic_i} \overset{?}{=} q,\tag1$$ where $a_i, b_i, c_i \in \{-1, 0, 1\}$ and $q \in \{0, 1\}.$ Is it possible to rewrite [1] to conjunctive normal ...
0
votes
2answers
71 views

Fact About Equality Proven by Euler in 1748 (Context: Integer Partitions)

I'm currently reading Integer Partitions by Andrews and Eriksson. In the introductory chapter (p.2), there is the following statement: ... The table would have a more efficient design: ...
2
votes
4answers
1k views

Satisfiability Problem: Determining Which People To Invite

When planning a party you want to know whom to invite. Among the people you would like to invite are three touchy friends. You know that if Jasmine attends, she will become unhappy if Samir is ...
2
votes
3answers
59 views

If $ \langle G, \star \rangle $ is an abelian group, then for all $a, b \in G$, show that $(a \star b)^{n} = a^{n} \star b^{n}$.

If $ \langle G, \star \rangle $ is an abelian group, then for all $a, b \in G$, show that $(a \star b)^{n} = a^{n} \star b^{n}$. I am stuck at the first step, unable to figure out how to start. I am ...
4
votes
2answers
367 views

Understanding definition of big-O notation

In a textbook, I came across a definition of big-oh notation, it goes as follows: We say that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$|f(x)| \le C|g(x)|$$ whenever $x \gt ...
1
vote
0answers
65 views

Comprehensive collection of combinatorial identities - with proofs

I read the answers to A comprehensive list of binomial identities?, and although there are links to listings of combinatorial identities without proofs, I am looking for such resources which have ...
0
votes
1answer
49 views

Simplifying a geometric series

I seem to be completely misunderstanding something about the simplification of a geometric series. $$\sum_{j=1}^{n+1} ar^j = \sum_{j=0}^n ar^j + (ar^{n+1}-a)$$ Why does this work? From what I tested, ...
2
votes
3answers
79 views

combinatoric question - balls arrangement

In how many ways can you arrange 200 balls into 40 cells, such that the sum of balls in cells 1-20 is greater (not equal) the sum of balls in cells 21-40? So, the number of posibilities can be ...
1
vote
2answers
52 views

Constructing equivalent matrices with rows and columns exchanged

I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and ...
3
votes
0answers
121 views

to find the graphs having vertices with same eccentricity

I was reading a paper http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=plik&nIdA=11134&sTyp=HTML&nIdSesji=-1 There is a formula to calculate eccentricity in the section ...
1
vote
4answers
118 views

A bijection between (0,5) and (10,20)?

My teacher gave this question: "Is there a bijection between sets (0,5) and (10,20)" ? I was thinking that it doesn't but I am not exactly sure...could someone clarify ?
0
votes
2answers
226 views

Probability Of Rolling A Strictly Increasing Sequence On A Six-Sided Die

By rolling a six-sided die 6 times, a strictly increasing sequence of numbers was obtained, what is the probability of such an event? I have no ideas on how to attack this. It says, an ...
0
votes
1answer
74 views

discrete math question with function growth

Consider three functions, defined recursively, each with the same initial value $V(1)=T(1)=U(1)=3$ but different recurrence relationships for $n>1$: ...
1
vote
2answers
36 views

binary representation shrinkage question

Suppose for a given number $n$, every operation is to add $+$ signs arbitrarily into its binary representation. Repeat this process $K$ times. Prove: It is always possible to reduce the number to ...
12
votes
3answers
388 views

$\frac{1}{7} + \frac{1\cdot 3}{7\cdot 9} + \frac{1\cdot 3\cdot 5}{7\cdot 9\cdot 11} + …$

If the sum $\frac{1}{7} + \frac{1\cdot 3}{7\cdot 9} + \frac{1\cdot 3\cdot 5}{7\cdot 9\cdot 11} + ...$ to 20 terms is $\frac{m}{n}$, reduced fraction, then what is $n-4m$? This is a question I dug ...
1
vote
0answers
47 views

maximum number of pendant vertices in a graph

Can anybody help me in providing a simple hint to my problem. I was just thinking how many pendant vertices a graph can have where diameter of the graph, $diam(G)\geq3$, after leaving the graph $P_4$. ...
4
votes
2answers
179 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
3
votes
1answer
61 views

Book stacking problem with consecutively lighter books

I'm currently working on problem 6a of this problem set from MIT Open Course Ware. It's a spin on the book stacking problem. In this scenario, any additional books you stack beyond the first one has ...