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
0answers
6 views

Convergences in probability and distribution for the number of trees in random graph $G(n,p)$

As we know the binomial random graph $G(n, p)$ is the disjoint union of trees for $p\sim o(1)$ and by the results from Erdos-Renyi's article on the evolution of random graphs; we know that the ...
0
votes
0answers
7 views

Solving Principle Component Analysis

Okay guys so i am struggling with theoretical mathematics. So i am given the Principal Component Analysis: Y = $$(X − 1x^T )G$$ where X (n × p) is the data matrix, 1 is a vector of length n ...
1
vote
1answer
14 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
0answers
6 views

Number of ways to select cookies (sets)

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*6*5^13. My logic ...
0
votes
1answer
28 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 ...
2
votes
0answers
74 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
0answers
14 views

Zero-one law in binomial random graph model $G(n,p)$

Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} ...
0
votes
3answers
15 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
18 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 ...
0
votes
1answer
18 views

Stirling number of first kind monotone for a half

Show that every $n>0$, there is some $m(n)$ such that $$s_{n,0}<s_{n,1}<\cdots < s_{n,m(n)}>s_{n,m(n)+1}>\cdots>s_{n,n},$$ where either $m(n)=m(n-1)$ or $m(n)=m(n-1)+1$ and ...
0
votes
1answer
24 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 ...
-2
votes
0answers
26 views
0
votes
1answer
26 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?
0
votes
2answers
106 views

Explicit Mapping to show that positive even integers and integers divisible by 3 have the same cardinality

So I'm really confused about what this question is asking and how to show it. I've started by trying to map out each set in my head ie. $\{\dots,-6,-3,0,3,6,\dots\} \{2,4,6,8,\dots\}$. I've done ...
0
votes
1answer
804 views

Disjunctive normal form (BOTH dnf and cnf) example help

T or ( not x and y ) or ( x and y ) In class we went over examples of how many things can be both DNF and CNF... eg. (not z) or y can be thought of as both (not z) or y .... dnf ((not z) or ...
3
votes
1answer
43 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
11 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 ...
0
votes
2answers
484 views

Proving properties of the images and inverse images of functions

Let $f : X\to Y; \;\;g : Y\to Z;\,$ and $\;g \circ f : X\to Z.$ Prove or disprove a) For all subsets $\,A \subseteq X,\;\; f^{-1}(f(A)) = A$. b) For all subsets $\,B \subseteq Y,\;\; f(f^{-1}(B)) ...
1
vote
1answer
38 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
1answer
27 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 ...
0
votes
0answers
22 views
1
vote
1answer
13 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 ...
-3
votes
2answers
32 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
0answers
23 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 ...
1
vote
1answer
24 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 ...
0
votes
1answer
22 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 ...
2
votes
2answers
69 views

Odd binomial sum equality has only trivial solution?

Suppose $$\sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2} = \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}.$$ Does $m=n=1$? Clearly $m \leq n$, and for every $n$ there is at most one ...
3
votes
4answers
69 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
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
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
2answers
56 views

Integer solutions to an equation with a constant before x

The question is: How many integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + 3x_5 = 80$$ if $x_i$ is greater than or equal to 0? I understand how to get integer solutions to a ...
13
votes
0answers
938 views
+50

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
1
vote
3answers
63 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
36 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?
2
votes
1answer
56 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 ...
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$ ...
-1
votes
1answer
813 views

List the elements of the set

I'm working on my math homework and I don't even know how to do this or what it is asking. Any help would be great! Let $A = \{1, 2, 3\} \times \{1, 2, 3, 4\}$. List the elements of the set $B = ...
1
vote
3answers
75 views

Proof an inequality by mathematical induction

I have a problem that I have to solve using mathematical induction but I'm stuck from a part. The problem is: Proof that $\large n<2^n$ is true for $\large n \in \mathbb{N}\ $ So, I did that ...
3
votes
2answers
61 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
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 ...
-1
votes
2answers
785 views

Understanding delaying or advancing a discrete time signal

Suppose I have a discrete time signal x[n]. It is said that x[n-k], where K>0, is a delayed version of x[n]. I am trying to understand this intuitively. My observation is in the signal I am ...
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 ...
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.
1
vote
1answer
51 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. ...
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 ...
-3
votes
0answers
19 views

discretization of a continuous filter [on hold]

I have a 1st order continuous filter T * y'(t) + y(t) = u(t) . I discretized the equation by hand and applied filter and I used ...
0
votes
2answers
621 views

Greedy Algorithm, Fewest overlaps

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
1
vote
2answers
65 views

How can I prove if these are (or not) possible solutions for the following recurrence?

So I'm presented with no initial conditions and the following recurrence relation: $8a_{n+2}+4a_{n+1}-4a_n=0$ I need to determine if these are possible solutions, and in that case, which initial ...
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
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$ ?