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
19 views

Use control parameter to set volatility of discrete distribution

I am trying to control the volatility in a simulation, and though I finally thought of a solution after writing this complete question, I would prefer a simpler solution that does not generate too ...
0
votes
1answer
40 views

hints for this question

Given two integers N and K and asks him to count the number of positive integers i such that i*(N-i) ≤ N*K and i is less than N Input First line contains, T, the number of testcases. Each testcase ...
0
votes
2answers
121 views

Prove $x$ and $y$ in $y = x^2 + 2$ are prime only for $x = 3$ and $y = 11$?

Let $x$ be a positive integer and $y = x^2 + 2$. Can $x$ and $y$ be both prime? The answer is yes, since for $x = 3$ we get $y = 11$, and both numbers are prime. Prove that this is the only value of x ...
0
votes
1answer
193 views

find the recurrence relation (homework)

I'm new to recurrence relations and I'm having trouble figuring out this problem: Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so that no two ...
0
votes
1answer
30 views

Probability that at least one baby born on each day

At Brokaw Hospital, six babies were born to six different women on Monday through Thursday of a particular week. Assuming that each baby was equally likely to be born on any of the four days, what is ...
0
votes
1answer
22 views

Need help clarifying relation properties

So I am facing some issues determining the right properties for: $ xRy\;if\,\sin^2(x) + \cos^2(y) = 1 $. (On real numbers) Obviously this one is reflexive as $\sin^2(x) + \cos^2(x) = 1 $ is a basic ...
0
votes
1answer
336 views

Looking for a formula to calculate DCT/FFT frequencies when cropping a matrix/image.

Given: A is a matrix of dimensions W1 x H1 . Cropping: Few rows and/or few columns were deleted from matrix A. We got matrix B of dimensions W2 x H2. Not more than 5% of matrix A rows/columns ...
0
votes
1answer
21 views

Proving claims about sequences by induction?

I am learning how to prove claims about finite sequences right now. Can you help me prove or disprove the following claim? ...
0
votes
1answer
219 views

Arrangements of all the letters in the word “rearrangement” with the r's being adjacent

If an arrangement of all the letters in the word "rearrangement" is chosen at random, what is the probability that all the r's are adjacent? Can someone give me a hint?
0
votes
1answer
33 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
0
votes
3answers
169 views

Primitive element modulo prime p

Let p be an odd prime and consider the set Z_p of integers modulo the prime p. An element g in Z_p is called a primitive element module the prime p if the element g has multiplicative order p-1 modulo ...
1
vote
1answer
68 views

Permutation + Combination

this is a question I had on my midterm, and I can't seem to be sure what the answer is and our professor did not post the solutions, therefore I cannot make sure I got it right (or wrong). How many ...
6
votes
1answer
822 views

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people?

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people? Does anybody know how to solve this?
1
vote
3answers
501 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
0
votes
1answer
376 views

Counting sets - Addition principle

Theorem: If A and B are non-empty sets, and A and B are disjoint, then $$ |A \bigcup B| = |A|+|B|$$ If I have n sets and all of them are disjoint, then $ |A_1 \bigcup A_2 \bigcup...\bigcup A_n| = ...
1
vote
1answer
22 views

put numbered balls in four similar boxes of a specific capacity…

With how many ways can we put $12$ numbered balls in $4$ similar(not numbered) boxes of capacity $3$ each one? Is it maybe $3^4$ ?
0
votes
1answer
11 views

Function form understanding

I dont understand what is the function when im given this kind of form: f= {<1,1>,<2,3>,<3,2>}. I understand functions when they are given in lambda form. For example how can I find the ...
0
votes
1answer
91 views

odd - even positions,arrangent of numbers

How many arrangements of the numbers $1,2,3, \dots, 2n-1,2n$ exist such that at the even positions there are only even numbers? How many arrangements are there,such that at least at one even position ...
1
vote
1answer
82 views

put balls in boxes with specific capacities

We have $10$ numbered balls and $3$ boxes with capacities: $5$, $3$ and $2$ balls. With how many ways can we put the balls in the boxes? The boxes are distinguished. I thought that it is like that: ...
1
vote
1answer
194 views

manhattan to euclidean metric

One may define a graph on a square lattice by taking the nodes of the lattice as graph vertices and the bonds of the lattice as edges. Suppose for simplicity that the nodes have integer $(x,y)$ ...
2
votes
1answer
128 views

Can you draw the e-NFA from the following definition?

I am trying to understand the solution, because I think I got it completely wrong. I wrote we could take the initial DFA and replace the normal transitions with epsilon transition except for all ...
0
votes
1answer
47 views

Prove by Induction that: $1+nx\le (1+x)^n$?

$1+nx\le (1+x)^n$, for all real numbers $x>-1$ and integers $n\ge 2$. Can you please also explain a little of the basic step and the inductions step. Thank you in advance.
1
vote
3answers
103 views

Flip a coin 3 times. What is the probability that number of tails is odd?

We flip a fair coin (independently) three times. Define the following events: A = "the number of tails is odd" B = "the number of heads is even" What is the probability of event A and event B?
0
votes
1answer
76 views

Flipping a fair coin 3 times. T/F

We flip a fair coin (independently) three times. De fine the following two events: A = "the number of tails is odd" B = "the number of heads is even" True or false: The events A and B are independent. ...
1
vote
2answers
32 views

choice of integers,so that a condition is satisfied

With how many ways can we choose the integers $x_1,x_2, \dots , x_k$ such that the condition $1 \leq x_1<x_2< \dots <x_k \leq n$ is satisfied? Do I have to find $(y_1,y_2, ...
0
votes
2answers
53 views

Problem with multiply choice counting question

Hi I was working on this question for my exam review: Consider a multiple choice exam with 100 questions, in which for each question, four options are given to choose from. You answer each question ...
1
vote
1answer
26 views

how many different choices exist?

If we choose $k$ objects from $n$ with replacement and we don't ignore the order of the choices(e.g if we choose $3$ objects of $A,B$ with replacement,the results $AAB$ and $ABA$ are considered as ...
0
votes
3answers
187 views

How many subsets of a set $S$ of size $37$ contain $x$, but not $y$, where $x,y$ are distinct?

Let $S$ be a set of Size $37$, let $x$ and $y$ be distinct elements of $S$. How many subsets of $S$ are there that contain $x$, but do not contain $y$. Can you explain why the answer is $2^{35}$?
1
vote
4answers
60 views

arrangement of digits

With how many ways can we arrange the digits $1,2, \dots, 9$,so that $1$ precedes $2$ and $2$ precedes $3$? Also,with how many ways can we arrange these digits,so that between $1$ and $2$ there are ...
0
votes
1answer
51 views

Prove that if $n\geq1$ and $a_1, a_2, \ldots, a_n$ are any real numbers, then $|a_1 + a_2 +\ldots+ a_n| \leq |a_1|+ |a_2| +\ldots+ |a_n|$

I understand that if all values of $a$ are positive, then $|a_1 + a_2 +\ldots+ a_n| = |a_1|+ |a_2| +\ldots+ |a_n|$. I also understand that if any values of a are negative, then $|a_1 + a_2 +\ldots+ ...
0
votes
1answer
21 views

Need to get summation formula?

I have: $$ Y[k]= \frac 1N \sum_{n=0}^{N-1} exp^{j2\pi\epsilon n/N} $$ After simplification, I have to get: $$ Y[k]= \frac {\sin \pi\epsilon} {N\sin(\pi\epsilon/N)} \cdot ...
1
vote
1answer
42 views

Are every prime (except 2,3,5) divisor of some of 10^n+1?

Referring to Is it true, that every prime (except 2) can be found as a divisor of enough long series of 1-s? , I have the same question. I have the intuitive hyptohesis, that every prime can be found ...
1
vote
2answers
76 views

one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals. I know there are a lot of ways to do this but I am looking ...
0
votes
1answer
11 views

Congruent question with multiple congruence conditions?

Say if x ≡ 3 (mod 7) and y ≡ 5 (mod 7) How would I use the above given information to solve the problems below? xy ≡ 4 (mod 7) x ≡ y (mod 7) If you could explain it, that would be greatly ...
0
votes
1answer
57 views

sequences of six digits (0-9)

How many sequences of six digits(0-9) contain at least one 3, at least one 5 , and at least one 8? Can someone please give me a hint?
0
votes
1answer
44 views

Defining a bijective function from $2\mathbb{N}$ to $3\mathbb{Z}-1$?

$2\mathbb{N}=\{2n:n\in\mathbb{N}\}$ and $3\mathbb{Z}-1=\{3n-1:n\in\mathbb{Z}\}$ Work: So far, my plan is to first define a bijective function from $2\mathbb{N}$ to $\mathbb{N}$ and then define ...
0
votes
1answer
24 views

Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +…+ n(n+1) = n(n+1)(n+2)/3

The problem is :Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +....+ n(n+1) = n(n+1)(n+2)/3 I have established a base case for n=0, 0*1 = 0(0+1)(0+2)/3 = 0 I have also ...
1
vote
1answer
186 views

How to guess an explicit formula using iteration

EDIT: Adding in more information that is hopefully useful. This is part of a multi step question I'm trying to answer for my homework. First we were given a1 = -3 and a formula ak+1 = ak -1, for all ...
0
votes
3answers
58 views

Proving that function $f:[0,\infty)\rightarrow [0,\infty)$ defined by $f(x)=\frac{x^2}{1-x}$ is bijective.

I am having a bit of trouble with the algebra for proving that the function is injective. Basically I set $f(a)=f(b)$ for $a,b\in[0,\infty)$ and $a,b\neq 1$. ...
2
votes
1answer
63 views

How do I do this summation? [closed]

$$\sum_{i=0}^{N-2}\frac{(N-2)!(i+1)(i+2)(i+4)}{2(N-2-i)!N^{i+1}}$$ The answer is N.
0
votes
1answer
31 views

Statistics with discrete math

I am working on a homework problem and I think that I am doing this correctly but i am not sure. This is the question: An upper-level math class has 13 students: 4 of them are females. Two of the ...
2
votes
3answers
103 views

How many even functions are there from $\{-n, \dots,n \}$ to itself?

If $A=\{-n,-n+1, \dots, n-1,n \}$, how many functions $A \to A$ are there,that are even,so they satisfy the condition $f(-x)=f(x), \forall x \in A$? Is it maybe $(\frac{|A|}{2})^{|A|}$ ?
0
votes
1answer
21 views

how many arrays exist with specific elements?

How many $m \times n$ arrays exist with elements $0,1 \text{ or } 3$? I thought that there are $(m \cdot n)^3$ arrays,but I am not sure..Could you tell me if it is right?
0
votes
2answers
35 views

Why are there $n^m$ such functions?

A function from the set $A$ to the set $B$ is just a correspondance from each element of the set $A$ to an element of $B$.If $|A|=m$ and $|B|=n$,how many such functions exist?I saw that the solution ...
2
votes
0answers
19 views

Finding the number of relations on set S

I know the number of reflexive relations on a finite set is: $2^{n^{2}-n}$ The number of symmetric relations is: $2^{n+1 \choose 2} $ The number of antisymmetric relations: $2^{n}3^{n \choose 2}$ ...
0
votes
2answers
34 views

Proving the statement?

In the case, if the statement is true, prove it, if false, give a counterexample. $$\forall a,b \in \mathbb N^+, 3| (a^2+b^2) \implies 3 |a \land 3|b$$ How do I prove this?
1
vote
1answer
26 views

calculate the number of different lottery columns

How many different lottery columns exist(of length $13$,with $1,2 \text{ or } X \text{ at each position}$) ? I have to use this theorem: Let $k$ a natural number and $E$ the set of all different ...
0
votes
2answers
161 views

Find $f(n)$ when $n = 2^k$ where $f$ satisfies the recurrence relation $f(n) = f\left(\frac{n}{2}\right) + 1$ with $f(1) = 1$

Given: $f(1) = 1$. Answer: $$f(2) = f(1) + 1 = 1 + 1$$ $$\ldots$$ $$f(4) = f(2) + 1 = 1 + 1 + 1.$$ How do I find the value of $f(n)$ where $n$ is an odd integer? Let say $f(3) = ...
2
votes
2answers
403 views

Finding the recurrence relation for number of ways to deposit n dollars

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar bills. a) Find a recurrence relation for the number of ways to deposit n dollars in ...
5
votes
4answers
402 views

What exactly are equivalence classes

What exactly are equivalence classes? Suppose I have an equivalence relation $\sim$ on some set $X$ we denote this as $x \sim y$. The equivalence classes are then $[x] = \{y \in X : y \sim x\}$. ...