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

There are $101$ positive integers that sum to $300$. Can we find a subset of these integers that sums to $100$?

We are given a set of $101$ positive integers that sum to $300$. Since summation of $101$ distinct numbers cannot be $300$, repetition among the $101$ positive integers exists. Can we choose a group ...
0
votes
1answer
7 views

How to eliminate bi conditionals?

p <--> q can be written as (p → q) ∧ (q → p) (~p V q) Λ (~q V p) After this I am confused. If I distribute Λ over V, I get (~p V q Λ ~q) V (~p V q Λ p) which becomes (~p V q Λ ~q ) V (~p V q ...
0
votes
0answers
20 views

How to find unknown equaivalent bases of a two given numbers?

How do I find the value of equivalent bases for the following? (√16)? = (5)? (√6)? = (25)?
0
votes
1answer
33 views

Is this the correct way to translate this phrase into symbols?

The domain of g is the set of all real numbers $x$ such that $x$ is not equal to $-3$. $$g(x)=\{x:\mathbb R|x\ne -3\}$$
-2
votes
0answers
24 views

Counting Theory Question - Houses [on hold]

If there are 50 houses in a single street (not a circle) and 2 families. How many ways can the families be housed. Considering the following: Family 1 must be within the first 10 houses. Family 2 ...
1
vote
0answers
30 views

Optimal choice for the values of money units

I just thought about how to find the optimal values for money units, given that you want your currency to come in $n$ different values (e.g. Euros come in 7 values for bills and 8 values for coins, so ...
2
votes
4answers
32 views

Disprove this number that exists in the integers.

$\exists n\in \mathbb{Z}, n^{2}<n$ I've started to prove the contradiction is true: $\forall n\in \mathbb{Z}, n^{2}\geq n$ But not sure how to do this, unless I need to show what (n)(n) = (m), m ...
1
vote
3answers
16 views

Prove this intersection subset question.

$(A\cap B\subseteq C) \wedge ({A}'\cap B\subseteq C)\Leftrightarrow B\subseteq C$ "A intersection B is a subset of C, and compliment A intersection B is a subset of C if and only if B is a subset of ...
1
vote
0answers
55 views

If two parallel lines meet at infinity, then what is their angle? [duplicate]

Since lines that meet at some point have an angle. And if parallel lines meet at infinity, then that what is the angle of two parallel lines that meet at infinity?
2
votes
2answers
20 views

Deck of cards probability with exclusion

What is the probability that a hand of five cards has exactly one club or exactly one heart So my logic was to select all possibilities with one club + all possibilities with one heart - ...
4
votes
4answers
78 views

If a group consists of five girls and five boys, what is the probability that all girls will end up on the same team?

$10$ kids are grouped into an A team with $5$ kids and a B team with five kids. If the group consists of five girls and five boys, what is the probability that all girls will end up on the same ...
1
vote
3answers
38 views

How many ways to line up a family?

A family with two parents, two daughters, and two sons line up for a photograph. How many ways are there for the family to line up so that the mother is next to at least one of her two daughters. ...
0
votes
1answer
25 views

Proof of coin and bag problem

There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively ...
1
vote
0answers
41 views

When does the dual of $s =s$?

When does $s^*=s$? $s^*$ represents the dual of $s$, where $s$ is a compound proposition involving only $T, F, \wedge, \vee, \neg $, and $s^*$ is obtained by interchanging $T$ for $F$, $F$ for $T$, ...
0
votes
1answer
31 views

Finding a generating function from an expression

Series representations: $$ \frac{1}{2(1-x)^3}+\frac{1}{4(1-x)^2}+\frac{1}{8(1-x)}+\frac{1}{8(1+x)}=\sum_{n=0}^\infty x^n\left(7+(-1)^n+8n+2n^2\right). $$ I'm trying to figure out to to turn this ...
2
votes
1answer
34 views

Set builder notation with $\land$?

Is it possible to rewrite set builder notation with conjunction $\land$? For example, $$y\in f(A)=\{f(x) \mid x\in A\} \\ ​​\iff \exists\,y, y=f(x)\land x\in A$$
1
vote
1answer
16 views

Calculate the number of paths found on the basis of probabilities

Let G=<V,E> - weighted directed graph $w(e_{ij})$ - transition probability from node $v_i$ to node $v_j$ ($w \in[0;1]$) So my first question is: how ...
0
votes
0answers
14 views

Lagrange interpolation, constant term of polynomial

I have a question about how to use the lagrange interpolation, $2x^3+8x^2+4$ The question is: What is the constant term of the $f \in Z_{13}[x]$ polynomial with degree at most 3, if f(1)=2, f(2)=3, ...
0
votes
3answers
21 views

Writing the truth value of the following question with justification.

Let $F(x,y)$ denote the statement $x+y = 0$, where the domain of discourse for both the variables is $\mathbb{R}$. Write the truth values of the following with justification. $\exists\, y: \forall ...
1
vote
1answer
45 views

Prove that if $xy=yz$ then $ \exists u,v \in A^*$ and $\exists p \in\mathbb N$ such that $x=uv$, $z=vu$ and $y=(uv)^pu$

Prove that if $xy=yz$ then $ \exists u,v \in A^*$ and $\exists p \in \mathbb{N} $ such that $x=uv$, $z=vu$ and $y=(uv)^pu$. $A^*$ is the set of all words that can be formed over the alphabet $A$. By ...
1
vote
1answer
24 views

Chromatic number of Erdos-Renyi random graphs $G(n,m)$

In Erdos-Renyi random graphs $G(n,m)$, set $n=4$ and $m=5$. The question is as follows: What is the probability for to having Chromatic number exactly 2 in the case of $G(4,5)$; in other words what ...
-3
votes
0answers
32 views

Connectivety of the Erdős–Rényi random graph [on hold]

Let G be a graph in G(n, p) (Erdős–Rényi model) I want to prove that that P( G(n, p) where p ≥ ( lnn/10n) and number of tree components on 11 vertices = 0 ) converges to 1 and lnn/n is a ...
1
vote
2answers
28 views

Quantifiers and Predicates in Discrete Mathematics

I was doing midterm review and I came across these formulas $$\forall x \big( P(x) \to Q (x))$$ and $$\forall x P (x) \to \forall x Q (x)$$ I wanted to know what the difference was in terms of $x$ ...
0
votes
2answers
34 views

How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies? [on hold]

A cookie store sells 6 varieties of cookies. It has a large supply of each kind. How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies? For my answer, I put $6 \cdot ...
0
votes
1answer
30 views

Find the Sequence of a Generating Function

I am given generating function $f(x)=x^m(1-x)^m$ where $m\in\mathbb{N^*}$ and I would like to find it's sequence. So my steps on that problem so far are ...
0
votes
3answers
21 views

Help with logical equivalences and proving tautology

I've been wracking my brain trying to figure this out, but I don't know what to do after a certain point. I'm trying to prove whether or not this is a tautology: $$ [(p\wedge r)\wedge (p\rightarrow ...
0
votes
3answers
19 views

General and particular solution from recurrence equation

I need to find the General Solution of $S_n = 3S_{n-1}-10$ for n = 1,2,3,4.... then I need to find the particular solution where $S_0 = 15$, then check the particular solution with the original ...
-2
votes
0answers
28 views

Finding recurrence relations in terms of n

The runtime of orange is log (n) and the algorithm is as follow ...
0
votes
1answer
27 views

Find the sequence

I am given generating function $\ f(x)=(1-x)^{1/2} $ and I want to find it's sequence. Is there any method that I can use to solve that kind of problem?
3
votes
1answer
48 views

Pigeonhole problem - Can solve it but can't model how it works…

So we have the below pigeonhole problem from an example quiz and I understand how to solve the problem, but I can't really model how it is working in my head. Can anyone explain it? There are 50 ...
3
votes
0answers
15 views

Maximum value of the smallest number of operations to obtain configuration from original configuration

Let $n$ be a positive integer. There are $n(n+1)/2$ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing $n$ marks. Initially, each ...
1
vote
1answer
31 views

Is proving “If $C⊆D⊆Y$, then $f^{-1}(C) ⊆ f^{-1}(D)$” done correctly?

Definition 9 Let $f: X\rightarrow Y$ be a function, and let $A$ and $B$ be subsets of X and Y, respectively. (a) The image of $A$ under $f$, which we denote $f(A)$, is the set of all images ...
1
vote
1answer
31 views

Find total number of ways to disconnect the following graph

Find total number of ways to disconnect the following graph: $4$ $5$ $6$ $8$ My attempt: I've done manually to find possible disconnected sets of given graph. I guess it is should be ...
0
votes
0answers
24 views

Temporal logic: how to prove or disprove $FG \phi \implies GF \phi$? [on hold]

$F$ for eventually (in the future) $G$ for globally (always)
-3
votes
2answers
33 views

What is my chance of winning a lottery where 2000 will win out of 100000 participants? [on hold]

This question is related to the H1B lottery where the total number of applicants is around 235000 and the number of applications that will be selected is 85000. So I want to know what my chances ...
1
vote
1answer
14 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
1
vote
0answers
24 views

What are “first principles”

I am watching a discrete math video where the professor says that using the Pigeonhole principle is easier than using the first principles. What exactly are the first principles and what in general ...
0
votes
1answer
24 views

How many elements are there in a total ordering T of a set A with |A| = n?

How many elements are there in a total ordering T of a set A with |A| = n? I have no clue on how to do this problem. If someone could let me know how to start the problem, it would be much ...
1
vote
1answer
30 views

How many rounds are needed for a k-elimination tournament? [on hold]

Supposing each game has exactly two players and there are no ties and no player can play more than once in the same round and the pairings of any given round can depend on the results of earlier ...
1
vote
1answer
40 views

Is proving $(f: X→ Y)\land f(\varnothing)\neq\varnothing$ is a contradiction correct in the proof of this statement?

Definition 4 The connective $\rightarrow$ is called the conditional and may be placed between any two statement $p$ and $q$ to form the compound statement $p→q$ (read: "if $p$, then $q$". By ...
1
vote
2answers
22 views

Discrete Dynamical System - determine what the model predicts will be the long-term distibution

If I have the following matrix: $$X_{n+1}\begin{pmatrix}1&0\\ 0&0.2\end{pmatrix}X_n$$ and if I also have the following initial state vector: $$X_0=\begin{pmatrix}5\\ 7\end{pmatrix}$$ What ...
1
vote
3answers
66 views

What's the negation of $ \ f: X\rightarrow Y\Rightarrow f(Ø)=Ø$?

Definition 8. Let X and Y be sets. A function from X to Y is a triple (f, X, Y), where f is a relation from X to Y satisfying (a) Dom(f) = X. (b) If (x, y)$\in f$ and (x, z) $\in f$, then y=z. ...
1
vote
3answers
42 views

Seating arrangements of 7 boys and 5 girls in a row.

In how many ways can these boys and girls be arranged in a row if between two particular boys A and B there are no boys but exactly 3 girls?
0
votes
1answer
26 views

Particular Solution of Recurrence Equation

Given: $S_{n+2} = 13S_{n+1} + 48S_n$ for $\forall n \in N$ I've found the General Solution which is $S_n = A16^n - B3^n$ I don't quite understand how to find the particular solution where $S_0 = 1$ ...
3
votes
4answers
70 views

Question about conditional statements as applied to math?

I was being bothered by the fact that $p \implies q$ is defined when $p$ is false, so I thought I would try an example in math terms to help me understand it; but I got a stuck: Let's define $p: x ...
2
votes
1answer
57 views

Given $f: X → Y$ and $g: X → Y$ are two functions. How to prove that if $f⊆g ⇒ f=g$?

Definition $(x_1, x_2, ..., x_n) = (y_1, y_2, ..., y_n) \Leftrightarrow x_1 = y_1, x_2=y_2, ..., x_n = y_n$ Definition $A_1 ×A_2×A_3 \cdots ×A_n =$ {$(a_1, a_2, ...a_n)| a_1 \in A_1, a_2 \in ...
2
votes
1answer
39 views

Is there a simple solution to these 2 equations without trying all possible values?

Now I have two equations and the computation is in a finite field GF(p), where p is a prime. $x, y$ are unknown, and $a, b$ are known. ($0<y<p-1$, and $0<ax<p-1.$) $\begin{cases} x^y ...
0
votes
0answers
34 views

Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. [duplicate]

Let $G = (V, E)$ be a finite graph. (A) Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. (B) Assume that $|V | = |E| + 1$. Find an example that $G$ is not a tree.
0
votes
0answers
23 views

Partial order set question: select n elements

Here is the problem: Given a set $S = \{s_1, s_2, s_3, ...\}$, where each $s_i = (v_{i1}, v_{i2})$, we want to establish an ordering on set $S$ based on $(v_{i1}, v_{i2})$. After this, we want to ...
2
votes
3answers
36 views

Let X be the unit interval [0, 1]. Find a function $f: X \rightarrow X$ that is a symmetric relation on X.

"R is symmetric if and only if xRy $\Rightarrow$ yRx" Question: Let X be the unit interval [0, 1]. Find a function $f: X \rightarrow X$ that is a symmetric relation on X. Source: Set Theory, ...