Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
0answers
25 views

Proof of series expansion of $f(k) = {r - sk \choose n}$ in Concrete Mathematics book by D. Knuth, et. al.

Please help me prove this equation in page 190 of Concrete Mathematics 2nd Ed. book by D. Knuth: $f(k) = {r - sk \choose n} = ...
1
vote
2answers
92 views

Why relations are defined as the smallest

Often relations are defined as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
5
votes
1answer
70 views

Expressing a Recursion in terms of factorials

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = \Gamma(n+1)$$ ...
1
vote
2answers
80 views

Matrix exponential of a skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. Question 1) How do I compute ...
0
votes
1answer
37 views

Diagonalization of Skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. and we have the relation $C=UDU^{-1} ...
-1
votes
3answers
45 views

Exactly why coefficient of $x^ky^{n-k}$ is $C(k,n)$ [duplicate]

in combination when we have a binomial lattices like $(x+y)^n$ the coefficient of $x^ky^{n-k}$ is equal with $C(k,n)$ ... for example we have $(x+y)^4$ so we have this $4$ factor ...
0
votes
0answers
21 views

Stirling number of the second kind and its extension

I have a question regarding Strling's number. For starters we all know that the number of ways in which it is possible to distribute the m distinct objects in to n identical containers with no ...
0
votes
2answers
57 views

Combinatorial Proof to $\sum_{k=0}^n (-1)^k {{n}\choose{k}} = 0$

Question: Combinatorial Proof to $$\sum_{k=0}^n (-1)^k {{n}\choose{k}} = 0$$ I know that by binomial theorem we can derive this, $$0 = ((-1)+1)^n = \sum_{k=0}^n {n\choose k}(-1)^k1^{n-k} = ...
2
votes
2answers
52 views

What are $10^k \pmod 3$ and $n = \overline{a_ka_{k -1} \ldots a_1a_0}$?

I feel like I should know these concepts, but I don't.
1
vote
0answers
11 views

elementary proof for discrete Kantorovich-Rubinstein theorem?

For the Kantorovich-Rubinstein theorem, please see the wikipedia page http://en.wikipedia.org/wiki/Wasserstein_metric (which does not contain a reference for the proof). I am only interested in the ...
4
votes
3answers
55 views

When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$?

Question: When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$? Attempt: $$1XX\\ X1X\\ XX1$$ The count of $1$ for the types above are, $${{3}\choose{1}}*9*9$$ ...
0
votes
1answer
32 views

Question about proving division

Suppose $m = a_k + a_{k -1} + \ldots + a_1 + a_0$. Does $3$ divide $m$? If so, how do we prove that? We know that $3|m \to 3j = a_k + a_{k -1} + \ldots + a_1 + a_0$ for some $j \in \mathbb Z$. ...
0
votes
2answers
37 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple ...
0
votes
1answer
65 views

Combination Problem with Sofa [closed]

Suppose we have 5 sofa on room A. in this room, 4 students seated on these sofa. These Strudents go to another room for eating dinner, and after that come back to room A. how many way the students can ...
3
votes
4answers
84 views

Book/Article recommendation

I am a first year Math major in the university, this summer I want to self study and go over some specific subjects. Firstly, can someone can give a suggestion for a detailed book/article about the ...
1
vote
2answers
78 views

Must the centralizer of a non-identity element of a group be abelian?

Q1: Must the centralizer of a non-identity element of a group be abelian? I challenge everyone by asking further about this question one step further. The definition of centralizer is: Let a be ...
1
vote
1answer
26 views

GCD proof - one way solved

Let a,b be positive integers. Prove there exist positive integers $c$, $d$ such that $cd = a$ and $\gcd(c,d) = b$ if and only if $b^2\mid a$. Proof exists $cd=a$ and $\gcd(c,d) = b \Rightarrow ...
0
votes
2answers
30 views

Ways to award first and second place to two persons out of nine

Question: In how many ways can the first and second place be awarded to two persons from among 9 people. ...
7
votes
4answers
177 views

Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$

Question:Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6\dots$, constructed by including the integer $k$ exactly $k$ times. Show that $a_n = ...
1
vote
2answers
82 views

Retrieve the initial cubic Bézier curve subdivided in two Bézier curves

I have a cubic Bezier curve subdivided to two cubic Bezier: Assuming that "t_cut" is the t value where this initial Bezier is cut: example of function subdivision(BezierCurve initialCurve, ...
1
vote
1answer
53 views

Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...
0
votes
2answers
75 views

how to find taxicab numbers but for squares?

Natural numbers that can be written as the sum of squares in two or more ways. The first ten numbers are 50, 65, 85, 125, 130, 145, 170, 185, 200, 205. $$ n = a^2 + b^2 = c^2 + d^2\\ a^2 − c^2 = d^2 ...
1
vote
2answers
53 views

If $a_i>o$ then $(a_1a_2\cdots a_{2^n})^{1/2^n}\leq \frac{a_1+a_2+\cdots+a_{2^n}}{2^n}$

I need help to prove this inequality, I have no idea how to proceed with the inductive step: $$a_1,a_2,\ldots,a_{2^n}>0 \Longrightarrow(a_1a_2\cdots a_{2^n})^{1/2^n}\leq ...
0
votes
0answers
30 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + β_j ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
0
votes
1answer
38 views

Combination with repition, Representation techniques.

Consider the following Question:A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernick bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are ...
1
vote
2answers
27 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
2
votes
0answers
93 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
1
vote
3answers
72 views

Prove that $17$ divides $9a + 5b$

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ ...
1
vote
1answer
31 views

Can someone explain the logic behind this step in a induction problem

There is a question in the book that I don't quite understand. Question Show that $n^2$ is smaller than $2^n$ whenever $n\ge5$. At the $k+1$ step it gets very whacked and confusing. $k+1$ ...
1
vote
1answer
39 views

Prove by Structural induction, circular permutations

Prove by Structural Induction: For a circular permutation of $n$ elements, the number of permutations is $(n-1)!$ How is this done?
0
votes
2answers
42 views

How do I reduce this induction problem at the k+1 step

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck. I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then ...
2
votes
2answers
77 views

At a party $n$ people toss their hats into a pile in a closet.$\dots$ [duplicate]

Question: At a party $n$ people toss their hats into a pile in a closet. The hats are mixed up, and each person selects one at random. What is the expected number of people who select their own hats? ...
0
votes
2answers
41 views

Let Alphabet have only one unary function of symbol f. Prove that every term must have 3K+1 symbols for some k≥0.

I believe in order to solve this question, I have to perform induction on the complexity of terms. But I'm not sure how to begin.
0
votes
2answers
22 views

Find the probability of each outcome when a biased die is rolled, if rolling a 2 or 4 is three times as likely as rolling each of the other$\dots$

Question:Find the probability of each outcome when a biased die is rolled, if rolling a $2$ or $4$ is three times as likely as rolling each of the other four numbers on the die and it is equally ...
1
vote
3answers
100 views

Discrete Mathematics Function Proof

The question is as follows : Let $f:A\rightarrow B$ be a surjective function and let $C$ be a subset of $B$. Prove $f(f^{-1}(C)) = C$. I understand what the question is asking. It's basically ...
1
vote
1answer
42 views

Number of ways distribute 12 identical action figures to 5 children

Need a little help with this problem. Use generating functions to determine the number of different ways 12 identical action figures can be given to five children so that each child receives at most ...
1
vote
1answer
35 views

Derivative of logistic loss function

I am using logistic in classification task. The task equivalents with find $\omega, b$ to minimize loss function: That means we will take derivative of L with respect to $\omega$ and $b$ (assume y ...
1
vote
1answer
41 views

How to find the Direct Discrete Laplace Transform of ${2n \choose n}$

Some time ago I developed a discrete version of the Laplace transform for the purpose of calculating sums and solve finite difference equations with constant coefficients. The notes below are a ...
0
votes
1answer
62 views

what is the coefficient of following expression

what is the co-efficient of $x^{50}$ in the expansion of $$\frac{1}{(1-x^{1.7})(1-x^{1.8})(1-x^{2.6})(1-x^{3.0})(1-x^{4.0})(1-x^{6.7})(1-x^{7.5})(1-x^{8.2})}$$ can you please explain me the logic
0
votes
2answers
25 views

Prove $n\in \mathbb{N}^+,\sum_{k = 0}^n C(n, k) = 2^n$, using $\dots$

Question: 55.) b.) Conclude that there are $C(m + n, n)$ paths from $(0, 0)$ to $(m , n)$. 57.) Prove $n\in \mathbb{N}^+,\sum_{k = 0}^n C(n, k) = 2^n$, using exercise 55. [Hint: Count the number of ...
2
votes
1answer
57 views

Prove that limits can be used for asymptotic analysis

True or false: If f(n)=$\Theta$(g(n)), then $$\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}$$ exists and is equal to some real number. I'm not sure what needs to be done to demonstrate this. I do ...
5
votes
3answers
678 views

How many of the 9000 four digit integers have four digits that are increasing?

How to find the number of distinct four digit numbers that are increasing or decreasing? The correct answer is $2{9 \choose 4} + {9 \choose 3} = 343$. How to get there?
1
vote
1answer
36 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
2
votes
1answer
18 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
1
vote
2answers
55 views

Find a closed form for the generating function for this sequence

The sequence: $0, 0, 0, 1, 1, 1, 1, 1, 1, \ldots$ The book gives the answer of $\frac{x^3}{1-x}$ but I'm not sure how to get this answer. I understand the generating function of this sequence will be ...
1
vote
2answers
26 views

Permutations and Discrete Math

can someone explain to me this permutations problem from my desicrete math textbook? Q: The board of directors of a pharmaceutical corporation has 10 members. Three members of the board of directors ...
6
votes
3answers
517 views

General Pigeonhole Principle - Coin Flips

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows: A coin is flipped three times and the outcomes recorded. So, HTT might be recorded ...
1
vote
1answer
32 views

Understanding an algorithm

I want to understand the above algorithm. My solution says that the algorithm should return $0$ if $n$ is a prime or 1. Otherwise it returns the smallest (positive) non-trivial divisor. Lets ...
1
vote
1answer
22 views

How many 4-permutations of the positive integers not exceeding 100 contain three consecutive integers in the correct order

Question:How many 4-permutations of the positive integers not exceeding $100$ contain three consecutive integers in the correct order a.) where consecutive means in the usual order of the integers ...
2
votes
1answer
49 views

Discrete Cauchy integral formula : The interior values are always convex combinations of exterior values for harmonic functions?

Let $T={\mathbb Z}^2$. For $t=(x,y)\in T$, the neighborhood $N(t)$ of $t$ is the four-point set $\lbrace x\pm 1;y\pm 1\rbrace$. A map $f:T \to {\mathbb R}$ is harmonic iff $4f(t)=\sum_{s\in ...