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

-5
votes
1answer
170 views

I have proved that 1 + 1 = 0 [closed]

I have proved that 1 + 1 = 0 in one of my questions where a field was given. I was wondering if it is true in every field we have 1 + 1 = 0. Also i was wondering (i know how to prove 1 + 1 = 0) can ...
-1
votes
1answer
36 views

What is transpose multiplier and forward multiplier?

For linear system X = A*s, we define the forward and transpose multiplies Af and At as follows: Af = @(s) A*s; At = @(s) A'*s; I want to know what is forward ...
0
votes
0answers
37 views

How to proceed with this simple proof?

If $$\alpha_k = \sum_l a_l \ \ g((k-l)T-l\Delta T)$$ $$s_k = \sum_l \alpha_l \ \ q((k-l)T+k\Delta T)$$ where $a_l \in \pm1$ and $g(t) = \frac {\sin(\pi t/T)}{\pi t/T}$ and $q(t) = \frac {\sin(\pi ...
-1
votes
2answers
121 views

Every field has at least two elements

I got a question saying in every field (F, +, ⋅, 0, 1), the set F has at least 2 elements. It asks if it is true prove it or if false provide a counterexample. I understand the idea of finite fields ...
5
votes
1answer
33 views

Prove that given graph consisting of vertices numbered with composite numbers is not eulerian

We have the following graph definition: $$V(G_n)=\{1\leq m\leq n : m = pq\}$$ (so vetices of $G_n$ are composite numbers) $$E(G_n)=\{\{i,j\}:i\perp j\}$$ (so vertices $i,j$ are connected if and only ...
2
votes
3answers
265 views

Discrete Math: Unions, Intersections, Complements

Are these answers correct? The union and intersection only include the elements in the universal set? $U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ (where $U$ is only a subset of the Universe) $A ...
2
votes
1answer
49 views

How many triangles can be made from $n$ points on a line and not on a line

We have a plane with $n$ points $(n\ge 34)$. $17$ points are on one line, and the rest are positioned such that no three points are on one line. How many triangles can we make from the $n$ points? ...
0
votes
1answer
51 views

Suppose A and B are disjoint, while B and C are disjoint as well.

I am currently trying to understand this example in the textbook and it's not really making any sense to me. Lets say A and B are disjoint, while B and C are disjoint as well. According to the ...
0
votes
0answers
82 views

How to predict intuitively the recurrence relations of josephus problem?

i have studied the Josephus problem from the concrete mathematics book.I have understand all related calculations discussed on that book.However i have some difficulties regarding to recurrence ...
3
votes
1answer
153 views

Induction Proof: $2$ divides $n^2 + n$ for each $n \in \mathbb{N}$

So I am looking at some induction questions and I am trying to solve them on my own but I am getting stumped and frustrated. There was a previous question question that was answered, but I changed it ...
0
votes
2answers
96 views

Finding a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in

Find a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in. $a_n=\begin {cases}A\text{____}a_{n-1}\\ B\text{____}a_{n-1}\\ C\text{____}a_{n-1}\\ ...
1
vote
1answer
30 views

How many subsets of $\{1,2…,n\}$ there are such that if $2$ exists in the set then $1$ isn't

How many subsets of $\{1,2...,n\}$ there are such that if $2$ exists in the set then $1$ isn't? I think the approach is a recursive formula: Let $b_n$ be the sequence: If $2$ is in the set then ...
2
votes
0answers
254 views

Minimal, maximal, least, and greatest element

Let B = {1, 2, 3, 6, 12, 18} and R be defined by xRy if and only if x|y. a) Determine all minimal and all maximal elements of the poset. b) Find all least and greatest elements of the poset. I am ...
2
votes
2answers
345 views

Proof by contradiction and mathematical induction

$\sum_{i=1}^n {2\over3^i}={2\over3}+{2\over9}+\dots+{2\over3^n}=1-{({1\over3})^n}$ I had this problem in class and we proved using 2 different methods: contradiction and mathematical induction. I ...
1
vote
1answer
83 views

Probability of a car having a defect in the brakes or fueling system?

Given the following probabilities, defect in brakes = 0.25 defect in transmission = 0.18 defect in fuel = 0.17 defect elsewhere = 0.40 Q. What is the probability that the defect is in the brakes ...
3
votes
3answers
35 views

I have 30 photos, which I want to sort into 2 categories. Either one can be empty. How many ways can I sort these photos, order matters?

I know the answer is $\binom{31}{1}\cdot30!$, and I understand the reasoning as organizing $30!$ ways and then $\binom{31}{1}$ places to put the delimiter. Why is it not $2^{30}\cdot30!$ That is, ...
0
votes
2answers
24 views

Let $(2x − y)^4 = gx^4 + hx^3y + ix^2y^2 + jxy^3 + ky^4$ , where $g, h, i, j, k$ are integers.

Let $(2x − y)^4 = gx^4 + hx^3y + ix^2y^2 + jxy^3 + ky^4$ , where $g, h, i, j, k$ are integers. What is $h$? = $-32$ What is $j$? = $-8$ i'm using the pascal triangle and know that i should start ...
1
vote
2answers
187 views

Permutation of 6-digit numbers without repetition

How many 6-digit numbers without repetition of digits are there such that a ) the digits are all non-zero b ) 1 and 2 do not appear consecutively in either order ? Calculated the answer as below ...
2
votes
1answer
142 views

Proving or Disproving a function that is onto itself is one to one.

I'm having some trouble formulating a proof for this following problem: A is a finite set and f a function with f : X → X. Suppose that f is onto. Now Prove or Disprove: f is one to one. ...
0
votes
2answers
40 views

Prove by math induction

$\forall n \geq 2$ $\frac{7}{9} \times \frac{26}{28} \times \ldots \times \frac{n^3 -1}{n^3 + 1} = \frac{2}{3} \times (1 + \frac{1}{n(n+1)})$ After basis step i went this far: $ ...
-1
votes
1answer
28 views

Probability question about sharing range of quantity

Suppose we have 10 Boxes, John shares into 7 of them, and Mike shares into 5 boxes. **The Question :**what is the expected number of boxes are shared between John and Mike? using equation :7*5 /100 ...
-4
votes
2answers
149 views

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5$ is $O(x^3 )$. [closed]

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5 \textrm{ is } \mathrm{O}(x^3 )$. What do i need to do here? Like step by step?
0
votes
2answers
137 views

What is the cardinality of the power set $P(A \cup B)$

Let $A = \{1, 3, 5\}$ and $B = \{3, 4, 5\}$ be sets. What is the cardinality of the power set $P(A \cup B)$? If i'm not mistaking isn't it all the possible combination of these two: $\{\}, ...
0
votes
3answers
43 views

A set S is defined recursively by

A set S is defined recursively by Basis step: $0 \in S$ Recursive step: if $a \in S$, then $a + 3 \in S$ and $a + 5 \in S$. Determine the set $S \cap \{ a \in \mathbb Z \mid 0 < a < 12 \}$. ...
5
votes
3answers
88 views

Summation of series in powers of x with certain combinations as coefficients

How can I find the sum: $$\sum_{k=0}^{n} \binom{n-k}{k}x^{k}$$ Edit: The answer to this question is: $$\frac{{(1+\sqrt{1+4x})}^{n+1}-{(1-\sqrt{1+4x})}^{n+1}}{2^{n+1}\sqrt{1+4x}}$$ I don't know how to ...
3
votes
1answer
91 views

There are 39 students in our class. We form groups of 2, with one left out. How many ways can the students be paired up?

I know that the answer is $\frac{39!}{(2!)^{19}\cdot19!}$, where each pair can be organized $2!$ ways and the pairs can be arranged in $19!$ ways. We can also extrapolate the case for $5$ students, ...
3
votes
1answer
45 views

How many ways can 8 persons, including Peter and Paul, sit in a row with Peter and Paul not sitting next to each other?

The solution I have to this problem is $8!-2\cdot7!$. I don't understand why the $7!$ is multiplied by two. My solution is that you have a total $8!$ ways to organize 8 people. Subtract all cases ...
3
votes
0answers
41 views

Multiplicative Inverse of Polynomials in Finite field

Find the multiplicative inverse of $x + 2$ in the field $\Bbb Z_5[x]/(x^2 + 2)$. I have done the following so far: \begin{align*} x^2+2 &= (x+2)(x+3) + 1\\ (x+2)(x+3) &\equiv -1 \pmod ...
1
vote
1answer
47 views

Count number of colorings of tetrahedron, where colorings are indistinguishible if one can be reached from another by rotation

I'm fairly new to group theory, and here's one problem I'm trying to solve: We're coloring nodes of tetrahedron in 3 distinct colors, and its edges in 2 distinct colors. We're treating two colorings ...
0
votes
1answer
40 views

Does proportionality include addition? ie. if A + B = C are A & B inversely proportional?

If A×B=C, then A is directly proportional to C in case that B is a constant or A and B are inversely proportional in case that C is a constant If A + B = C If C is a constant are A & B ...
16
votes
3answers
267 views

Count permutations of $\{1,2,…,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this?

Here's a problem I've solved: Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers (e.g. 1,2,3,4). So I did it kinda brute-force way - let $A_i$ be the set of permutations of $[7]$, ...
1
vote
1answer
61 views

How many bags can be made out of 4 kinds of balls

We have balls in a bin, $30$ balls of type $a$, $30$ balls of type $b$, $30$ balls of type $c$, $30$ balls of type $d$. We take out one ball per minute in random and move it to a bag. How ...
0
votes
3answers
52 views

Find a base in linear algebra

So I have this problem: Let $V_1 = \{(x_1,x_2,x_3) \in \mathbb R^3 : x_1+x_2-x_3 = 0\} $ and $V_2 = \{(x_1,x_2,x_3) \in \mathbb R^3 : x_1-2x_3 = 0\} $. Find a base in $V_1∩V_2$ and show that $V_1+V_2 ...
-1
votes
5answers
116 views

The interval in which $ab+bc+ca$ lies if $a^2+b^2+c^2=1$

What is the interval in which $$ab+bc+ca$$ lies if $$a^2+b^2+c^2=1$$.I have considered using the AM-GM inequality. But that's not working. Please provide some advice.
0
votes
1answer
39 views

About Newman and Girvan definition of Modularity of Network-Community

Can some body explain me the following statement about Community Structure in a Graph : Newman and Girvan write: „In a network in which edges fall between vertices without regard for the communities ...
3
votes
2answers
83 views

Is my argument correct to solve this textbook problem?

The problem is from M.Bona's "A Walk through Combinatorics", Ch1 Prob 13: There are infinitely many pieces of paper in a basket, and there is a positive integer written on each of them. We know ...
3
votes
3answers
242 views

How many permutations of cycle-shape $(3,2^2,1)$ are there in $S_8$?

I am not familiar with this kind of counting problem, so I googled the key words. From what I found it looks like Stirling Numbers of First Kind do the job(?). These numbers are denoted [$\frac nk$ ] ...
3
votes
2answers
2k views

Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.

Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications" Let P(n) be the number of strings not containg two containing ...
0
votes
1answer
31 views

Strong fixed points and generating function

For a permutation $\sigma\in S_n$ we say i is a strong fixed point, if $\sigma(j)<\sigma(i)$ for $1\leq j<i$ and $\sigma(j)>\sigma(i)$ for$ i<j\leq n$ i) Show a strong fixed point is a ...
1
vote
1answer
74 views

ordering items so no two adjacent ones are equal

There are $n$ numbers, $a_1, a_2, ...., a_n$, which may contain repetitions. Under what conditions can they be arranged in such an order that no two same numbers are adjacent? A necessary condition ...
1
vote
1answer
104 views

How many non decreasing sequence of length k is possible?

If we have a set like this { 1A ,2A ,2B, 3A, 3B, 3C}, how many non decreasing sequence is possible, such that number in left is less than number in right of length k? i.e, Length = 2 then the ...
2
votes
0answers
37 views

Bijective function between lists and sets

How many eight-bit strings have exactly three $1$’s? The answer is $8\choose 3$. Since we count subsets here, how can we set up a one-to-one correspondence between any $8$bit list with only three ...
0
votes
0answers
23 views

How to get samples of different paths?

Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed). Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B. I ...
0
votes
1answer
23 views

Number of subsets transversal both to a finite set and to its complement

I have a set $V$ of $n$ elements and a subset $A$ of fixed cardinality $2 \le k \le n-2$. How many subsets $Y$ are there such that $Y \cap A \neq \emptyset \wedge Y \cap A^c \neq \emptyset \wedge A ...
0
votes
0answers
48 views

Convert an equation in Laplace “s” space to Discrete “z” space using a table

I'm trying to discreteize an equation. I have the equation in laplace form, but I do not have the original differential equation. The equation is: $$\frac{\theta(s)}{V(s)} = \frac{a}{s(s+b)(s+c)}$$ ...
1
vote
2answers
268 views

Find pmf for $i=0,1,2,3,4$

I have a problem that I'm having trouble with. Here is the problem: "Five distinct numbers are randomly distributed to players numbered 1 through 5. Whenever two players compare their numbers, the ...
18
votes
2answers
966 views

Puzzle: Cracking the safe [duplicate]

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
0
votes
2answers
158 views

How many ways to distribute $n$ objects into $r$ boxes so that each box have at least $1$ (but no more than $k$) objects?

Example: How many ways are there to distribute 15 fruits to 6 people so that each person has at least 1 fruit but no more than 3? I understand how to do it when we need to make sure that at least ...
1
vote
4answers
161 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
26 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 ...