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

0
votes
0answers
3 views

Getting equations from a network graph

I am learning about Network Analysis in Discrete Math and I need help figuring out how to get the equations from this graph: The arrows represent how many particles are going in a given direction. ...
2
votes
1answer
56 views

How do I prove these biconditional statements?

I keep getting stuck when I get to (not p or q) and (p or not q) for number 3 and for number 4 I get stuck in relatively the same place. Edit: I want to prove them with using equivalence laws, not ...
2
votes
0answers
9 views

Deduce the conclusion from the premise.

Use the valid argument form to deduce the conclusion from the premises, giving a reason for each step. A. ~p v q ➵ r B. s v ~q C.~t D. p ➵ t E. ~p Λ r ➵ ~s F. (conclusion) ~q So Far this is ...
1
vote
0answers
10 views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
0
votes
0answers
15 views

Translating English to Quantifiers

there is a student in this class who has chatted with exactly one other student $$ \exists x\exists y(y\ne x\land \forall z(z\ne x\to(z=y\leftrightarrow C(x,z))))$$ ƎxƎy(y ≠ x ^ ∀(z ≠ x -> ( z= ...
1
vote
1answer
29 views

In how many ways can we distribute 24 bullets among four burglars?

When distributing these bullets, each burglar must at least have three bullets, but no more than eight. I have tried solving this with generating functions, but I am stuck at this part where I am not ...
2
votes
1answer
8 views

How to figure out how many possible sequences contain a specific criteria

If a 6-sided die is rolled 5 times and each roll is recorded as an element of set A (|A| will be 5 after all rolls), How many results out of all the possible results will have exactly two 4's as ...
-4
votes
1answer
25 views

What is the effect in the time required to solve a problem when you double the size of the input from n to 2n? [on hold]

What is the effect in the time required to solve a problem when you double the size of the input from $n$ to $2n$, assuming that the number of milliseconds the algorithm uses to solve the problem with ...
1
vote
1answer
22 views

How to prove elementary identities for binomial coefficients using combinatorial arguments?

I'm in a second year discrete mathematics course, and we have identities like this $$\binom{n}{k}(n-k) = \binom{n-1}{k}n$$ and Pascal's Triangle law. Our professor said that algebraic proofs are ...
-1
votes
0answers
29 views

value for x in product 165432078*1009612= 167022211x3376

I have the next product: $$165432078*1009612= 167022211x3376$$ How can I now which the value for $$x$$ is?
1
vote
4answers
40 views

Inclusion and exclusion in combinatorics

You have 15 identical balls and must divide them into 4 drawers stacked on top of each other with the following limitations: You have at least 2 balls in each drawer There will be no more than 5 ...
1
vote
2answers
26 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
-2
votes
0answers
18 views

Parabolic Integration [on hold]

Hello, please i would like to understand the step from the first integral to the seconde. thanks
1
vote
1answer
14 views

Big O and Big Omega Proof with lg base 2

Hello I am a beginner to this kind of notation and I would greatly appreciate an explanation which is easy to understand. I need to prove $$ \log_2(6 + \frac1x) = O(1) $$ and $$ \log_2(6 + ...
2
votes
0answers
34 views

(Concrete) mathematical aspects of programming

It is often said that progamming is mathematics as it "makes use" of "discrete mathematics". However, I would like to ask a more concrete question: what are the concepts of a programming ...
0
votes
3answers
45 views

Showing that $S_1 \cup S_2$ is countable [duplicate]

Let's say that $S_1$ and $S_2$ are two countable infinite sets that are disjoint (i.e. $S_1 \cap S_2 = \emptyset$). How would you show that $S_1 \cup S_2$ is also countable?
0
votes
1answer
24 views

Ramsey Numbers and edge coloring

Show that for every $k \in\mathbb{N}$ there exists an $n \in\mathbb{N}$, where $n ≤ 3k!$ such that if $K_n$ is coloured in $k$ colours then we can find in $K_n$ a triangle whose edges are of the same ...
5
votes
1answer
53 views

Combinatorics - Without order

You have 10 different types balls to choose from. How many different ways are there to choose 5 balls such that no type of ball appears more than twice. My attempt: Case 1 (selecting different ...
2
votes
3answers
31 views

How do I describe a set of names?

I want to describe the following set... { "Person1", "Person2", "Person3"... } ... where the number is from 1.. 100. How do I do this using mathematical set ...
4
votes
5answers
100 views

Proving a Statement using Mathematical Induction

I'm trying to prove that $6 \mid (n^3 - n)$ where $n$ is a nonnegative integer. I started off by proving the basic step with $P(6)=4$. The next step would be the induction. However I'm having a bit f ...
0
votes
0answers
19 views

Discrete Mathematics; Counting, Summations [duplicate]

Let n ≥ 1 be an integer. Prove that: $$ \sum\limits_{i=1}^n i(\frac{n}{i}) = n \bullet 2^{n-1} $$ I am not sure how to prove this, I think I need to use the derivative of $$(1 + x)^ n$$ any help ...
1
vote
1answer
35 views

Number of Partitioning a deck with m cards in n types into n-element sets.

For exsample, There are 2cards in 3type. AA,BB,CC. Partition 6cards into 2 3-element sets. [AAB,BCC],[AAC,BBC],[ABB,ACC],[ABC,ABC],... 4 ways or Partition 6cards into 3 2-element sets. ...
0
votes
2answers
43 views

array of $n$ numbers, find the $2$ missing numbers

Given an array of size $n$. It contains numbers $1$ to $n$. Each number is present at least once, except for $2$ numbers. What algorithm will allow you to find the $2$ missing numbers?
2
votes
1answer
26 views

Find the covariance of $Y_1$ and $Y_2$

I had a statistics question I was hoping for help on: Let $Y_1$ and $Y_2$ be discrete random variables with join probability function: $$f(x,y) = \begin{cases} \dfrac{y_1 + 2y_2}{18} & \text{if ...
1
vote
2answers
30 views

Proving $\sum_{k=0}^{n} {n \choose k} = 2^n$ with Newton's Binomial Theorem

I'm having a hard time proving this theorem from a textbook. Theorem For any integer $n \ge 0$, we have $$\sum_{k=0}^{n} {n \choose k} = 2^n$$ Proof Take x = y = 1 in Newton's Binomial Theorem My ...
0
votes
0answers
8 views

finding percentge given number range

I have a range from 2.3566e-19 to 0.0010997 I'm trying to get the bottom 10% and the top 10% the formula / numbers I used is below but the answer doesn't look right how can I fix this. ...
2
votes
1answer
40 views

How does $n(n-1)(n-2)\cdots(n-m+1) \cdot \frac{(n-m)(n-m-1)\cdots1}{(n-m)(n-m-1)\cdots1} = \frac{n(n-1)(n-2)\cdots1}{(n-m)(n-m-1)\cdots1} $

I'm having issues understanding how the previous line goes to the net line. $$ \text{Assume } m \le n \\ n(n-1)(n-2)...(n-m+1) \cdot \frac{(n-m)(n-m-1)\cdots1}{(n-m)(n-m-1)\cdots1} \\ = ...
0
votes
3answers
52 views

Proof by Contrapositive?

i am having trouble proving the statement below using Proof by Contrapositive. I have negated the statements as required and then i prove that $n$ is odd if and only if $7n+4$ is odd. However, from ...
-4
votes
0answers
18 views

Discrete Math - graph theory [on hold]

Need help on Discrete Math Thanks!! Matt
0
votes
0answers
20 views

Proving bijection of a function of the form f(x,y).

I am trying to prove that the function $f:\mathbb{R}^2\rightarrow \mathbb{R}^2$ defined by $$f(x,y) = ((x^2+1)y, x^3)) $$ is bijective. I know that to prove a function is bijective we have to prove ...
0
votes
1answer
26 views

Modify the Cantor pairing function

I have an infinite set of pairs $I:=\{(k,m) \mid k,m \in \mathbb{N},\quad m\geq 1, \quad 1\leq k\leq m\}$. I want to establish a bijective correspondence $\phi$ between $I$ and $\mathbb{N}$. I've ...
1
vote
1answer
20 views

Prove that for all $m$, there exist some $k$, such that $(m-n)^2 > m^2$ for all $n>k$

I have a problem where I need to prove: $\forall m \in \mathbb{N}:\exists m \in \mathbb{N} ∋(m−n)^2>m^2~∀n>k$ My thought was since it is only "there exists some k.." can I not say: if $k = ...
0
votes
2answers
27 views

Logical equivalence + Quantifiers (Universal and Existential)

I'm taking a Discrete Mathematics course and we're using Rosen's book (which I hate because it seems like it makes difficult material to understand even more incomprehensible). Trouble is, I am lost ...
1
vote
2answers
49 views

Isn't $ n(n-1)(n-2)…(n-m+1) $ a factorial already?

Let $ m \ge 1 $ and $ n \ge 1 $ be integers Let $A$ be a set of size $m$ Let $B$ be a set of size $n$ How many one-to-one functions $f: A \rightarrow B$ are there? skipped stuff $$ ...
0
votes
1answer
26 views

the sum of two unbounded normal operators

why A and B are normal?and why "0" is not closed on H1(R)?
-1
votes
0answers
21 views

Probability helps to evaluate a sum

Let's consider a sum $$\sum_{n=0}^{m} \binom {n+m} {n} \cdot 2^{-n}$$. How does this sum can be evaluated, considering the topics about probability? One of the solutions is written at the "Concrete ...
1
vote
1answer
23 views

Determining if a function is one-to-one or onto.

We have two sets: {1,2} and {a,b,c}. How would I go about listing the functions between these two sets and then identifying if those functions are either one-to-one or onto? Would the functions be ...
0
votes
2answers
33 views

placing couples in a circle combinatorics question

In how many ways you can sit n men and n women so that : a) Every man sits near his wife. b) None of the men can sit next to thier wives. I think the answer for A is 2(n-1)!, not sure if it's true ...
2
votes
2answers
82 views

Counting the numbers with certain sum of digits.

The question : In how many different numbers between $1$ and $100000000$ have the sum of their digits equal to $45$? I'm thinking about using the stars and bars formula but I'm not sure if it's ...
1
vote
4answers
22 views

Completing simplification step when solving a recurrence

I am trying to understand a simplification step in one of the recurrence examples solved by repeated substitution in a book of algorithms problems I found on Github. I am using it for extra practice ...
2
votes
0answers
19 views

Erdős-Szekeres theorem on monotone sequences

Given a sequence $S$ with $21$ different numbers. It is known that there isn't any monotone subsequence in the length of $6$. Prove that there exists $2$ monotone subsequences, one decreasing and the ...
0
votes
3answers
30 views

Combinatorics question about picking a staff

This is the Question : In a building there are 5 men and 5 women. we need to pick representive for the building so that at least one woman and at least one man has to be there. there are no limitions ...
-1
votes
1answer
27 views

Counting relations question

I have a small question about relation counting, i'm looking for formulas. I know that there is a formula for reflexive and anti reflexive. I'm not sure about the simetric or a-simteric ones, and if ...
4
votes
1answer
41 views

$\land,\lor$ and $\lnot$ determinate a functionally complete basis

I read that a Boolean algebra is defined by the binary operations $\land$ and $\lor$ and the unary operation $\lnot$ on a set such that $$\varphi\land(\psi\land \chi)=(\varphi\land \psi)\land ...
0
votes
0answers
38 views

Importance Sampling of 2D constant piecewise function convertible to 1D?

So I have a constant piecewise 2D function (luminance values of pixels of an image) that I am writing an importance sampling algorithm for. I was going to write my algorithm by first sampling the 1D ...
-2
votes
1answer
39 views

using boolean law to simplify equation

I need to use boolean laws to simlfy the folliwng: a) (A+B)(C+D)+(A+B)(C'+D')= what I did for a) (A+B)(C+D)+(A+B)(C'+D') (A+B)[(C+D)+(C'+D')) (A+B(C+B)+(A+B)(c'+D') (A+B(C+B)+(A+B)(c'+D') Am I ...
-1
votes
1answer
168 views

Am I solving this question correctly?

How can I evaluate the following term: $$\left((\{a,b\}\cup\{b,a\})\times(\{b,a\}\cap\{a,b\})\right)\setminus \left((\{b,a\}\setminus\{a,b\})\cup(\{a,b\}\times\{b,a\})\right)$$ You can see the notes ...
-1
votes
0answers
28 views

Am I doing the Cartesian product of sets correctly?

Question in the image and how I attempt to solve it. Did I do it correctly? And is that the right answer?
-3
votes
0answers
63 views

Proving that $x’y’ + yz’ + x’z’ = yz’ + x’y’$ using the laws of Boolean algebra. [duplicate]

I'm trying to prove the following identity using the laws of Boolean algebra. $$x’y’ + yz’ + x’z’ = yz’ + x’y’$$ Here's what I've tried: [insert attempt here]
0
votes
0answers
26 views

Clique cycles structure

I am currently going through the paper "Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles" by Peter Allen (http://www.ime.usp.br/~allen/twocycle.pdf) and I have some ...