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

Linear Travelling Tournament Problem: 4 teams

The linear travelling tournament (LD-TTP) is a variant of the travelling salesman problem (TS). The LD-TTP’s objective is to find a round-robin schedule that minimizes the total travel distance ...
0
votes
2answers
28 views

What type of order is $A/{\sim}$ if $A$ is…

I find it hard to understand this question and proving different types of order. I hope someone can help me. If $A = \langle A,\ge\rangle$ and for all $a,b \in A $ it’s the case that $a \sim b$ ...
1
vote
2answers
40 views

Given the function $f:[0,1]→[0,1]$; $f(x)=x^2$, check which one(s) of the properties it has.

This homework is past due, but I am still fiddling trying to figure this out. question: I do not understand what the heck the notation of $f:[0,1] \to [0,1]$; means. I thought I did, but my ...
-4
votes
2answers
52 views

b) How many onto functions are there from A to C? [duplicate]

Let $A=\{1,2,3,4\}$ Let $B= \{a,b\}$ Let $C= \{ \text{hiking, baseball, hockey} \}$ a) How many onto functions from A to B $(1,a) (1,b) (2,a) (2,b) (3,a) (3,b) (4,a) (4,b)$ Thus 8. b) How many ...
0
votes
2answers
35 views

Clarification on inductive proof of Bernoulli's inequality

Prove that if $h > -1$, then $1 + nh ≤ (1+h^n)$ for all nonnegative integers $n$. I've read several solutions and I'm still totally lost on how to go about this. I have the inductive hypothesis:...
0
votes
1answer
28 views

Reflexive, Symmetric, Transitive for (a,b)E R iif (a-b) is a multiple of k

If k is any positive integer, and R is a relation on the set 0,1,2,3 as (a,b) are elements of R iif (a-b) is a multiple of k. Is R reflexive, symmetric and/or transitive. I know reflexive means x=x; ...
0
votes
1answer
13 views

How to prove that partial order is isomorphic a linear order

I'm trying to solve a question in discrete mathematics, but I do not understand how to solve it... The question: Is a partial order (set with four elements) isomorphic a linear order with three ...
0
votes
1answer
26 views

Hasse Diagram with “better than” relation [closed]

Adam have five elements to choose between; a, b, c, d and e. His preferences (better than) are as follows: a < b b < c c > d a < c b > a c > e a < d b > e a > e Kate have also five ...
0
votes
0answers
22 views

Consider the system S which can take n input parameters and each parameter can take on m values

(a) What is the maximum number of pairs a single test case for this system can cover? "I know that there are m^n different combinations in this example, but i'm unsure how many pairs a single test ...
-2
votes
0answers
28 views

Order relations and properties, dilemma [closed]

A, B, C and D are prices in a gameshow that I've just won. I must choose one price and according to the task my preferences are; A is equal to C D is equal to A B is equal to C D is better then C B ...
0
votes
1answer
24 views

How to prove this using laws? [closed]

How do they prove this? $$(p\to q)\land[\neg q\land(r\lor\neg q)]\equiv\neg q\land\neg p$$
2
votes
0answers
89 views

Number of ways to connect vertices of n squares with line segments

What is the number of ways to connect the vertices of n squares with non-intersecting line segments ? These line segments should not cross the edges of the given squares as well. Obviously $N(3)$ is ...
0
votes
0answers
26 views

matrix multiplication result value range

Here is the initial question: About the output value range of LeGall 5/3 wavelet Today I found actually the transform can be seen as a matrix multiplication. It is easy to calculate the wavelet ...
0
votes
0answers
22 views

How to make check matrix H when you have generator matrix (algorithm)

It's all built on top of python numpy lib. So we have a class finite field and get access to elements of field like Finite_field[index_of_element]. Elements of field are numpy matrices(ndarray). For a ...
2
votes
1answer
29 views

Difference sets without squares of Integers

I am trying to print numbers occuring in A030193 i.e Let S = set of square numbers; a(0)=0; a(n) = smallest m such that m - a(i) is not in S for all i < n. but I am unable to do it in better ...
2
votes
3answers
68 views

Is $\emptyset$ considered as a powerset by itself?

For example, $X = \{\emptyset, a, \{b\}\}$. Find the power set of $X$. As far as I believe everyone understand, a power set of something means to display whatever element is within the set itself. ...
3
votes
1answer
32 views

Why am I under-counting when calculating the probability of a full house?

I was trying to answer this question. Find the probability of getting a full house from a $52$ card deck. That is, find the probability of picking a pair of cards with the same rank (face value), ...
-1
votes
1answer
69 views

Is there a basis which spans the real numbers?

Is there a finite set of real numbers $S=\{a_1, a_2, ..., a_n \}$ such that every real number can be written as a linear combination (with integer coefficients) of the elements of $S$? If no, is there ...
6
votes
2answers
547 views

Why is $\{\{1\}\}$ not equal to $\{1,\{1\}\}$?

Determine whether each of these pairs of sets are equal$$A = \{\{1\}\} \qquad \qquad B = \{1, \{1\}\}$$ I believe $A$ is equal to $B$ because all elements in $A$ are in $B$, but the answer says that ...
0
votes
1answer
44 views

Matrix-Tree Theorem for rooted directed graphs

I am working my way through the proof of the theorem on the pages: 3,4,5 in the script here. I understand almost everything but the most essential idea: how to connect ...
1
vote
1answer
40 views

How many ways are there to pick k cards in a game of Skat?

In a game of Skat there are 4 suits (spades, hearts, diamonds, clubs) and 8 values (7, 8, 9, 10, jack, queen, king, ace) yielding 32 cards altogether. I'm trying to figure out in how many ways $k \geq ...
5
votes
1answer
123 views

Minimum number of edges such that $\chi_1=\chi$ (version 2)

I have asked this question a few months ago here. I received an answer that I will explain, but found a mistake in the proof. I am looking for new answers, or for a way to correct the one that has ...
0
votes
1answer
35 views

Summation Notation (Discrete Mathematics) [closed]

I am currently studying sequence which I think will lead up to my next topic induction. My question is if $$\sum_{k=0}^n \frac{k+1}{n+k}= \frac{1}{n}+\frac{2}{n+1}+\frac{3}{n+2}+\cdots+\frac{n+1}{2n}$...
0
votes
0answers
10 views

Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$. I know about Lovasz extension, but it works in other way: given submodular ...
4
votes
2answers
76 views

Proving that $\lceil f(x) \rceil$ $=$ $\lceil f(\lceil x \rceil )\rceil$ when $f(x) =$ integer $\implies x =$ integer

On P. 71 in 'Concrete Mathematics' the following Theorem is given: Let $f$ be any continuous, monotonically increasing function on an interval of the real numbers, with the property that \begin{...
0
votes
1answer
42 views

If a set $A$ is uncountable , and a set $B$ is countable then $A \times B$ is uncountable.

I prove it by contradiction. Let $A \times B$ is countable. It means we can list down the all the ordered pairs of $A \times B$. So if ordered pairs of the form $(a,b)$ are countable (where $a \in A$ ...
1
vote
1answer
27 views

Recurrence equation for sequence of vectors

Consider recurrent formula for a sequence of numbers $(y_n)$ (either real or complex): $$a_k y_{n+k}+a_{k-1}y_{n+k-1}+\cdots+a_0y_n=\sum_{i=0}^k a_i y_{n + i} = 0$$ It's known that the exact explicit ...
4
votes
2answers
64 views

How many distinct ways are there to $2$-color the $8$ vertices of a cube?

How many distinct ways are there to $2$-color the $8$ vertices of a cube, with colorings only considered distinct up to rotation?
0
votes
0answers
31 views

Applications of tensor product of graphs (modelling of Internet Graphs)

I was going through the book Handbook of Product Graphs, by Richard Hammack, Wilfried Imrich, Sandi Klavžar. Somewhere in book, they mentioned the following lines : One of the applications of tensor ...
0
votes
1answer
27 views

In how many ways can 10 different things be distributed to 4 persons if 2 are to receive 2 things and the others are to receive 3 things?

I have no idea how to answer this question, I did a lot of research on trying to figure it out but every answer is so different. I would prefer something along the lines of using combinations and ...
1
vote
1answer
27 views

Conditional probability in independence and mutually exclusive events.

This thread shows that if two events are to be mutually exclusive and independent, one of them should have zero probability. I worked the following example that seems to contradict conditional ...
4
votes
2answers
82 views

Find $x$ in $1!+2!+\ldots+100!\equiv x \pmod{19}$

Here I come from one more (probably again failed) exam. We never did congruence with factorials; there were 3 of 6 problems we never worked on in class and they don't appear anywhere in scripts or ...
0
votes
1answer
59 views

Function over non-numerical sets

Considering a finite lexicographically ordered set, for example, $\{a, b, c, d\}$ called $A$ with $A$ as domain and codomain of a function which returns the element with right shift of 1 over A, how ...
0
votes
2answers
26 views

Finding the generating function of a recurrence relation in dependence of a variable

Given this inhomogeneous linear recurrence relation of 2nd order : $F_n = F_{n-2} + a$ for $n \geq 2$ with $F_1 = 1$ and $F_0 = 0$ How do I find the generating function of this recurrence ...
0
votes
0answers
17 views

How to investigate the relationship between range and payload?

I am interested in learning about the relationship between range and payload for an electric aircraft. How do I use math to investigate the relationship between range and payload for an electric ...
1
vote
0answers
21 views

If $n,r\in \Bbb{Z}^+$ and $2^{r-1}+2-r \leq n < 2^r+1-r$, find $r$ in terms of $n$ in closed form.

For integer $r$ and $n$, consider the relations $$2^{r-1}+2-r \leq n < 2^r+1-r$$ To eliminate possible pathological cases for small $n$, take both $n$ atnd $r$ to be at least $3$. I'd like to ...
3
votes
1answer
27 views

Is a relation between A and B the same as a mapping from elements of A to subsets of B?

The way I always saw it was that a relation is a subset of $A \times B$, or a collection of ordered pairs $(a,b)$, where $a \in A$ and $b \in B$. Is there any meaningful distinction between the two ...
-1
votes
0answers
22 views

Finding the cardinality of sets [closed]

Find the cardinality of each of the following sets. a) {x, {x}} b) {a, {a}, {a,{a}}} c) P({a, {a, {a}}}) d) P({∅})
1
vote
2answers
47 views

Number of ways to choose 4 groups of 4 people from a set of 16 people

How many ways are there to choose 4 groups of 4 people each from a set of 16 people (the groups are distinct) ? I can't quite decide if the answer should be ${16 \choose 4} + {12 \choose 4} + {8 \...
1
vote
1answer
41 views

Closed form solution of a hypergeometric sum.

The binomial theorem is one of the best known hyper-geometric sums for whom a closed form expression exists. The natural question is whether generalizations exist . In particular I would like to know ...
1
vote
2answers
67 views

Bound on the value of $\binom{n }{n/2}$

I know the value of $\binom{n}{r}$ is maximum for $r=n/2$ if $n$ is even. I am in need to calculate the value of $\binom{n}{n/2}$. \begin{align*} \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\ldots+\binom{...
0
votes
1answer
32 views

Discrete Mathematics - Quantifiers problem

This is a question from the Discrete Mathematics question from Kenneth Rosen book. I didn't understand the question and thus I am confused how to begin with question. Below is the question from the ...
0
votes
1answer
26 views

Quantifiers Kenneth Rosen Discrete Mathematics

Please help me in regard with this question.I didn't have a clue how to solve this. The way I thought about this question is assuming the truth values of predicates P(x) and Q(x) and then trying ...
4
votes
3answers
68 views

Are Pandemic chain reactions confluent? (vertex spills weight to neighbors at threshold, once)

Are resolutions of chain reactions order-independent in the board game Pandemic? More formally: You're given an undirected graph $G = (V, E)$ and a vertex weight $w \colon V \to \{0, \ldots, 3\}$. ...
0
votes
3answers
40 views

Solving polynomial equations given some constraints

I want to solve a polynomial equation but I know that it can have exactly one root. Is there some method to solve these kinds of problems. for example- $$A(1+x)^4 + B(1+x)^3 +C(1+x)^2 + D(1+x) +E=0$$...
0
votes
1answer
27 views

Possible two digit hex numbers

I'm currently learning about counting theory, and I feel like I am confusing myself with a question asking the following: Hexadecimal digits are formed from 0-9 and A-F, how many possible digits can ...
1
vote
0answers
23 views

What is the proof of the formula for generalized permutations (permutations with finite repetition allowed)?

I have currently been studying discrete mathematics and combinatorics where I came across the introduction to generalized permutations in the textbook (Introductory Discrete Mathematics by V.K. ...
0
votes
1answer
29 views

Finding the number of vertices in this graph

A graph $G_{n,k} = (V, E)$ for $n,k \in \mathbb{N}$ ist defined by: $V = \{M$ $|$ $M \subseteq [n] \text{ and } |M| = k\}$, $E = \{\{v_1, v_2\}$ $|$ $v_1 \cap v_2 = \emptyset\}$ $\subseteq P_2(V)$...
0
votes
2answers
15 views

Usage of “for which” P(x,y) is false during quantification of two variables

There's a little confusion between the usage of "for which" in my discrete mathematics explaination. I do need a little help to break down this connective. For instance : ...
0
votes
1answer
41 views

How many integers in $\{500,…,1000\}$ are not divisible by 3, 7 or 13?

I am wondering what the best way to approach this question is. I thought that I would calculate the number of integers that aren't divisible by 3, 7 or 13 in $\{1,2,...,1000\}$ as well as the number ...