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
30 views

Proof of R is transitive if and only if $R^{-1}$ is transitive.

Question:Let R be a realation in a set X. Prove that $R$ is transitive if and if only if $R^{-1}$ is transitive. My proof $R$ is transitive ≡ [(x, y)∈R∧(y, z)∈R⇒(x, z)∈R] by the def. of a ...
1
vote
1answer
37 views

Question about onto function

I came across this question when doing an online test about onto function. Here's the question and the correct answer given. However, for $b = -1$ $\in$ $B$ $\{-1, 0, 1, 2, 3, ..\}$ I can't find any $...
1
vote
3answers
58 views

How do I calculate the gradient of a discrete function?

In the continuous case, I have $$\lim_{x\to x_0} \frac{f(x) - f(x_0)}{x - x_0} = \lim_{h\to 0} \frac{f(x_0 +h) - f(x_0)}{h}$$ But what is the gradient of the function $f: \mathbb{N} \rightarrow \...
0
votes
0answers
59 views

how to generate parity check matrix for a non-systematic generator matrix?

Introduction: Suppose $C$ is an $\left [ n,k \right ]$ code. Let $I_{k}$ be the $k\times k$ identity matrix. Let $P$ be a $k\times \left (n-k \right )$ matrix. Then, $\left ( I_{k} | P\right )$ is ...
-1
votes
2answers
50 views

Prove that $\{(a, a), (b, b), (c, c), (a, b), (b, a), (c, a), (a, c)\}$ is reflexive and symmetric but not transitive.

Question: Let $A=\{a, b, c\}$ and let $R=\{(a, a), (b, b), (c, c), (a, b), (b, a), (c, a), (a, c)\}$. Prove that $R$ is reflexive and symmetric but not transitive. I checked that the relation $R$ is ...
0
votes
0answers
29 views

If $f(n) = \Theta(n^{\log_b{a}}\lg^k{n})$ where $k \ge 0$ , then the master recurrence has solution $T(n) = \Theta(n^{\log_b{a}}\lg^{k+1}n) $.

I'm working through problems to the book "introduction to algorithms". I'm going through the section on the master recurrence and have been running into some roadblocks. I found a solution to the ...
5
votes
3answers
217 views

Extremly simple combinatorics - divide to groups

We have a group of $10$ men and $4$ women, we want to divide this group into two groups of $7$ such that each of those groups has at least $1$ woman. What I did: I actually solved this in two ...
2
votes
1answer
64 views

(i) Show that the drawings in Fig. $1.4$ represent the same graph. (ii) Find the group of automorphisms of the graph in Fig. $1.4$.

From A Course in Combinatorics by van Lint, Wilson: Problem $1A$: (i) Show that the drawings in Fig. $1.4$ represent the same graph (or isomorphic graphs). (ii) Find the group of automorphisms of ...
2
votes
1answer
17 views

Closed form expression for $n_j$ defined by $n_j=\lceil n_{j−1}/b\rceil$ clarification

I came across this answer to this question: Closed form expression for $n_j$ defined by $n_j=\lceil n_{j-1}/b \rceil$ I was hoping someone could clarify the following step: $q−1 \leqslant \dfrac{...
2
votes
2answers
67 views

Example of a relation on $X$?

I can understand "relation $R$ in $X$" through the following example in the book, but I haven't got a clue of what "relation on $X$" looks like. Can you give an example of of a relation on $X$? "...
2
votes
1answer
40 views

Find the domain and image of the relation $R=\{(a, b), (c, b), (a, b)\}$

Let $A={a, b, c}$, and let $R=\{(a, b), (c, b), (a, b)\}$. Find the domain of $R$ and the image of $R$. This would be very elementary, but I want to get my answer checked. Let $R$ be a relation ...
3
votes
6answers
702 views

Example of a relation that is symmetric and transitive, but not reflexive

Can you give an example of a relation that is symmetric and transitive, but not reflexive? By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$. $R$ ...
2
votes
6answers
121 views

Prove $(1+2+…+k)^2 = 1^3 + … + k^3$ using induction [duplicate]

I need to prove that $$(1+2+{...}+k)^2 = 1^3 + {...} + k^3$$ using induction. So the base case holds for $0$ because $0 = 0$ (and also for $1$: $1^2 = 1^3 = 1$) I can't prove it for $k+1$ no matter ...
4
votes
1answer
102 views

Number of ways to color n objects with 4 colors if all colors must be used at least once

I have seen, and solved the following problem: How many ways to color n objects with 3 colors $\{A, B, C\}$, if all colors must be used at least once. $\require{enclose}$ The answer is as follows: $$...
0
votes
0answers
36 views

Hall's theorem proof

Could you tell me the proof using augmenting paths of Hall's theorem.(In a bipartite graph, the vertices of the smaller set can be paired one-to-one with the vertices of the other set, if and only if ...
0
votes
0answers
59 views

Two's complement involving binary numbers [Single-precision floating point number]

Given the following bit pattern: 0010 0100 1001 0010 0100 1001 0010 0100 What decimal number does it represent, assuming it is a single-precision floating point number?
3
votes
3answers
45 views

$n$ distinguishable items into $b$ distinguishable bins (there's more to elaborate…)

I've been thinking about this problem which I think is interesting, but can't solve it. There are $n$ distinguishable items, and $b$ distinguishable bins. Each bin has to include at least one item. ...
15
votes
5answers
261 views

How to prove that $\frac{(12!)!}{12!^{11!}}$ is integer?

So far I have used that a combination is an integer so $\frac{n!}{m!(n-m)!}$ is integer. Now let $n=mb$ so $\frac{mb!}{m!(mb-m)!}$. What is left is to prove that $\frac{(mb)!}{m!^b}$ is integer so ...
11
votes
1answer
180 views

Curious combinatorial summation

Let $\gamma$ denote a grid walk from the upper left corner $(1,k)$ to the lower right corner $(\ell,1)$ of the $k\times\ell$ rectangle $\{1,..,k\}\times\{1,..,\ell\}$. There are $\binom{k+\ell-2}{k-1}...
1
vote
2answers
90 views

Number of ways to color n objects with 3 colors if colors must be used once

I am aware this combinatoric problem (which I got from Discrete Mathematics Elementary and Beyond) has been answered on here before, but from what I can tell the solution I have come up with is ...
6
votes
5answers
552 views

Example of a relation that is reflexive but not symmetric

By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$, and $R$ is symmetric if and only if $x\,R\,y\implies y\,R\,x$. I think $x\,R\,x$ can also be ...
3
votes
2answers
684 views

Why is {1, 2, 3} an equivalence relation?

"The equality relation (=) on a set of numbers such as {1, 2, 3} is an equivalence relation." I know the equality relation = is an equivalence relation in the set of real numbers. Because it can ...
4
votes
1answer
57 views

Maximum number of edges in a planar graph without $3$- or $4$-cycles

What is the largest possible number of edges in a planar graph without $3$- or $4$-cycles? I've been unsuccessfully trying to solve this problem from my book. I know that every planar graph without $...
0
votes
1answer
36 views

Are axiom schema of specification and axiom of specification the same terminology?

I sometimes see books just having "axiom of specification" rather than lengthy "axiom schema of specification". Are these two the same thing?
1
vote
1answer
24 views

How is the second equeation in red cricle is derived from the first equation?

I am wondering how the equation in red circle derived from the first equation. I am sorry if I have place tags in the wrong place.
4
votes
1answer
50 views

Existence of Solutions to a $2-$Equation System of Congruences [duplicate]

Do there exist $a, b> 1$, such that $$ a^4 \equiv 1 \pmod{b^2}$$ and $$ b^4 \equiv 1 \pmod{a^2}.$$
6
votes
2answers
95 views

In how many ways can $7$ people be chosen out of $12$ people so that $2$ given people can never be selected together?

Is it right to take the combination of $7$ out of $12$ and subtract the combination of $5$ out of $10$ so i take out the ways that both of them are chosen? So it will be $792-252=540$ I just find ...
1
vote
2answers
45 views

If $n$ is a factor of $m$, prove that $x^n-a^n$ is a factor of $x^m-a^m$

I don't know how to prove this: If $n$ is a factor of $m$, prove that $x^n-a^n$ is a factor of $x^m-a^m$ ($n$,$m$ are positive integers). Help please.
1
vote
1answer
58 views

Linear Non Homogeneous recurrence relation

Find the explicit formula for given recurrence relation: $$a_{n}-7a_{n-1}+10a_{n-2}=2n^{2}+2$$ With the initial conditions $a_0=0,a_1=1$. I just want to know whether the particular solution will be ...
8
votes
1answer
77 views

How many rectangles are there on an $8 \times 8$ checkerboard?

How many rectangles are there on an $8 \times 8$ checkerboard? \begin{array}{|r|r|r|r|r|r|r|r|} \hline & & & & & & & \\ \hline & & & & &...
0
votes
0answers
22 views

Impulse Response from diffrence equation (and find the output when the input is given)

I'm a student in electronics, and in a few weeks, i have an exam on digital signal processing. The book isn't clear, and the lessons weren't clear either. I have this simple difference equation. I ...
1
vote
1answer
61 views

Puzzle: What is the algorithm for finding the kangaroo

There is a kangaroo that placed somewhere on $L$ upon the axis of the natural numbers. At some point of the time, The bell is ringing and the game starts: Each round the kangaroo jumps $K$ steps ...
1
vote
1answer
46 views

Find expected value from given PDF (CDF)

The probability distribution function (or Cumulative Distributions Function) of a discrete random variable $X$ is given by $$\begin{equation} F_X(x) = \begin{cases} 0, & \text{for $x<-2.5$...
1
vote
2answers
68 views

Leaping frog algorithm

I need your help with a riddle, I need to find the best algorithm to catch a frog, The frog is on the Natural numbers, it begins at point L, each time it goes K Leaps right (means if it was at point X,...
4
votes
3answers
108 views

What Does “Same Algebraic Structure” Mean?

What does same algebraic structure mean in group theory and when would two groups have the same algebraic structure? What properties should be checked? That would be great if you could explain it ...
1
vote
1answer
66 views

$G’$ be the graph constructed by squaring the weights of edges in $G$.

Let $G$ be a weighted graph with edge weights greater than one and $G’$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T’$ be the minimum spanning trees of $G$ and $G’$,...
1
vote
1answer
156 views

Number of distinct cycle in complete undirected graph of length $4$?

Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$ My attempt : ...
1
vote
5answers
55 views

Exponents and mod (Euler's theorem)

I know how to compute $7^{402} \pmod{10}$ using Euler's theorem since $7$ and $10$ are relatively prime. But is there an easy way without using a calculator to compute $12^{720} \pmod{10}$. I don't ...
0
votes
2answers
41 views

Double sum of products of integers up to $n$

Suppose that $S$ is defined by $$ S(n) = \sum_{i=0}^{n} \sum_{j=0}^{i} ij. $$ I'm confused as to how $S(3) = 25$ from this summation. Can anyone expand on it as to how to get the answer?
8
votes
4answers
196 views

Generating functions - deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$

I would like some help with deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ using generating functions. I have managed to do this for $1^2 + 2^2 + 3^2 +\cdots$ by putting $$f_0(x) = \frac{1}{...
3
votes
3answers
145 views

How many ways to arrange 15 people around 3 circular tables seating 5 people each

I've seen questions where it will have you arrange $N$ people at $2$ tables with $N\over 2$ people sitting at them. The answer is usually $$\binom{N} {\frac{N}{2}} \cdot \left(\frac{N}{2} - 1\right)! ...
0
votes
0answers
14 views

What is the size of Quotient in integer division with remainder?

Suppose $a=(a_{k-1},\dots,a_1,a_0)_Z$ and $b=(b_{l-1},\dots,b_1,b_0)_Z$ then $ab=m=(m_{k+l-1},\dots,m_1,m_0)_Z$ so $m$ is a $(k+l)$-digit number in the base $Z$. Let $b_{l-1}>0$ and $a=bq+r$ where ...
1
vote
2answers
94 views

How to simplify a sum of exponential equation?

Suppose I have three constants $a, b, c\in R$. I have a formulation as $f=e^{ab}+e^{ac}$. Can I have some result like $f'=e^{a(b+c)}$. I know $f'$ does not hold. But I just want to combine the two ...
3
votes
0answers
140 views

Random Variable: Ordered List of ints.

You are given an ordered list of integers : 1, 2, ...100. You then randomly permute (reorder) the integers. a.) Define a random variable that indicates whether or not a pair of integers in the list ...
-6
votes
1answer
47 views

Cardinality of two power sets Question [closed]

Problem 5 (2 pts) Given two finite sets A and B with the cardinalities A= n and B = m. (a) What is the cardinality of the powerset P(A x B)? (b) How many functions is there from A to B?
2
votes
2answers
54 views

Proof containing pairwise disjoint sets

I came across the following question while studying. Let $A,B,C,D$ be pairwise disjoint sets. Prove that if $|A| = |B|$ and $|C| = |D|$ then $|A \cup C| = |B \cup D|$. I thought of the fact that ...
0
votes
0answers
37 views

Congruence for an alternate sum of powers of the odd multiples of a prime

Let $p$ be an odd prime, and $m$ a positive integer, $$S(m,p)=\underset{0\leq k\leq p^{m+1}-1}{\underset{2 k+1\equiv 0 \bmod p}{\Sigma }}(-1)^k (2 k+1)^{m} $$ $S(m,p)$ is an alternate sum of the $m$...
0
votes
3answers
68 views

Equivalence relation and Distinct equivalence classes

Given the set $S = \{x-y \sqrt5: x, y$ are rational numbers and $x-y \sqrt5 \neq 0\}$. Assume the relation $T$ is de fined on the set $S$ by $a T b$ if $a/b$ is a rational number. Question has two ...
-1
votes
1answer
90 views

Number of non-negative integers solutions of $x_1 + x_2 + x_3 + x_4 + x_5 = 10$ when $x_1 = x_2$ and when $x_1 > x_2$

$X_1 + X_2 + X_3 + X_4 + X_5 = 10$. (i) How many non-negative integer solutions are there? this is the easy part (ii) How many non-negative integer solutions are there such that $X_1 = X_2$? Do ...
1
vote
1answer
98 views

Finding distinct equivalence classes

Q: Given the set $S = \{x - y\sqrt 5 : \text{x, y are rational numbers and }x - y \sqrt5 \neq 0 \}$. Assume the relation defined on the set $S$ by $a\ T\ b$ if $a/b$ is a rational number. Find the ...