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
22 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
83 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
28 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
54 views

When does the dual of $s =s$?

Why I believe this is not a duplicate: The linked question might be the same, but the accepted answer is only a partial answer, because it gives no reason as to why those are the only solutions. Since ...
0
votes
1answer
34 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
38 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
17 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
15 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
24 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
47 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
26 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
37 views

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

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

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

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
31 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
20 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
52 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 ...
5
votes
1answer
61 views
+100

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
33 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$? [closed]

$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? [closed]

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
25 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
34 views

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

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
42 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
23 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
67 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
43 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
71 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
59 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
41 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, ...
1
vote
1answer
59 views

Where in the proof of this theorem shows “If (x, y)$\in f$ and (x, z) $\in f$, then y=z.”?

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. ...
3
votes
2answers
62 views

How many colours do we at least need so that we can ensure all 250 countries have different flags.

One for FN standardized flag consists of three horizontal rectangular fields. If we assume that the middle field not are allowed to have the same colour as the top or bottom field, how many colours do ...
2
votes
3answers
37 views

Compute the Euler function $\phi(n)$ for $n = 360$ as well as the number of divisors $d(n)$.

Compute the Euler function $\phi(n)$ for $n = 360 $ as well as the number of divisors $d(n)$. Is this correct? $360 = 2^3\cdot 3^2\cdot 5$ thus $\phi(n) = 2^2\cdot 2\cdot 3\cdot 4 = 96$. $d(n) = 4 ...
0
votes
2answers
40 views

12 books shelf and bag.

I got two varieties for the same question: Ways that four books out of a bag of 12 books can be placed on a shelf. Ways to choose 4 books out of 12 arranged on a shelf and put them in a bag. ...
0
votes
1answer
27 views

Transivity / Binary relation? [closed]

Discuss the Transitivity of Binary Relations $\mathcal{S} $ $a$ on $\Bbb R $ defined by $a (x, y)$ $\in \Bbb R^2 $--> $x \leq ay$ ( for some a $ \in \Bbb R$ ) I have this assignment about ...
2
votes
0answers
76 views

Expectation or Integration of the normal cdf

Can any one help me how to solve this pronbelm? I have a random variable $W$, i.e., $$W=\Phi(X)^k\Phi(-X)^m=P(Z\le X)^kP(Z \ge X)^m,$$ $X$ is Normal($\mu$,1), $Z \text{ is Normal(0,1)}$, and $k$ ...
0
votes
1answer
44 views

What is the negation of a logical expression? [duplicate]

If I have for example the following: $p$ is $ x > 4$ $\lnot p$ is $x < 4$ ?
0
votes
0answers
16 views

Stuck: To show that the divide and conquer relation represent Merge Sort

I've just started with recurrence relations. I know that the divide and conquer relation in merge sort is given by, $M(n) = 2M(n/2) + n$ Question: A divide and conquer relation is given $$a_n = ...
1
vote
1answer
13 views

How Many Marriages in a Bipartite Graphs?

Given two disjoint sets, say $M$ and $W$, both of size $n$, I want to compute how many possibilities of marriage exist. For example, when $n=1$, there are two marriages only: either $m_1-w_1$ or ...