Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

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.

-2
votes
0answers
18 views

Making Paths to Adjacent Matrix is erroneous problem?

Is it possible make all path from any v vertex to any w vertex which are belong to given graph to a adjacent matrix? I think it is impossible because concept of adjacent matrix is just expression of ...
0
votes
0answers
11 views

Cardinality of cartesian products of a series of infinite sets

Let $\hat P(A)=P(A)-\{\emptyset\}$, and $A_0=\mathbb{N}$ and $A_{n+1}=\hat P(A_n)$. I was asked to prove $|A_n|=|A_n\times A_n|$ for any $n\in\mathbb{N}$. I thought about using induction: We have a ...
0
votes
1answer
4 views

Applying set operations on congruent mod relation

I've been asked a question to solve about congruent modulo. But the question is very different than another congruent modulo questions I have seen so far. It wants me to apply set operations on it. ...
-1
votes
2answers
47 views

Evaluate $\sum_{n=1}^N n {n \choose k}$ and get a closed form solution

Find a closed form of $\displaystyle\sum_{n=1}^N n {n \choose k}$. 1) Firstly, is it valid to simplify this equation to: $\sum_{n=k}^N n {n \choose k}$ because ${n \choose k} = 0$ for $n < k$? 2)...
0
votes
1answer
18 views

Universal Quantified Statement being equivalent when variables are swapped

I was given this statement and asked to express this with universal quantifiers. Likes(x,y) is a Binary Relation that means that person x likes person y. The statement given was: "Everybody is ...
-3
votes
0answers
37 views

find the minimum value of $2a^8+2a^6+a^4-b^3-2a^2-2$ and show the process

To find the minimum value of $2a^8+2a^6+a^4-b^3-2a^2-2$. Here is the image:
0
votes
2answers
47 views

Find number of five digit natural numbers using digits $1,2,3,4,5$ such that consecutive digits do not appear together

Find number of five digit natural numbers using digits $1,2,3,4,5$ without Repetition such that consecutive digits do not appear together I just tried in by listing the possibilities in a sequential ...
0
votes
0answers
15 views

Define $[n,k]$ as the number of $(n+k)$-lists of the form $a_1+a_2+..+a_i$ where n of the elements are $1$s and k of them are $-1$s

Define $[n,k]$ as the number of $(n+k)$-lists of the form $(a_1+a_2+..+a_i)$ where n of the elements are $1$s and k of them are $-1$s and where for all i , the sum of the first i entries is non-...
-1
votes
0answers
20 views

Find whether the following are lattice or not.

enter image description here I looked everywhere from youtube to my book, but no one is explaining "FOR EACH PAIR OF ELEMENT THERE IS A GREATEST LOWER BOUND AND LEAST UPPER BOUND", because to me ie, ...
1
vote
2answers
55 views

Arranging $n$ balls in $k$ bins so that $m$ consecutive bins are empty

This question is inspired by the following problem: Randomly place seven balls into ten bins, with no bin containing more than one ball. What is the probability that there will be (at least) two ...
1
vote
1answer
53 views

How many ways are there to distribute 25 identical balls among 5 players where each player must get at least 1 and no player may get 10 or more?

We know that $$x_1 + x_2 + x_3 + x_4 + x_5 = 25; 1\leq x_i < 10$$. Therefore, I'm thinking about getting all possible combinations and subtracting them by where 4 people get at least 1 and one ...
1
vote
4answers
34 views

Review on my method for $Number$ $of$ $diagonals$ in a regular $n$-gon is $\frac12n(n-3)$

I have an assignment on permutations and combinations topics. In that there is a question- The number of interior angles of a regular polygon is $150^\circ$ each. The number of diagonals of the ...
4
votes
2answers
38 views

Let $\mathbb{Z}$ be the integers with the discrete topology. Let $f: \mathbb{Z} \to \mathbb{R}$. Give conditions to have $f$ continuous.

This is part of an exercise with different sections. I've proved that $\mathbb{Z}\subset \mathbb{R}$ has the discrete topology as the subspace topology. Now they ask me the following: Let $\mathbb{...
4
votes
4answers
790 views

How many ways can the cube be arranged such that the red face is adjacent to the blue face?

Each face of a cube can be painted in one of six colors and the color of each face must be different. Suppose you pick a coloring uniformly at random from the set of allowed coloring. How many ways ...
0
votes
1answer
15 views

Equation Involving Digit Sum Function

Define the digit sum $S$ of a number as the sum of its digits. For example, $S(456)=4+5+6=15$. Given positive integers $a_1, \cdots, a_n$ and $Q$, I'd like to ask how to obtain the nonnegative ...
-1
votes
1answer
25 views

Derrangments function for coloring a chess table

How many ways are there to color a chess table of size n*n with n different colors. We color in such a way that in each horizontal row there are all colors and at the same time in no vertical row ...
2
votes
0answers
65 views

Find a good formulae

We know that equation $$s_1+s_2+s_3=n-1 \quad \mbox{$s_1,s_2,s_3$}\geq 1$$ has $\binom{n-2}{2}$ solution. I want to find any good formulae for the following form : $$\sum\limits_{(s_1,s_2,s_3)}\...
0
votes
1answer
37 views

Is $T(n,m) = 2\, T(n-1, (m-1)(1-1/n))$ polynomial in $n$ and $m$? [on hold]

Can you prove or disprove that $T(n,m)=2T(n-1, (m-1)(1-\frac{1}{n}))$ grows polynomially in $n$ and $m$? If it matters, $T(1, j) = 1$ and $T(i, 1) = 1$. Usually $m$ is much greater than $n$, or at ...
0
votes
1answer
25 views

Show that if 3 does not divide n, then n is congruent to 1 (mod 3) or n is congruent to 2 (mod 3).

I'm curious to know whether my proof makes sense and if there's an easier method, as I'm still trying to wrap my head around this question. My proof is as follows using the contrapositive. ...
1
vote
1answer
51 views

Finding the minimum number of cards to be drawn Generalized Pigeonhole Principle

Suppose you have a drawer with cards on which a number $1$ through $18$ is written. You can pick cards from the drawer with your eyes closed. What is the minimum number of cards you have to draw to ...
1
vote
3answers
39 views

When do i use the power ^ sign in a combination question?

My problem: If there are 5 different candies in a jar and a child wants to take out one or more candies, how many ways can this be done? I said it is $^5C_1 -\; ^5C_0 = 5-1 = 4$ ways. The $-1$ for ...
1
vote
1answer
19 views

Find the Recurrence relation for $q_n$ given the following condition:

Let $q_n$ denote the number of strings of length $n$ (formed from digits 0,1,2,3) which have even number of $2$'s. set up a recurrence relation for $q_n$.
1
vote
3answers
27 views

Solve the recurrence relation $f(n) = 4f(n/3)+5$ where $n=3^k, k=1,2,3…$ and $f(1)=5$

Solve the recurrence relation: $f(n) = 4f(n/3)+5$ where $n=3^k, k=1,2,3...$ and $f(1)=5$ I never seen a recurrence relation like this before. What would I need to use or do to solve this?
0
votes
1answer
18 views

Using Generating Function to calculate number of ways to select committees

How many ways are there to select three committees from 10 people? The committees serve different purposes, someone has to be in every committee and everyone serves in exactly one committee. (Use the ...
0
votes
0answers
21 views

Discrete Mathematics on Contraposition [on hold]

For all irrational number x, square root x is irrational. I dont know how to solve it using Contraposition. Please Help
0
votes
2answers
18 views

Proof by induction coins

Question: Tom only have 2 type of coins: coins: 4 cents and 5 cents. Write a proof by induction that every amount n ≥ a can indeed be paid with Tom coins 1) Base Case: Tom can pay $12, $13, $14, $15, ...
0
votes
1answer
26 views

Give an example of a function from $\mathbb N \to \mathbb N$ that satisfied

For each of the following properties give an example of a function from $\mathbb N \to \mathbb N$ that satisfied: (a) one-to-one but not onto (b) onto but not one-to-one (c) both onto and one-to-...
0
votes
1answer
24 views

Is there a non-planar, non-hamiltonian and eulerian graph?

I'm trying to find a graph that is non-planar, non-hamiltonian and eulerian but I can't find anyone. Is this possible? Thanks
1
vote
4answers
30 views

How can I prove that for any $A, B$ if $A\subseteq B$ and $B\subseteq C$, then $(C-A)\cup (B-A)\subseteq C$?

How can I prove that for any $A, B$ if $A\subseteq B$ and $B\subseteq C$, then $(C-A)\cup (B-A)\subseteq C$? I've been working on this question and I haven't really made much progress with it. I ...
2
votes
1answer
35 views

Pigeonholes and onto functions

I've been scratching my head at this problem for a while and can't seem to figure out why the number of pigeonholes is $3^5 - C(3, 2)2^5 + C(3, 1)1^5$ and not $3^5 - C(3, 2)2^5 - C(3, 1)1^5$ ...
1
vote
1answer
27 views

Predicate Calculus and Statement

I'm having a hard time to understand predicate Calculus, Statement and Prolog programming. Let $male$ be a unary predicate symbol with the indicated meaning. Let $parent$, $son$, $sibling$, and $...
0
votes
1answer
22 views

Probability with Births and Discrete Math

A couple is planning to have a family. Let us assume that the probability of having a girl is 0.48 and a boy is 0.52,and that the gender of this couple’s children are pairwise independent. They want ...
4
votes
1answer
205 views

Show circle with points coloured red and blue must have monochromatic red equilateral triangle

Colour each point on a circle of radius $\frac{1}{2}$ red or blue, such that the region of blue points has length $1$. Prove that we can inscribe an equilateral triangle in the circle such that all ...
0
votes
1answer
33 views

Confuse in Probability in Discrete Mathematics about train late problem

A student is being late to catch the morning train in 3/10 of trials. If he runs of on time he will always catch the train. If he runs of late, he gets to the station with 5 min delay after regular ...
0
votes
1answer
12 views

Solving Recurrence Relation for the number of n-letter words

Find and solve the recurrence relation for the number of n-letter words composed from letters A, B, C and D such that no A comes after any B. What I learn in the class is, $$ A = a_{n-1} $$ $$ B = 3^{...
-2
votes
1answer
13 views

Help Understanding Solved Proof for Existential and Universal Quantifiers [on hold]

I am having trouble understanding how they went from the 1st line to the 2nd line. Is there some rule that I am missing? If so, can someone please tell me what that rule is? Thank you so much! Click ...
1
vote
2answers
43 views

Infinitely many consecutive primes with difference greater than 2. [on hold]

Let $p_k$ be the $k$-th prime number. Show that there are infinitely many $k$ such that $$p_{k+1} − p_k > 2$$. Suppose If this is not true then won't that contradict the twin-prime conjecture?
0
votes
2answers
105 views

Probability of sending same postcards to 10 friends out of 15 types of postcards

In a shop there are 15 types of postcards, and you want to send one postcard to each of 10 friends. To save precious vacation time, you decide to select each postcard independently at random from the ...
0
votes
0answers
21 views

What can I use online to plot 2D and 3D diophantine equations?

Using the algebraic operations and equality, and (scatter) plotting the integer solutions, for example: Plotting $x$ and $y$ for $x^2 + y^2 + n^2 = 9$ $(2, 2), (3, 0)$ and $(0, 3)$ are among the ...
-1
votes
2answers
65 views

Pigeonhole Principle Proof Generalized

An airport sees 1500 takeoffs per day. Prove that there are two planes that leave within a minute of each other. All I can get started with is finding the total minutes in a day- 1440min. I ...
0
votes
1answer
23 views

How to Prove The Complement Of The Domain Is Complement Of The Image If f Is Bijective

It seems true that $f(\overline{X}) = \overline{f(X)}$ for $f:A\rightarrow B$ and $X$ is any subset of $A$ if and only if $f$ is bijective.But I couldn't write it as a formal way like epsilon argument....
1
vote
0answers
47 views

Solve recurrence for strings that do not contain the substring 101

Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2\cdots8.$ Find a recurrence relation for $A_n$. What does the ...
-3
votes
2answers
23 views

If |A| = 10, how many subsets are in the power set of A? [on hold]

Discrete mathematics Please give additional steps
0
votes
1answer
26 views

Arrange people at round table so that everyone knows the two people next to them

Each of the guests know: a) more than half of the guests b) at least half of the guests. Prove that in both of these cases it is possible to arrange them to sit around a round table so that everyone ...
0
votes
1answer
54 views

Why $∀x(P(x)→Q)$ is equivalent to $∃xP(x)→Q$

Given $x$ occurs free in $P$. If $x$ does not occur free in $Q$, then $∀x(P(x)→Q)$ is semantically equivalent with $∃xP(x)→Q$. How to understand this statement. And also, need an example to show that ...
1
vote
1answer
41 views

What is uniqueness quantification?

Can someone explain the concept of Uniqueness quantification ∃! in an easily understandable way since I can't understand the definition of it, what's special about it with other logical operators like ...
-1
votes
1answer
40 views

Probability and using Time with Passwords and combinations

Consider Bob, an absent-minded student. Bob has a set of 6 passwords that he uses for all his login needs. He often forgets which password matches with which website so his strategy is to try all of ...
0
votes
0answers
17 views

Question about the proof of Linear Homogeneous Recurrance Relations.

In Rosen's book, there is a proof of a theorem on Linear Homogeneous Recurrance Relations. To prove the only if part of this theorem, why all we need to prove is ...
0
votes
0answers
28 views

Roulette Expected Winnings Discrete Math

Someone is playing Roulette. Here is an example of an outcome: If a player bets on a single outcome the payout is 35 to 1 – meaning if the player guesses the correct answer and puts down a dollar, he/...
2
votes
2answers
68 views

How many words of length $n$ over the alphabet $\{0,1, 2\}$ contain an even number of zeros?

How many words of length $n$ over the alphabet $\{0,1, 2\}$ contain an even number of zeros? I can't understand why it isn't $3^{n-1} \cdot 2$. For $n-1$ letters, we have $3$ options. That means $3^{...