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
1answer
17 views

How to prove that a map is bijective and how to win the inclusion exclusion theorem

Let $S$ be a set of n elements and $V$ the $2^n$-dimensional vector space of all maps $f : 2^S \to \mathbb{C}$ Let $\phi : V \to V$ be the linear map so that for $f : 2^S \to \mathbb{C}$ the ...
1
vote
0answers
11 views

Naive Bayes classfier prove

I have a question about the binary classifier about the way to prove it as a linear classifier. For example, Consider binary classification where the class attribute $y$ takes two values: $0$ or $1$. ...
0
votes
1answer
8 views

Does this component have 2 2-clan and also 2 2-clique

I have done many examples with n-Clan and also with n-Clique, but I found an example online as shown in the figure bellow, it says there is only 1 2-Clan and also 1 2-Clique, nevertheless I think it ...
0
votes
0answers
11 views

Questions on Erdős–Ginzburg–Ziv theorem for primes and understanding related lemmas and there applications.

While trying to prove the prime case of Erdős–Ginzburg–Ziv theorem: Theorem: For every prime number $p$, in any set of $2p-1$ integers, the sum $p$ of them divisible by $p$. I came across with ...
0
votes
0answers
16 views

minimising quadratic function subject to integer solutions

I would appreciate if one could help me to solve this problem. I have a bivariate quadratic function: $$ f(a_1,a_2)=(1-u_1^2)a_1^2 +(1-u_2^2)a_2^2 -2u_1u_2a_1a_2 $$ where $u_1^2+u_2^2=1$ and $a_1$ ...
0
votes
0answers
13 views

Software for computing n-Clique, n-Clan, n-Plex?

I am studying graph theory and complex network into details, I would like to ask if some one could help providing a useful (academic) tools or some good tools for computing n-clique, n-clan, n-core, ...
0
votes
1answer
13 views

Falling power of a sum in terms of falling powers of the terms

I am trying to come up with an expression for $(x+y)^{\underline{n}}$ in terms of $x^{\underline{r}}$ and $y^{\underline{r}}$. I tried for $n=2$ and $n=3$ and it looks like binomial expansion holds, ...
4
votes
1answer
46 views

What is the result of $\cap_{n=1}^{\infty}{(-1/n; 1/n)}$

I would like to know the intersection of $(-1/n ; 1/n), \forall n \in N$. I am in trouble thinking it could be $\{0\}$ or $\emptyset$. Can anyone help me?
1
vote
1answer
25 views

How can i prove $p\to (q \vee r) \equiv (p \wedge \sim q) \to r$?

please Help me in this question i have tried to solve it like this: $$p \to (q \vee r) \equiv (p \wedge \sim q)\to r$$ $$p \vee \sim (q \vee r) \equiv \sim(p \wedge q)\vee r$$ $$p \vee \sim q \wedge ...
1
vote
1answer
18 views

K-Clan detection based on a given connected Graph

I have the following definition of the K-Clan: A k-clan is a k-clique where the diameter of the corresponding sub-graph is at most k. and here according to the graph bellow I do not know why 135 is ...
0
votes
1answer
39 views

How many people does the $n$th person know? [on hold]

Arrange $N$ different people in a row. For each $k$ from $1$ to $N$, define $P(k)$ to be the $k$th person in that row. Then $P(k)$ ($k$ is from $1$ to $N-1$) knows exactly $k$ people ...
0
votes
2answers
21 views

Find a graph with critical vertices and without critical edges.

A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G. Obviously such decrement can be no more than 1 in a graph. A critical graph is a ...
0
votes
0answers
16 views

How to calculate the disjunctive normal form of boolean function? [on hold]

How to calculate the disjunctive normal form of boolean function?
3
votes
5answers
177 views

What does “$x$ divides $y$” mean?

I need to negate the following sentence: "If for the integers $x, y, z$ we know that $x$ divides $y$ and $y$ divides $z$, then $x$ divides $z$." In this scenario, what does it mean for $x$ to ...
0
votes
1answer
16 views

Definition of discrete $\mathcal{l}_1$norm

The $\mathcal{l}_1$ in $\mathbb{R}^n$ is $$ \|{v}\|_1=\sum_{j=1}^n\left|v_j\right|$$ and the definition of $\|\cdot\|_{1,h}$ is $$\|{v}\|_{1,h}=h\sum_{j=1}^n\left|v_j\right|$$ My question is: Is ...
0
votes
2answers
26 views

Linear/Discrete Math Equivalence Classes

I am confused on this question: For each of the following binary relations on $\Bbb R$, state whether or not the relation is an equivalence relation. If it is an equivalence relation, describe the ...
0
votes
2answers
35 views

What delimits the mathematical framework within which information compression limits (from entropy) are valid.

Lets suppose for absurd that I eliminate one number from the naturals. If I were supersticious I would eliminate number 13. Now imagine that to keep normal mathematics possible within such system ...
-1
votes
0answers
39 views

Decribe the set ? List or word [on hold]

$S=\{x\mid x\text{ is element of non-negative integer and (Eq) }(q\to x=2q)\}$ I am pretty sure that the problem look liked this. How do you describe this set? By list? By wording?
-5
votes
0answers
24 views

Function, onto, one to one [on hold]

$S=\{0,2,4,6\}, T=\{1,3,5,7\}$ $\{(0,5),(2,8),(4,10),(6,15)\}$ Question was to tell if it is a function or not. And if it is function, find if it is onto or one to one. $S$ is domain and $T$ is ...
4
votes
1answer
31 views

Anagram with condition on last letter

How many ways can "computer" be arranged with a vowel as last alphabet? Isn't it $7! \times 3 $? since there are 3 vowels. $3$ (e,o,u) $ \times 7!$(number of arrangement without one of vowel). ...
0
votes
2answers
46 views

How many 2 digit even numbers can be formed from these numbers?

How many even 2 digit numbers can be formed from the numbers 3,4,5,6,7? The digits cannot repeat (you can't have 44 or 66 for example). I know the answer to this is 8, because I just wrote them all ...
1
vote
2answers
28 views

More $1$s than $0$s in recursively defined set?

Let $S$ be the set of strings defined recursively by: Basis Step: $1 \in S$ Recursive Step: If $s \in S$, then $01s \in S$, $10s \in S$, $0s1 \in S$, $1s0 \in S$, $s10 \in S$, $s01 \in S$, $s1 \in ...
2
votes
1answer
17 views

Decomposition of hyper-rectangles into congruent simplices

Let $(a_1, \ldots, a_d) \in \mathbb{N}_+^d$ be positive integers and the semi-axes of the $d$-dimensional $\ell_1$-ellipse $$ E_{\bf a} := \{{\bf x} \in \mathbb{R}_{\geq 0}^d: \sum_{j=1}^d ...
1
vote
1answer
37 views

Proof Bell-Number $B(n+1)=\sum\limits_{i=0}^n\binom{n}{i}B(i)$

Let B(0) := 1 und B(n) for n$\geq$1 the counts of all sets partitions of [n]. The numbers B(n) are the Bell-numbers. For $n \geq 0$ prove that: \begin{equation} ...
1
vote
1answer
19 views

$f(n) = n^{\log(n)}$, $g(n) = log(n)^{n}$ is $f\in O(g(n))$?

$$f(n) = n^{\log(n)}$$ $$g(n) = \log(n)^n$$ $$f\in O(g(n))\text{ or }f \notin O(g(n))$$ why? I do not seem to get this one in particular For O (big O) Thanks!
-1
votes
1answer
50 views

prove $\sum \limits_{k=1}^n A(n,k){x+k-1 \choose n}=x^n$

A descent in the permutation $\sigma = a_1 \cdots a_n \in S_n$ is an index $i\in[n-1$] for which $a_i > a_{i+1}$. Let A(n, k) be the number of permutations of $[n]$ with $k-1$ descents where $n ...
0
votes
2answers
30 views

Permutations with repetition element condition

I'm trying to figure out: How many permutations (with repetition allowed) does A,B,C have for a given $k$ (the length of the permutation) if A cannot be followed by a C anywhere in the end result? ...
1
vote
1answer
41 views

Exact value of a sum involving harmonic numbers

Could somebody tell me the exact value of this series? $$ \sum_{k=1}^{\infty} (-1)^k\frac{H_k^{(5)}}{k} $$ where $$ H_k^{(n)}=\sum_{i=1}^{k}\frac{1}{i^n} $$ Thanks!
-8
votes
0answers
50 views

How to prove that one guy in all groups [on hold]

I dont know how even think about it. Anyone? thanks
2
votes
0answers
35 views

What exactly is wrong with this argument (Lucas-Penrose fallacy)

Argument "For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method." ...
0
votes
1answer
9 views

Discrete time Fourier transform on decimated signals

If I have a signal $x[n]$ and its decimated version, $y[n]=x[2n]$, is there a known expression for the DTFT of $y[n]$, $Y(\theta)$, as a function of $X(\theta)$? Thanks,
-4
votes
1answer
26 views

Discrete Structures camper problem [on hold]

If a camp has 12 cabins, what is the smallest number of campers that will guarantee that at least one cabin has more than six people? Please explain each step- I'm confused about how to do this.
-2
votes
2answers
32 views

Help with Discrete Structures proof [on hold]

I don't have any clue how to do this $\sum\limits_{i=1}^n(-1)^{i-1}i^2 = (-1)^{n-1}n(n+1)/2$ whenever n is a positive integer. Please explain each step.
0
votes
2answers
24 views

Logical Equivalences not using a truth table

I am tasked by using logical equivalences to show [q and ~(p implies q)] is tautology or a contradiction. I know that by setting up a truth table that it is false. I did a truth table and confirmed ...
1
vote
1answer
23 views

Distributing 3 white and 10 black marbles to 9 distinct boxes.

Question In how many ways can you distribute 3 white and 10 black marbles (identical) to $9$ distinct boxes? My attempt $3$ white marbles can be distributed in ${3+9-1 \choose 3}={11 \choose 3}$ ways ...
2
votes
1answer
31 views

What is the difference between Maximal and Maximum Cliques

Hardly I can not find the clear differences between Maximal and Maximum Cliques, As I think Maximal means a graph can not be extended to connect more edges , means each node is connected with all ...
5
votes
3answers
76 views

Suppose a city with Three type of coins ?!

in a city we have tree type 1 dollar, 2 dollar, 3 dollar of coins. we want to pay for a 20 dollar product. how many ways we can pay for a 20 dollar product, if the seller has no money and number of 1 ...
0
votes
3answers
31 views

Finding particular solution when solving recurrence relation

I have a question about how to find the particular solutions when trying to solve recurrence relations. For example, trying to solve $$ a_{n+2} = -4a_n + 8n2^n $$ I begin with finding the roots in ...
1
vote
1answer
36 views

Sum of the series with Stirling numbers of the first kind.

Yesterday I worked on one problem in discrete math and in the process of decision I came across this series. Try to do it with generating functions, but there is no success for me. So, what do you ...
0
votes
1answer
27 views

Which are Linear homogeneous recurrence relations

Determine which of the following are linear homogeneous recurrence relations with constant coefficients and state the degree/order of those that are. If they are not, say which property of the ...
0
votes
1answer
31 views

number of walks of length equal to the size of the edge list [on hold]

Let the graph $G$ and the non-empty list $(e_i ~| ~i \in 1, ... n)$ in $E(G)$ be given. There exists at most one walk of length $n$ in $G$ with $(e_i ~| ~i \in 1, ..., n)$ as its edge list, unless ...
0
votes
1answer
13 views

What is the formulae to draw a straight between the given ratio?

when $X_{min}=50, Y_{min}= 1.0$ when $X_{max} > 50, Y_{max}= 1.5$, where $X_{max}$ varies from $51, 52, 53, \ldots$ What is the value of $Y$ at any given point fo $X$? If $X_{min}$, $X$ & ...
4
votes
4answers
80 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers ...
1
vote
0answers
20 views

Finding the supremum and infimum of subsets of $\mathbb{R}$

For the following subsets of $\mathbb{R}$, give their supremum, maximum, infimum, and minimum, if they exist. Otherwise, indicate that they do not exist. ...
2
votes
5answers
125 views

How to prove $\sum\limits_{i=0}^n (-1)^i \binom{n}{i} \binom{n-i}{k}=0$

I would like to prove that: \begin{equation*} \sum\limits_{i=0}^n (-1)^i \binom{n}{i} \binom{n-i}{k}=0;~k\geq0 ; n\geq1. \end{equation*} Can any one help me how to do that? Thanks
-1
votes
0answers
15 views

How to prove that this system of boolean functions is functionally complete? [closed]

How to prove that this system of boolean functions is functionally complete using other systems of boolean functions. Express operators from a functionally complete set with functions from my set: ...
0
votes
1answer
16 views

Counting using modulo (discrete problem)

I am having trouble with my discrete h/w. I (kinda) understand the problem but I am stuck on how to write/format the solution. Please help! 16. a) To each integer $n$ we assign an ordered pair ...
1
vote
1answer
42 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
-4
votes
0answers
159 views

Proving that 2 intervals have the same cardinality [closed]

How can I Prove that the invervals [0, 1) and (0, 2] have the same cardinality by finding a bijection between them? And how can I Prove that the intervals (0, 1) and [0, 1] have the same cardinality ...
0
votes
3answers
57 views

Prove that if $A \mathbin{\triangle} C = B \mathbin{\triangle} C$, then $A = B$ [duplicate]

I know what I'm supposed to do. Since $A \mathbin{\triangle} C = B \mathbin{\triangle} C \Longrightarrow (A-C) \cup (C - A) = (B- C) \cup (C - B)$ Prove $A$ is a subset of $B$: Let $x$ be an ...