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

2
votes
1answer
40 views

$\mu-$recursive functions

In my book there is the following: Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or ...
2
votes
3answers
148 views

What is the maximal path of a tree?

Could anyone explain obviously what the maximal path is ? Is it necessary for a tree that has two maximal paths that share no common vertex ?
0
votes
0answers
14 views

Order of the Big-O's?

My order by their Big-O order would be: 8,5,3,1,2,7,6,4. Would this be the correct order? $f(n) = C$ where $C$ is some constant $f(n) = \log (n) $ $f(n) = n^6 $ $f(n) = n! $ $f(n) = 6^n $ $f(n) = ...
3
votes
6answers
79 views

Using induction prove $(n^3)-n$ is divisible by 3 whenever n is a positive number.

I am not sure if I am doing this right, but I have this: There exists an integer $k$. $2k =$ positive number $(2k)^3 - 2k$ [*And this is where I get lost. How does one prove this?]
0
votes
0answers
19 views

Prove that the circuit rank $= |e|-|v|+c$ , where $c$ is the number of connected components?

How to prove that for any given graph $G=(V,E)$, the circuit rank is $$|E|- |V| + C,$$ Where $C$ is the number of connected components.
1
vote
3answers
23 views

Representing a Decimal as a Fraction - 2 Methods

So I am trying to represent the number 0.71717171 · · · as a fraction and have managed to do it using algebra. I was told I was supposed to solve it using a geometric sum. Could someone guide me ...
1
vote
3answers
24 views

Determine whether the relations are symmetric, antisymmetric, or reflexive.

This exercise is given in my textbook and I am trying to solve it. Determine whether they are symmetric, antisymmetric or reflexive. $R_1=\{(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)\}$ ...
2
votes
2answers
44 views

Showing that a function is surjective (onto)?

For example : $F:\Bbb R\rightarrow\Bbb R$ defined by $F(x) = \frac{2x+1}{3}$ I let $F(x)=Y$ which gives $Y=\frac{2x+1}{3}$ then simplify and solve for $x$ , what I have at the end is ...
3
votes
2answers
98 views

How high a priority does discrete math have for people who want to become machine learning practitioners?

Machine learning seems to depend on such math fields as probability, statistics, calculus, and linear algebra. @pranav suggested discrete math would be an important prerequisite. However, someone ...
7
votes
5answers
75 views

Show that if $g \circ f$ is injective, then so is $f$.

The Problem: Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions. (a) Show that if $g \circ f$ is injective, then so is $f$. (b) If $g \circ f$ is surjective, must $g$ be surjective? ...
0
votes
1answer
30 views

Consider the recursively defined language, L2

Consider the recursively defined language, $L_2$ i) $x \cap L_2$ and $y \in L_2$ ii) if $w \in L_2$, then so is $wxw \in L_2$ Find all strings in L_2 with length less than $7$ ...
1
vote
0answers
27 views

Polya's Enumeration Theorem applied to the 'colourings' of a cycle using integers

I am trying to solve a problem about an application to Polya's Enumeration Theorem. The problem concerns the cycle group on 5 vertices, $C_5$. I found its cycle index to be $x_1^5+4x_5^1$. Thus the ...
0
votes
0answers
8 views

Combinatorial proofs with vandermond's identity [duplicate]

I am studying for my final for discrete math and I have come across a proof that I am confused on solving. I was wondering if anyone could help. I understand that it is vandermond's identity but I ...
1
vote
0answers
12 views

Deriving the Particular Solution to a Linear Discrete Dynamical System

In my lecture notes it says that for a linear dynamical system of the form $ f(x) = Ax $ where A is diagonalisable d x d matrix, with $ \left \{ v_1 , v_2, \cdots , v_d \right \} $ a basis for $ ...
3
votes
0answers
31 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
1
vote
0answers
40 views

Set $X$ has $n$ elements, and set $Y$ has $m$ elements. Prove by induction that $X$ into $Y$ has $n^m$ elements.

I found this problem in a discrete mathematics textbook but there is no solutions provided for me to see how it was done. I started by making the inductive hypothesis, assume $n^m$ is true. The base ...
2
votes
1answer
38 views

RSA cryptography?

I understand how RSA cryptosystem works; however, I am not sure how to apply it to answer these questions. Can someone explain please? Let $N=3869$ and be equal to the product of two distinct, ...
0
votes
1answer
34 views

Discrete math, Showing a recursive equation as equivalent to a non recursive equation.

I'm having trouble with this: Show that this recursive function: $L(n) = \{0 : n = 1\ ,\ \lfloor(L(n/2))\rfloor +1 : n \gt 1\}$ is equivalent to this non-recursive equation: $L(n) = ...
0
votes
2answers
53 views

Truth table- what is the value of the statement?

$(p \lor q)\rightarrow (p \land q)$ this is the statement. I know how to build the truth table from this but what does it mean when both p and q are false, what is the value of the statement?
-1
votes
0answers
12 views

How to test if a tree fit in existed hypothesis?

Saying I have some data, and I build a tree based on the data. Now I want to test if this tree fit in my predefined hypothesis statistically. How can I do it? For example, the null hypothesis is the ...
0
votes
1answer
15 views

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x)=e^{\theta x}$. Show that $E[f(X)]=exp(\lambda (e^\theta -1))$

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x)=e^{\theta x}$, where $\theta \in \mathbb{R}$ and suppose that $X ~ Po(\lambda)$ for some $\lambda >0$. Show that $E[f(X)]=exp(\lambda ...
2
votes
4answers
39 views

Suppose that $X$ is a discrete random variable taking values in $\{0,1,2,…\}$. Show that $E[X]=\sum^{\infty}_{k=0}{P(X>k)}$

Suppose that $X$ is a discrete random variable taking values in $\{0,1,2,...\}$. Show that $E[X]=\sum^{\infty}_{k=0}{P(X>k)}$ Absolutely lost. From my notes, we define $E[X]$ as follows ...
0
votes
1answer
34 views

How can I mathematically model the combinatory problem?

I have the following problem, and I would like to model it using a mathematical formula, for a purpose of optimization problem: let's say that I have two tasks $[T_1, T_2]$, and $3$ resources ...
0
votes
1answer
9 views

variation of domination numbers

I am searching a e-copy of a book T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998. It is out of print. Is it possible to ...
2
votes
1answer
12 views

W/ generating functions, How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$?

The question is: How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$? Solve this by writing down the correct generating function. I have no idea ...
1
vote
1answer
26 views

Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$?

The question: Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$? I used a modulo calculator to get that the answer for $N$ mod $4$ is $3$, and ...
0
votes
1answer
49 views

How many chain letters were sent?

On the first Sunday of 2003, Rizzo and Frenchie start a chain letter, each of them sending five letters (to ten different friends between them). Each person receiving the letter is to send copies to ...
1
vote
2answers
31 views

Irreducible polynomial Mod $2$

would the polynomial $x^5+x^3+1$ Mod $2$ be irreducible? I've tried factorizing, however, can't seem to find any factors? if it is irreducible how can i conclude this?
3
votes
2answers
52 views

Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$

I have this review question for an exam and I was hoping someone can help me solve it: Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$ this is what I have so far, not sure if it is ...
0
votes
2answers
30 views

Irreducible factorization

I fully understand the concept of irreducible factorization, however, is there a method in order to find the irreducible factors? For example if we have the polynomial $$x^{12}-1$$ in mod $2$
0
votes
0answers
19 views

I have question regarding Permutation and Combination.

A box has $12$ cards where $5$ cards are digital numbers ($4$-digits) and $7$ cards are characters ($4$ characters on each card). Choose $2$ cards from the box to construct a password. a. Is it ...
1
vote
2answers
31 views

Why is it that no bipartite graphs contain a triangle?

I know it has something to do with the vertices belonging to two differnt sets without intersection but I'm not exactly sure of a concrete explanation. Thanks in advance.
1
vote
1answer
41 views

Why does there not exist a 3 regular graph of order 5?

Because the lines of a graph don't necessarily have to be straight, I don't understand how no such graphs exist. Can anyone shed some light on why this is?
4
votes
4answers
69 views

Bound on size of subset of $\{1,2,\ldots,2n\}$ where no member is a multiple of another

Use mathematical induction given a set of n+1 positive integers, none exceeding 2n,there is at least one integer in this set that divides another integer in the set. I can't understand why when n= 1 ...
0
votes
0answers
16 views

Binary block code

I don't fully understand how i would construct binary block codes? As far as I know we have a code, say, $(5,4,3)-$code, then $5$ would represent the length, $4$ would represent the number of codes ...
1
vote
1answer
25 views

Switching lights in a matrix

I'm interested in papers and articles on the following problems (not necessarily solutions). At least is there a name to these that I can lookup ? Say that $a_{ij} \in \{-1, +1\}$ for $1 \leq i, j ...
2
votes
0answers
22 views

Petersen graph, non-planar. How homeo

Can someone explain to me how these graphs are homeomorphic?
0
votes
2answers
24 views

Analysis of Algorithms - Big O Notation Equivalences - Limits

Please see below block question from review for test. True Or False? Justify Your answers A) is 2^(n+1) = O($2^n$) B) is 2^2n = O($2^n$) C) is log($n^2$) = O(logn) D) is ...
6
votes
2answers
80 views

${n}\choose {r}$ =$ 8$ Is there any way to find such $n$ and $r$?

Let ${n} \choose {r}$ = $8$. Is there any other choice of $n$ and $r$ except $8$ and $1$, $8$ and $7$ ? In general how to check that existence is guaranteed or not?
-1
votes
1answer
48 views

show $(x+1)^p = x^p$ + 1 (mod p) [closed]

for integer number a,b and p $\neq$ 0 is a=b (mod p) $\Leftrightarrow$ a-b is by p divisible. let f=$\sum \limits_{i=0}^n a_ix^i$ , g=$\sum \limits_{i=0}^n b_ix^i$ be polynomial so that f=g (mod p) ...
-1
votes
1answer
21 views

Distributing $n$ identical item to $k$ groups, each group must have at least one item

The problem is formulated as distributing $n$ pennies to $k$ children and each child is guaranteed at least one penny. The theorem is given as $\binom{n-1}{k-1}$ but I don't understand this theorem. ...
0
votes
2answers
29 views

Converting an NFA to DFA

I am atttempting to convert an NFA into an equivalent DFA. I did it, but i am not sure if it is correct. If anyone can please take a look at let me know if it is correct or if there is something wrong ...
1
vote
1answer
15 views

Inverse function table

I am required to create a table of values (like the one above) for h-1(x). Because x is ordered, i am just wondering, would the two tables would be identical? I just feel a little insulted that's ...
3
votes
2answers
38 views

show $\sum_{k=0}^n {k \choose i} = {n+1 \choose i+1}$

show for n $\geq i \geq 1 : \sum_{k=0}^n {k \choose i} = $ ${n+1} \choose {i+1}$ i show this with induction: for n=i=1: ${1+1} \choose {1+1}$ = $2 \choose 2$ = 1 = $0 \choose 1$ + $1 \choose 1$ = ...
0
votes
2answers
45 views

symmetry vs antisymmetry

So the problem I have is to write all the properties that a relation has (reflexive, symmetric, transitive, irreflexive, antisymmetric). The problem is the congruence relation on the set of triangles. ...
0
votes
1answer
28 views

Where does the root of this tree come from?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
2answers
39 views

Solving characteristic equations…

Can someone explain to me what my teacher is doing? $x^2 - ax - b = 0$ ..? Isn;t he using the quadratic formula to solve this problem? If that's the case, then where is the $c$ at? Shouldn't he have ...
2
votes
1answer
40 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
2answers
52 views

Show $\#\{(A,B) \vert A \subseteq B \subseteq [n]\} = 3^n $

How to show that: $$ \#\{(A,B) \vert A \subseteq B \subseteq [n]\} = 3^n$$ for $n \geq 1$. That is, how can I show that there are $3^n$ pairs of subsets $(A,B)$ of a set with $n$ elements such that ...
1
vote
1answer
28 views

Discrete Math Help. Identify whether its true or false.

This is what i have for part a but not sure if this is correct. a) There is a $x$ and $y$ for all integers, that $xy = y$. b) For every $x$ is an integer, there is a $y$ for all integers, that ...