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
19 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
34 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
1answer
23 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
29 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
43 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 ...
2
votes
1answer
35 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
15 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!
0
votes
1answer
46 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
29 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
48 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
0answers
7 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
23 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
22 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
30 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
75 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
28 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
12 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
66 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
19 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. ...
3
votes
5answers
122 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
13 views

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

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
15 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
151 views

Proving that 2 intervals have the same cardinality [on hold]

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 ...
0
votes
1answer
20 views

Gaussian elimination problem

$$x_1 + 10x_2 − 3x_3 = 8$$ $$x_1 + 10x_2 + 2x_3 = 13$$ $$x_1 + 4x_2 + 2x_3 = 7$$ when making 2nd and 3rd 1st columns 0 using Gaussian elimination, the second row second column also becomes zero, so ...
1
vote
0answers
21 views

Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
2
votes
3answers
60 views

Evaluate $7^{8^9}\mod 100$

I'm preparing myself for discrete math exam and here's one of the preparation problems: Evaluate $$7^{8^9}\mod 100$$ Here's my solution: $7^2\equiv49 \mod 100\implies (7^2)^2\equiv49^2=2401\equiv ...
-5
votes
0answers
15 views

discrete mathematics matrix relation proof [closed]

Show that if MR is the matrix representing the relation R, then M[n] R is the matrix representing the relation Rn.
-1
votes
2answers
20 views

Reflexive, Symmetric, Anti Symmetric and Transitive

I am really struggling with these concepts. I understand the basic principle, but cannot really find a situation where something is not reflexive, symmetric or transitive. (Clearly I don't understand ...
-3
votes
0answers
39 views

SimRank Example? [closed]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
1
vote
3answers
93 views

Prove $\frac{1}{n} =\frac{1}{n+1}+\frac{1}{n(n+1)}$ for all integers $n\in\Bbb Z$

I'm pretty sure that we need induction, since it's the format I had to use for previous problems similar to this (it isn't specified that it HAS to be an inductive proof, either, if there is another ...
0
votes
1answer
61 views

Proving set identities

I am attempting to work on some proofs for my math assignment, but I'll be honest in that I am really struggling to understand them. I read through the power point given by my teacher; however, even ...
0
votes
0answers
16 views

How to solve asymptotic recurrence without using Master Theorem

I am working on the following problem. Consider the function $B:\mathbb{N}\to\mathbb{R}$ defined by: $$B(n) = \begin{cases} 1 & \text{if $n\leq 2$,}\\ 3\cdot B(\lceil n/\log_2 n\rceil) + n & ...
-5
votes
1answer
75 views

Discrete math halp!? [closed]

Define the relation $\rho$ on $\mathbb{R}$ by the rule: $\forall x, y \in \mathbb{R},~ x \rho y$ if and only if $\exists n \in \mathbb{Z}$ such that $y = x + n\pi$. In other words, $x ρ y$ if and only ...
1
vote
1answer
38 views

Find new generating function, given an arbitrary generating function

In a discrete mathematics past paper, I am asked to find the generating function for the sequence $$\langle a_0, 0, a_2, 0, a_4, 0, \ldots \rangle,$$ given that $A(x)$ is the generating function for ...
5
votes
2answers
57 views

Find the generating function of this sequence

I need to find the generating function of the sequence $c_n = (a_0, a_1, a_2, \ldots)$, where: $$a_n = \begin{cases} 2^{n/2} & \text{if $n$ is even,} \\ 1 & \text{if $n$ is odd.} ...
0
votes
1answer
11 views

Maximization of a statistical property of a subset of random numbers

I have encountered a maximization problem which could be formulated as a discrete mathematics problem arising from statistics, but I don't know where to start or which techniques could be applied to ...
2
votes
1answer
33 views

Counting the functions with f(i) ≤ f(i+1) for all i=1,..,n-1

How can I determine how many functions are weakly monotone increasing from $[n]\equiv \{1,..,n\}$ to itself: $$ f:[n] \to [n] \text{ so that } f(i) \leq f(i+1) \; \forall i\in[n-1]$$ Thank you for ...
-1
votes
0answers
19 views

Stirling numbers: $S(n,k)=\sum_\limits{m=k}^n k^{n-m}S(m-1,k-1)$ [closed]

How can I show $S(n,k)=\sum_\limits{m=k}^n k^{n-m}S(m-1,k-1)$ holds for the Stirling numbers, $n\geq m \geq k \geq 2$.
0
votes
1answer
34 views

find the number of one-to-one function $[\pm n] \rightarrow [\pm n]$

the permutaion of $[\pm n]$ is a bijective (one-to-one) function $\pi:[\pm n] \rightarrow [\pm n]$ so that $\pi (-i) = -\pi(i)$ . $[\pm n]:=\{1, \dots, n-1, \dots, -n\}$. i have to find and determine ...