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
votes
1answer
40 views

Find all $a$, so $q$ prime number which ,$q\times n= aaaaaaa$ [duplicate]

I need your helping to find all the $a$ numbers,which follow the next rules: there is prime number $ 2\lt n\in \mathbb N$ and $ 5\neq q\in \mathbb N$ so that the digits of $n\times q$ are only $a$. ...
1
vote
2answers
61 views

This sigma to binom?

Can you please show me how to get from the left side to the right side? $$\sum\limits_{k=0}^{20}\binom{50}{k}\binom{50}{20-k} = \binom{100}{20}$$
1
vote
2answers
79 views

Show that there is precisely one cyclic code C of length 4 and dimension 2. Write down all the codewords in C.

I have shown there is one cyclic code, put not sure how to calculate the codewords in C. I think that the generator matrix is \begin{bmatrix}1&0&1&0\\0&1&0&1\end{bmatrix} but ...
1
vote
1answer
23 views

Translating Mathematical (Universal/Existential Quantifier) Statements into English?

Can anyone confirm if I have these correct? Or if not, where I am going wrong? Translate these statements into English, where $K(x)$ is '$x$ is a Kangaroo' and $H(x)$ is '$x$ hops' and the domain ...
0
votes
0answers
31 views

Show that there is precisely one cyclic code C of length 4 and dimension 2.

So far I have calculated the unique factorization of $x^4-1$ to be $(x-1)(x+1)(x^2+1)$ but am unsure of where to go next. Would the generator matrix then be of the form ...
2
votes
3answers
43 views

In how many ways can $12$ different balls go into $3$ different boxes so that in every box there are $4$ balls? [closed]

I need help with this question: In how many ways can $12$ different balls go into $3$ different boxes so that in every box there are $4$ balls? The answer should be $34650$. Thank you.
1
vote
4answers
40 views

Does a sequence require a unique value for a particular natural number?

In a question, I was asked to prove the existence of a sequence that converges to $\sup S$, where every element is an element in a set S. The solution used defined ($A_n$) for $n$ natural numbers as ...
0
votes
2answers
65 views

Prove that there is prime number and natural so $n\times q$ digits are $1$.

I need your helping to prove that there is a prime number $ 2\lt n\in \mathbb N$ and $ 5\neq q\in \mathbb N$ so that the digits of $n\times q$ are only $1$. for example:if $n=3$ then $3\times 37=111$ ...
2
votes
1answer
24 views

Big O Notation logarithms

I'm having trouble with these two Big O notation proofs (b) $(n + \log_2 n)^5 = \Theta(n^5).$ (b) $(\log_2 n)^5 = O(\log_2 n^5).$ For the first one, I'm having trouble finding a $c$ value ...
6
votes
2answers
93 views

Number of solutions $(x_1)(x_2)(x_3)(x_4) = 2016$

Having some trouble wrapping my head around this one: find the number of solutions to the equation $(x_1)(x_2)(x_3)(x_4) = 2016$, where $(x_i)$s are integers that are not necessarily positive. ...
0
votes
3answers
34 views

How many binary words of length $9$ are there that contain 4 $0$s and 5 $1$s?

I'm studying for a Discrete Mathematics II exam, and I came across this example in the textbook of the course. The writer proceeds to solve as $\dfrac{9!}{4!5!}=126$ and provides no explanation. ...
0
votes
1answer
17 views

Determine the parity and the inverse for each of the following permutation of {1, 2, . . . , 9}:

So i was given this question. Determine the parity and the inverse for each of the following permutation of {1, 2, . . . , 9}: (a) (987654321) (b) (135792468) I don't understand how to go about ...
6
votes
4answers
104 views

# of partitions of $n$ into at most $r$ positive integers $=$ # of partitions of $n + r$ into exactly $r$ positive integers?

How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?
1
vote
1answer
21 views

Count the ways to choose distinct subsets $A_0, A_1, . . . , A_n$ of ${1, 2, . . . , n}$ such that $A_0 ⊂ A_1 ⊂ . . . ⊂ A_n$

I was given this question. Count the ways to choose distinct subsets $A_0, A_1, . . . , A_n$ of ${1, 2, . . . , n}$ such that $A_0 ⊂ A_1 ⊂ . . . ⊂ A_n$ I followed a different example to solve this ...
9
votes
1answer
65 views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. ...
1
vote
1answer
24 views

Calculate the number of equivalence relations $S$ that satisfies $R \subseteq S$

Let $A=\{1,2,3,4,5,6,7,8\}$ and let $R=\{(1,2),(5,4),(4,5),(6,2),(4,4),(6,5),(7,8)\}$ be a relation on A. What it the number of equivalence relations $S$ that satisfies $R \subseteq S$ I know what ...
4
votes
2answers
61 views

How many different strings can be made from letters in CHICAGOLAND, subject to constraints? [closed]

How many different strings can be made from the letters in CHICAGOLAND, using all letters, and such that no two vowels are adjacent to each other?
3
votes
1answer
58 views

Good set with $n$ elements must have element $\ge {2\over n}\binom{n}{n\over2}$?

Let $n$ be even. A set $\{a_1, \dots, a_n\}$ consisting of positive integer s is good if for every two different disjoint subsets $S$, $T \subseteq [n]$ of the same cardinality we have$$\sum_{i \in S} ...
1
vote
1answer
25 views

Proving in planar graph

So I have a connected triangle-free planar graph - let's name it G. So I have proven that there exists a vertex V $$deg(V)\leq 3$$ I proved that using $$m\leq 3n-6$$ where $$n=|V(G)| , m=E(G)$$ along ...
1
vote
0answers
39 views

relations and equivalence classes

$S$ is the set of all equivalence relations on set $A = \{1,2,3,4,5,6,7,8,9\}$ in which one of the equivalence classes is $\{1,3,5,7,9\}$. What is the size of $S$? I don't even know how to start... ...
0
votes
1answer
32 views

DNF simplification

I am currently learning about propositions and logical equivalences in a mathematics course I'm taking at university. I'm having trouble understanding how to simplify DNF Formulas. I was given a truth ...
0
votes
2answers
48 views

Minimum number of moves to even out a row of brick piles

Consider a row of $15$ piles of bricks. There is a total of 75 bricks, all identical. The number of bricks per pile varies across the piles. For instance, the distribution of bricks per pile might be ...
0
votes
2answers
64 views

How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 12$ with restrictions on $x_1,x_2,x_3,x_4$

So I was given this question. How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 12$ with $x_i > 0$ for each $i \in \{1, 2, 3, 4\}$? How many solutions with $x_1 > ...
0
votes
0answers
109 views

Is the establishment of the validity of this argument correct?

I am trying to show that the following argument is valid. There is an email that is sent but it is not saved in the inbox. All emails are saved in the inbox or the inbox is full. If the inbox is ...
-1
votes
2answers
41 views

discrete mathematic Question that i need help with please [closed]

Determine the number of integer solutions of $x_1 + x_2 + x_3 + x_4 + x_5 = 32$ where $x_i > 3$ for $1 ≤ i ≤ 5$.
2
votes
2answers
40 views

Using Set Builder Notation on a set that jumps in intervals?

I'm new to the world of Discrete Mathematics. I have been reviewing a little on Set Builder Notation and have looked over the following site thoroughly: ...
1
vote
1answer
58 views

Uses of Ramsey Theory in Astronomy?

In the last paragraph of a Scientific American article of July 1990 that can be found here http://www.math.ucsd.edu/~ronspubs/90_06_ramsey_theory.pdf Graham and Spencer write "Today we can easily ...
0
votes
1answer
30 views

Propositional Equivalence

Are the following two propositions equivalent? p IMPLIES (q IMPLIES r) p IMPLIES (q AND r) From what I can tell, using the logical equivalences, this should be false, correct? p ...
0
votes
3answers
34 views

Solve $x^2+2xy-782y=0$ diophantine equation

I'm trying to solve $x^2+2xy-782y=0$ diophantine equation. With these steps: a) $(*4)$; $4x^2+8xy-3128y=0$ b) $(+/-4y^2)$; $4x^2+8xy+4y^2-3128y-(4y^2)=0$ c) Reducing; $(2x+2y)^2+(-3128y)-(4y^2) = ...
0
votes
2answers
31 views

Modular Linear Equations

I am revising for one of my Computer Science exams, and a repetitive question keeps coming up; however it's very maths based. And I suck at mathematics. Question $3)$ Consider the following two ...
2
votes
2answers
44 views

nested quantifiers (exactly one questions)

Express this statement using quantifiers, without using the uniqueness quantifier."There is exactly one student in this class who has taken exactly one mathematics class at this school" T (x, ...
0
votes
1answer
20 views

Is $[a]_R$ the same as [a]?

Source: Discrete Mathematics with Applications by Susanna Epp Is $[a]_R$ the same as [a]=a/R? Then, $x \in ([a]_R$=a/R) is the same as $x \in ([a]=a/R)$, right?
4
votes
3answers
72 views

Showing $\sum_{k = 2}^n \binom{k}{2} \binom{n}{k} = \binom{n}{2} 2^n$ without induction.

How do I prove the identity$$\sum_{k = 2}^n \binom{k}{2} \binom{n}{k} = \binom{n}{2} 2^{n-2}$$combinatorially, i.e. counting the cardinality of the same set in two different ways? I know how to do it ...
6
votes
2answers
64 views

At least $P(m, n - 1) = {{m!}\over{(m - n+1)!}}$ surjective functions from $[m]$ to $[n]$?

How do I see that there are at least$$P(m, n - 1) = {{m!}\over{(m - n+1)!}}$$surjective functions from $[m]$ to $[n]$?
1
vote
1answer
17 views

Big O $n^{1/n}$ = Big Theta(1)?

I am trying to prove if $n^{1/n}$ = Big Theta(1) Is it sufficient to say that if we let c = n, then $n^{1/n}$ <= $n*1$ And if we let c = $1/n^{1/n}$, then $1$ <= ($1/n^{1/n}$)/$n^{1/n}$ I'm ...
2
votes
0answers
13 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
0
votes
1answer
28 views

Can a finite set that is odd and a finite set that is even have the same number of subsets?

A more clear way of asking it I suppose would be. Supposing a finite set 'S' that is not empty, how would I be go about proving that the number of subsets of S if the total number of elements is odd, ...
3
votes
3answers
94 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 ...
-1
votes
3answers
43 views

Reducing this binomial expression [closed]

I need help for showing that: $$\sum\limits_{k=2}^{50} = k \cdot(k-1)\binom{50}{k}$$ is equal to: $$50\cdot 49\cdot 2^{48}$$ please help , thank you.
1
vote
3answers
89 views

Suppose $a \in \mathbb{Z}.$ Prove that $5 \mid 2^na$ implies $5 \mid a$ for any $n \in \mathbb{N}$

This question is supposed to be solved by induction, however I'm unsure of where to get my base case from exactly, because the question is asking about both $a$ and $n$. I started with my base case ...
2
votes
1answer
16 views

Help finding Cardinality of two sets, and their interactions?

I'm trying to find the cardinality of the below: $$A = \left\{ x\in \mathbb{Z}: \bigg|\frac{3x^3 + x^2 - 2x + 4}{3x + 4}\bigg| \geq (2^{50} -1 ) \right\}$$ and the set $$B = \left\{ x\in ...
0
votes
2answers
33 views

Total Number of Equivalence classes of R

I was given the following question for homework: Let P denote the set of all compound propositions involving the simple/atomic propositions p, q, and r and the logical connectives ∨, ∧, and ¬ ...
0
votes
2answers
19 views

how do I use propositional equivalence laws to simplify? [closed]

I have two statements that are supposed to simplify to the same answer: 1) (not(p or q) or not(p or not q)) 2) ((p or q) implies (not p and q)) how do these simplify using the equivalence laws of ...
0
votes
0answers
7 views

Rate of change of a variable: adding cross products

Say there is a variable, Nominal GDP growth, and it's a function of 1) growth of inflation and 2) growth of quantity of goods and services produced in the economy (i.e. growth of real GDP). The rate ...
0
votes
1answer
28 views

proving $E \leq \frac{(n-k+1) \cdot (n-k)}{2}$

I'm trying to prove something about graph theory, but I'm not sure if I'm thinking in the right direction. Let $G$ be a simple graph, that is a graph without multiple edges and loops, let $n$ be the ...
1
vote
1answer
40 views

Prove that a Rational number cubed is a Rational number

How can I prove that when a Rational number is cubed it continues to be a Rational number. First of all, I tried to find a counterexample, but I did not find any, so it must be true. I know that any ...
0
votes
0answers
70 views

Integration of the product of Hermite Polynomial and exponential function

how to proceed with these two integration.. $$\int^0_{−∞}e^{−ax2}H_{2k}(x)dx=?$$ $$\int^∞_{0}e^{−ax2}H_{2k}(x)dx=?$$ where $$H_n(x)$$ is the Hermite Polynomial (physicist's convention).
2
votes
1answer
30 views

What is the expected value of cosine of a multivariate Gaussian?

Suppose $X \sim \mathcal{N}\left(\mu, \Sigma\right)$. How do I evaluate $\operatorname{E}\left[\cos \left(t^{T}X \right) \right] $ and $\operatorname{E}\left[\sin \left(t^{T}X\right) \right] $? Does ...
0
votes
2answers
40 views

Proving in Discrete Structures Problem

Here's how it is. So I was studying some notes on Discrete Structures then I discovered this. Prove that $2^N = \binom{N}{0} + \binom{N}{1} + \binom{N}{2} + \dots + \binom{N}{N}$ Since I was new to ...
0
votes
1answer
8 views

Graph theory: Proof that if the graph G(V1V2,E1E2) is conntected then the intersection (V1V2) is not empty.

I'm attempting to prove the following with contradiction. Unfortunately i'm not sure if my deduction is flawless in this one. Given: $G_1=(V_1,E_1),\quad G_2=(V_2,E_2),\quad G=(V_1\cup V_2,E_1\cup ...