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
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
29 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
42 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
69 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
24 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
30 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 ...
2
votes
1answer
113 views

What branch/field of mathematics is this? [closed]

I do not want solutions, I just want the field/branch of mathematics that these problems deal with, and possibly a good online source or two to learn it. Problems :- 1:- 2:- 3:- 4:- ...
-1
votes
1answer
49 views

Is there a book about discrete algebraic structures? [closed]

In German it is called "Diskrete algebraische Strukturen".The literal translation would be discrete algebraic structures, does something like this exist? The course contains the following topics ...
-1
votes
2answers
56 views

Compute this sum $\sum\limits_{i=3}^n \binom{n}{i} \frac{i!2^{i-3}}{(i-3)!}$ [closed]

I'm having problems calculating this: $$\sum_{i=3}^n \binom{n}{i} \frac{i!2^{i-3}}{(i-3)!}$$ I got that it equals to $3^n$ but it's not the correct answer. P.S. If it is necessary I can provide my ...
0
votes
1answer
26 views

Hardness for problems with non constant input parameters.

It's well known that problems like $3$-sat and $4$-sat and probably $k$-sat for $k\geq 5$ are NP-hard problems but what happens for example if i was to consider something like $\lceil \mathrm{log}(n) \...
0
votes
2answers
52 views

Show $\sum_{i=1}^{n+1} 2^ii = 2^{n+2}n+2$ , for all integers $n\ge 0$ using induction.

How would i solve this problem?, i tried and went through the entire process is this correct and how would i factor the induction part. $\sum_{i=1}^{n+1} i\cdot 2^i = n\cdot 2^{n+2}+2$ , for all ...
0
votes
1answer
24 views

What is the complement of a product of two sets?

I am given this information: Suppose $A=\{1,2,3\}$, $B=\{3,5\}$, $C=\{1,2,4,6,9\}$ and $U = \{0, 1, 2, 3, 4, 5, 6,7,8,9\}$. Enter "T" for each true, and "F" for each false statements. There ...
0
votes
1answer
11 views

Sum of products expansion of basic Boolean function: $ F(x,y) = \bar{y} $

So I have a question about this very basic-looking sum of products expansion. My professor has this particular example in his lecture slides but I can't quite wrap my head around this. I don't ...
0
votes
1answer
69 views

What is the name of this property of a set?

Let $S$ have property $P$ if there exists a function $f(x,y)$ such that: the domain of $f$ is $(S,S)$ the range of $f$ is $(-1,0,1)$ if $f(a,b) = 1$ and $f(b,c) = 1$ then $f(a,c) = 1$ and if $f(a,b) =...
0
votes
0answers
32 views

Calculate maximum value limit in set partition

I have all the subset of 4 element as follows with value associated with each subset ...
0
votes
1answer
32 views

Using induction on modified inequalities.

Here's the original problem: Prove by induction that $\left(\frac{1}{2}\right) \left(\frac{3}{4}\right) \cdots \left(\frac{2n-1}{2n} \right) \leq \frac{1}{\sqrt{n+1}}$ for all $n \in \mathbb{N}$. ...
1
vote
2answers
30 views

Mathematical induction for discrete math problem

I need to use mathematical induction to prove that $$(z+1)^n=\sum_{k=0}^n{n\choose k}z^k$$ $z$ is any complex variable I know that ${n\choose k}=\frac{n!}{k!(n-k)!}$ and that $0!=1!=1$. I did the ...
4
votes
2answers
87 views

How many functions from $\{0,1\} \times \{0,1\}$ to $\{0,1,2\}$ are there?

The question in my homework is: How many functions from $\{0,1\} \times \{0,1\}$ to $\{0,1,2\}$ are there? How many are one-to-one? How many are onto? My first step was to take the Cartesian ...
5
votes
6answers
116 views

Factoring out a $7$ from $3^{35}-5$?

Please Note: My main concern now is how to factor $7$ from $3^{35}-5$ using Algebraic techniques, not how to solve the problem itself; the motivation is just for background. Motivation: I was trying ...
1
vote
1answer
22 views

Explain why this relation has a reflexive, symmetric, antisymmetric, and transitive propery

Let S = {1, 2, 3} Let R = {(1,1),(3,3),(2,2)} So the answer is that it is reflexive, symmetric, antisymmetric, and transitive. I understand that it is reflexive, however I do not understand how it ...
0
votes
0answers
54 views

How can I understand the step by step calculations for the formula from the blog below?

I am studying clustering and found a useful article on the blog post here Finding the K in K-Means. But I am having difficulty in understanding the formulas below and how I can do step by step ...
0
votes
0answers
22 views

Aliasing-effect and Nyquist-Shannon-theorem

I have to examine the aliasing effect occuring at discrete fourier transform using the testfunction $g(t) = \sin(\omega t) + \sin(4\omega t)$. I sample the function in the interval $t \in [0: T]$ ...
0
votes
1answer
24 views

strong induction factoring question

I seen an example from my book and the factoring didn't make any sense can someone help me understand the factoring that they used? suppose that $e_0, e_1, e_2... $ is a sequence defined as follows: ...
0
votes
0answers
17 views

Characteristics of relations. Are these relations correct?

The question ask: Let $A=$ {$1,2,3$}. List the ordered pairs and draw the digraph of a relation on $A$ with the given properties. I just want to check if my ordered pairs are correct or not so I have ...
0
votes
1answer
15 views

Safe to say Disjunction (OR) is considered as Logical True while Conjunction (AND) is considered as Logical False

I'm back again to ask some discrete mathematics question. I was studying about the connectives with truth table while i stumbled upon a similar case. I wonder if i'm right to safely assume that ...
1
vote
1answer
33 views

I have a question involving logical quantifiers which I have been stuck on for a while. I have trouble understanding the concept.

There is a question that has been bothering me where the concept is confusing to me. Assume B is the set of all boys and G is the set of all girls. L(B,G) represents that B likes G. $$\forall b \in ...
2
votes
4answers
56 views

Proving $ a^4 \equiv 1 \pmod d$

I need to prove the following statements: Prove the following statements: (a) if $a$ is odd then $a^4 ≡ 1 \pmod 4$, (b) if $5$ does not divide a, then $a^4 \equiv 1 \pmod 5$. Can I do this ...
0
votes
1answer
42 views

Prove there's a monochromatic isosceles triangle.

The points in a circle are coloured red and blue. Prove that there exists a monochromatic isoceles triangle. I can prove that there exists a monochromatic triangle. If there are no three points of ...
0
votes
0answers
32 views

Application of tensor product of graphs in real life.

I was going through the book HANDBOOK OF PRODUCT GRAPHS by Richard Hammack, Wilfried Imrich, and Sandi Klavzar. In the preface section, application of direct product of graphs is mentioned. I am ...