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

1
vote
2answers
26 views

Elementary discrete probability. Need some guidance with a rather basic problem.

There are $m$ white balls and $n$ black balls in a box. Balls are randomly drawn from the box with no return. Denote $X_1$ : number of white balls that been drawn before the first black. For $2 \leq i ...
-3
votes
3answers
45 views

rearranging the digits of 7524693 [on hold]

In the number 7524693, how many digits will be as far away from the beginning of the number if arranged in ascending order as they are in the number?
-1
votes
1answer
44 views

Bijective correspondence between $X$ and $X \cup \{a\}$ for an infinite set $X$ [on hold]

Let $X$ be an infinite set, and $a\notin X$. I need to prove that $|X \cup \{a\}| = |X|$. Preferably using bijective correspondence or Schröder–Bernstein theorem. Thank you.
0
votes
0answers
24 views

I want to prove that their is a binary representation for every base 10 number

I just want to make sure if my logic is right. let $x$ be a number that has no binary representation and let $y(n)$ be the closest binary representation we can get to $x$. $$y(n+1) = y(n) + 2^k$$ ...
2
votes
1answer
37 views

Order of statements in implication

The question is from Excercise 13 of part 1.4 in Rosen's "Discrete Mathematics and Its Applications" (5th edition): "let M(x,y) be "x has sent y an e-mail message", where the universe of discourse ...
1
vote
4answers
45 views

Discrete Maths Set Theory: Prove that $\left|(X^Y)^ Z\right|=\left|X ^{Y \times Z}\right|$.

I need to prove that $(X^Y)^ Z$ and $X ^{Y \times Z}$ are in bijective correspondence. Can anyone please help? EDIT: Chuks's version said: prove that $(X\times Y)\times Z\sim X\times(Y\times Z)$. ...
2
votes
2answers
78 views

Fill $8$ boxes with $60$ items

I have $8$ boxes and $60$ items: how many ways can I fill the boxes so that The order of the items in each box does not matter It does not matter which boxes are filled with which items. In other ...
0
votes
1answer
81 views

Permutation question in discrete mathematics. At least 1 out 3 members (P) from a total of 10 members

Im doing a question out of Discrete and Combinatorial mathematics by Grimaldi (4th Edition). I'm stuck on one of the questions and am trying to find an alternative way of doing it, that is not in the ...
0
votes
0answers
15 views

DFT of subdomain of periodic domain

$f(t_i,x_j)$ is a solution of stochastic differential equation on grid. $j=[0,N+1]$, $i=[0,\infty]$ and boundary conditions are periodic: $f(t_i,x_0) = f(t_i,x_N)$ and $f(t_i,x_{N+1}) = f(t_i,x_1)$ ...
1
vote
1answer
15 views

Recurrence Relations for Sequence Counting Hamming Weights

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero ...
3
votes
2answers
61 views

Finding how many bits of length n there are

So we are starting on the section of combinatorics in my discrete math class and our instructor gave us a simple problem to see if we understood what we learned that day. The problem consists of three ...
-1
votes
1answer
68 views

What is the inverse function of gcd? [on hold]

Let $a,x,c \in\mathbb{Z}$. If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable, then what values can $x$ take and how to find those values ?
4
votes
3answers
46 views

Discrete math - Set theory - Symmetric difference: Proof for a given number.

I can't find anything on this topic elsewhere. I'd like to know what keywords/sites I should be using to find what I'm looking for if this is to elementry of a question. (been using discrete math, set ...
-4
votes
2answers
40 views

License Plate problem [on hold]

A license plate contains 7 characters (order matters). Each character may either be an upper-case letter A–Z or a number 0–9. How many license plates. . . (a) contain the string ABC? (b) have at ...
-1
votes
1answer
99 views

Injections, Surjections, Bijections [on hold]

So i was given a question that asks me to determine whether the function is injective, bijective, or surjective. If you answer bijective than determine the functions inverse, domain, and target space. ...
1
vote
5answers
53 views

Proving that that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$

How might I prove that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$? I am not sure the best place to start other than assuming $x\in(R \setminus S)\setminus T$ and trying to ...
0
votes
0answers
21 views

Asymptotical stability of a discrete dynamical system

There is a linear time invariant discrete system, \begin{align} x_{k+1}&=\tilde{A}x_k, \end{align} where $\tilde{A}$ is a block matrix represented by \begin{align} \tilde{A}= ...
2
votes
2answers
247 views

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side?

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side? My approach: Since each side of the table seats two people, there are ...
0
votes
1answer
76 views

Find the number of flags of different types using induction

A flagpole is $n$ feet tall. On this pole we display flags of the following types: red flags that are $1$ foot tall, blue flags that are $2$ feet tall, and green flags that are $2$ feet ...
0
votes
2answers
1k views

What is the purpose of implication in discrete mathematics?

I would be obliged if you can show me an example of a truth table for implication where there is a also a real life aspect to it. (i.e., where would someone use the scenario to make F->F = T and also ...
3
votes
4answers
117 views

Proving that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even.

Here is the proof: Let $a,b \in \mathbb{Z}$. Prove that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even. When working these problems, I do try to set them up logically. My ...
0
votes
0answers
20 views

Repertoire method in solving recurrence [duplicate]

I don't know, how should I start solving this: $$a_1 = 2 \\ a_n = 2a_{n-1} +7$$ using the repertoire method. Could anyone give me an algorithm or explain, how to use this method in this case?
3
votes
1answer
468 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
0
votes
3answers
29 views

Proving $a=b \bmod 19$ is an equivalence relation

My question is: $a \equiv b \bmod {19} \iff aRb$ (prove that $R$ is an equivalence relation) Before that, I already know that equivalence relation is when $R$ is reflexive, symmetric and ...
-1
votes
0answers
69 views

Determine whether it is injective, surjective, bijective or neither injective nor surjective [on hold]

The question i was given asked (a) Determine whether it is injective, surjective, bijective or neither injective nor surjective. (b) If you answered "bijective" in part (a) determine the ...
1
vote
1answer
51 views

Inviting 4 friends out of 8 for a week such that each friend visits at least once

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once. Let's number the friends for brevity, 1 to 8. This is like asking how ...
40
votes
8answers
41k views

What is the best book for studying discrete mathematics?

As a programmer, mathematics is important basic knowledge to study some topics, especially Algorithms. Many websites, and my fellows suggest me to study Discrete Mathematics before going to ...
0
votes
0answers
29 views

Application of Havel- Hakami Theorem [on hold]

Definition :Given a sequence $d_1 \geq d_2 \geq \cdots \geq d_n$ called graphical if it is degree of a possible graph. need a proof of the question below. Question : The above sequence is graphical ...
0
votes
1answer
25 views

defining a sequence of numbers L n≥1, and prove something about it

So i was given this question just to try for practice to test our knowledge and i'm really confused on how to go about this question. How should i go about this question, i'm confused with the greek ...
-4
votes
0answers
44 views

prove that for any 2n≥2 and any \a ​1 ​​ ,…,a ​n ​​ ∈N, we have the following: [on hold]

So the question I was given goes like this we will introduce a mystery function,P:N→N. We don't know a formula for P (and we won't be able to determine one!) but we do know that P satisfies the ...
2
votes
3answers
74 views

Proving $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$ using strong induction

The question says $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$. Here is my proof by strong induction: Base case: $10\cdot0=0$. Let $k\geq 0$, and suppose that for any $m\leq k$ we have ...
1
vote
3answers
203 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
3
votes
3answers
4k views

How many distinct ways to climb stairs in 1 or 2 steps at a time?

I came across an interesting puzzle: You are climbing a stair case. It takes $n$ steps to reach to the top. Each time you can either climb $1$ or $2$ steps. In how many distinct ways can you ...
0
votes
0answers
26 views

Is there a theory for cellular automata propagating signals in straight lines?

Is there a theory explaining how a cellular automata can propagate signals in straight lines? For example, this video shows how some "signals" travel down at a diagonal, even though they are composed ...
3
votes
2answers
41 views

number of triangles determined by a rectangular grid

Suppose we are given an $m\times n$ rectangular grid of lattice points, such as $S=\{(k,l): 0\le k\le n-1,\; 0\le l\le m-1, \;k,l\in\mathbb{Z}\}$, and we want to determine the number of ...
-2
votes
1answer
19 views

Determine the number of strings that can be formed by ordering the letters given. [closed]

How many strings can be formed by ordering the letters SALESPERSONS if the four S's are consecutive?
0
votes
1answer
47 views

consider a graph of a gameboard

Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location at the ...
0
votes
0answers
28 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
1answer
43 views

Compose $(1243)$ and $(5)$

Checking my work. In either direction: $(1243)[1] = 2$ and $(5)[2] = 2$, so far we have $(1, 2,\ldots$ $(1243)[2] = 4$ and $(5)[4] = 4$, so far we have $(1, 2, 4,\ldots$ $(1243)[4] = 3$ and ...
1
vote
1answer
100 views

Minimization of a combinatorial function

The following gamma function depends on the overall sum of $x_n,x_j,x_k$ $$\gamma(X)=\sum_{x_n+x_j+x_k=X}\left [ \left ( \prod_{i=1}^{s}(x_{ni}-1)!C_i^{x_{ni}} \right )\times ...
-2
votes
0answers
40 views

What is elnekiti's triangle? (edited) [closed]

Elementary ceĺular automata shows amazing complex systems such as pascal's triangle is similar to " wolfram rule 90 " , so i looked over youtube searching for extra content and i found this video Here ...
0
votes
1answer
14 views

About cycles and the values in the range of a permutation function

Let $f = \{(x_1 y_1), (x_2 y_2), \ldots, (x_n y_n)\}$ be a permutation. A cycle of $f$ is given by $g = (1, f(1), f^2(1), f^3(1) \ldots)$. When counting permutations, we usually drop $1$ and count ...
2
votes
3answers
4k views

Proving/Disproving Product of two irrational number is irrational

I saw this question where I had to prove/disprove that: Ques. Product of two irrational number is irrational. I tried 'Proof by Contraposition'. Product of two irrational number is irrational. p ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
3answers
59 views

Generating function for a sequence

Please provide a clue on how to solve the following problem: Find a closed form for the generating function for the sequence $\{a_n\}$, where $$a_n = \frac1{(n+1)!}$$ for $n=0,1,2,\ldots$ I know ...
1
vote
3answers
484 views

Number of subsets of $\{1,2, \ldots, n\}$ containing no three consecutive integers: recurrence equation?

I'm thinking about the problem below. I know that I have to find a polynomial formula for that first, and then from that polynomial formula I can find the recurrence relation. I actually attempted ...
1
vote
0answers
17 views

Multigraphic Degree Sequences

Given a degree sequence $\{d_1,d_2,\ldots,d_n\}$, can I determine in polynomial time in $n$ whether this sequence is multigraphic AND can be realized by a connected multigraph? Looking at this ...
0
votes
0answers
17 views

Integer problem to minimize cuttings

A company has to make 4 items in the given quantities. item1 =4 item 2=2 item3=1 item 4=1 Te surfaces has to be covered in plywood.The company has got 3 ...
0
votes
0answers
31 views

Let $(12)$ and $(23)$ be cycles. Then is $(12)(23)$ a permutation?

The reason I ask this is because sometimes we talk about non-disjoint cycles, for example: $(ab)(bc) \neq (bc)(ab)$. Do we consider $(ab)(bc)$ a permutation where $f(b) = a$ and $f(b) = c$?
2
votes
3answers
594 views

Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$

I can't figure out an algebraic proof for the following identity: $$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$ Combinatorical solution: We can see that as choosing some from ...