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

How many possible bit strings of length 12 is the number of 1s an integer multiple of the number of 0s?

Question:In how many possible bit strings of length 12 is the number of 1s an integer multiple of the number of 0s? Can someone please show the solution since on there is no solution on the textbook? ...
3
votes
2answers
58 views

put the following in standard form

how do I compute the following by putting it in standad form? \begin{equation} (2-2\sqrt{3i})^{20} \end{equation} what I have tried to do is use de Moivre theorem but that requires me to put it in ...
1
vote
1answer
79 views

Pigeonhole Principle and sets homework

Can someone help me with this question? I'm having trouble solving this problem. I don't know where start. Let $S$ be a set of integers with the following properties: Every element of $S$ ...
3
votes
3answers
51 views

how does $p | (a^2 + b^2)$ force $p | b^2$

I have a question that reads: if $p | a$ and $p|(a^2+b^2)$, then $p | b$. In the solution menu it reads: since $p|a$, $p|a^2$. Now $p|a^2$ and $p|(a^2+b^2)$ forces $p|b^2$. we can conclude that ...
0
votes
0answers
104 views

Prove of f^m=f^k

Prove that for any f :Jn → Jn, there exists a positive integer m such that f^m = f^k for some positive integer k < m. I'm totally stuck with the prove. Any inputs will be much appreciated. Thanks
0
votes
3answers
35 views

Combinatorics problem involving teams (Discrete math)

A company has 10 men and 18 women. A work team consists of two workers. What is the maximum number of work teams (man-man,woman-woman,man-woman) that can be formed from this group? How many different ...
0
votes
1answer
38 views

Graph theory Euler graph

let $G=(V,E)$ be an undirected graph wheres $deg (v) =p >1$ for all $v \in V$ and also $|V|=2p+1 ,$ I need to show that G and his Complement graph are Euler graphs.... $$$$ I think that i ...
0
votes
2answers
48 views

Is induction defined on natural numbers?

Whenever I use the inductive method to prove some questions, I usually start from the $n=1$ case and assume it holds for all $n$. However, is the reason why we do not consider the $n=0$ case because ...
2
votes
1answer
44 views

Solve the equation $x^2+x+9\equiv 0\pmod {63}$

Solve the equation $x^2+x+9\equiv 0\pmod {63}$ Quadratic equation $x^2+x+9=0$ can't be factorized (with integer roots). Also, $63$ is not a prime, and I have checked the method of completing the ...
0
votes
1answer
27 views

show that $q$ and $r$ are unique when $r$ is less than or equal to zero.

Given $a$ and $b$ are integers. Suppose you are given $q$ and $r$ are integers such that $b = qa + r$ and $-a < r \leq 0$ show that $q$ and $r$ are unique by using Euclidean remainder. ...
0
votes
0answers
29 views

Exploring n + abs(x)

In class we are focussing on 'Lattice Theory' at the moment. I have an assignment with instructions saying simply - "Explore the following:" followed by a list of 5 theorems. The purpose of the ...
2
votes
0answers
31 views

Equivalence relation on set $X$

Me and my friends were complaining about one of the exercises in discrete math. If there are two equivalence relations $R_1$ and $R_2$ on set $X$. Is $R_{1}\setminus R_{2}$ still an equivalence ...
0
votes
1answer
23 views

What is an isomorphic graph (geometrical interpretation)?

I've seen definitions stating that "If $G=(V,E)$ and $G'=(V',E')$ , then a mapping $\theta : V \rightarrow V'$ is an isomorphism if, for all $u,v \in V$, $uv \in E$ if and only if $\theta (u) ...
0
votes
1answer
87 views

Functions that has finite support

The support of a function is defined as $$\operatorname{supp}(f) := \{n \in\mathbb N | f(n) \neq 0\}$$ A function $f$ has finite support if $\operatorname{supp}(f)$ is a finite set. We know that the ...
3
votes
4answers
111 views

Find closed form of a sequence $2,5,11,23,…$

Find closed form of a sequence $2,5,11,23,\dots$ How to get generating function for this sequence (closed form)? Explicit form is $f(x)=2+5x+11x^2+23x^3+\cdots$ Is it possible to get to geometric ...
1
vote
1answer
38 views

Discrete Mathematics - POSETs

My task is to find out what is the lowest # of elements a partial ordered set can have with the following characteristics. If such a set exists I should show it and if it doesn't I must prove it. 1) ...
1
vote
1answer
30 views

Robinia Leaf Problem

Someone may know the children's game with a robinia leaf. The leaves are pinnate with 7–21 oval leaflets and the game works like the following: Ever player picks a leaflet, which is then marked by ...
0
votes
0answers
74 views

Which of the following first order formulae is logically valid?

Which of the following first order formulae is logically valid? Here $α(x)$ is a first order formula with $x$ as a free variable, and $β$ is a first order formula with no free variable. $[β → ...
1
vote
1answer
33 views

Recurrence relations and eliminating the complex numbers

I want to solve the following recurrence relation, But I can't get rid of the complex numbers appearing. $a_n - 2a_{n-1} + 2a_{n-2} = 0, a_0 =1, a_1 = 2$ First, I let $a_n = cr^n$, then I find ...
0
votes
1answer
43 views

Prove : Independent set plus covering number is equivalent to number of vertices in a graph

What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes? AFAIK : In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which ...
0
votes
1answer
39 views

Depth first search tree in an undirected graph $G$.

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$. which one of the following ...
1
vote
1answer
36 views

Solving a recurrence relation without the characteristic equations

I am new to solving recurrence relations and I am presented with the following two problems (1) $$a_n = (3n-1)a_{n-1}, a_0 = 3$$ and (2) $$a_{n+3}-6a_{n+2} + 11a_{n+1}-6a_{n} = 0, a_0 =1, a_1 =1, ...
1
vote
0answers
24 views

Is my binary search tree correct?

I must construct a binary search tree for the predefined identifiers in the order of ORD, CHR, WRITE, SEEK, PRED, EOF, WRITELN, BOOLEAN, PAGE, GET, TRUE, COPY, POT, ABS I am thinking I got it right ...
1
vote
1answer
23 views

Proving path length, transitive closure

Set A is finite with n elements. Suppose a and b are elements of a set A with a != b. Let R be a relation on the set A so that there is a path from a to b of length at least 1. Show there is a path ...
-2
votes
1answer
38 views

Prove that (0,1) ⊆ R and (4,10) ⊆ R have the same cardinality [duplicate]

Hows does (0,1) and (4,10) both existing as real numbers make it have the same cardinality?
1
vote
1answer
35 views

How is this relation transitive?

$$R = \{(0,1), (0,2)\}$$ I drew out a directed graph; however, I still do not see how this relation is transitive. If $0$ was reflexive, then it is transitive; however, that is clearly not the case ...
0
votes
1answer
33 views

Is it possible to minimize this summation?

I am given the following information: $$\sum_{i=1}^{n}a_i = 1$$ $$\forall i \in n \quad a_i > 0$$ I would like to minimize the following summation: $$\sum_{i=1}^{n}a_i^2$$ I don't really know where ...
1
vote
2answers
34 views

How many 40-multisets

Consider the collection formed by the letters of the English alphabet and the numbers from 1 to 9. How many 40-multisets are there that have at most 10 letters? I am assuming this is going to be ...
0
votes
0answers
49 views

Cardinality of set of graphs with k indistinguishable edges and n distinguishable vertices

What is the cardinality of the set of simple, connected graphs with k indistinguishable edges and n distinguishable vertices. I've looked at this problem which is very similar, but not the same. ...
2
votes
1answer
40 views

Confused about multinomials. Can we write $\binom{n}{a,b,c}=\binom{n}{a}\binom{n-a}{b}\binom{n-a-b}{c}$ if $a+b+c \le n$?

Can we write $\binom{n}{a,b,c}=\binom{n}{a}\binom{n-a}{b}\binom{n-a-b}{c}$ if $a+b+c \le n$? The definition for multinomial says $a+b+c=n$ must hold or else $\binom{n}{a,b,c}=0$. I found that if ...
0
votes
0answers
45 views

Finding the closed-form answer to a counting problem - polynomial result

A monic monomial of degree $m$ in $k$-many variables is considered the same as another monic monomial obtained by changing the order of the factors. For example, if $m = 4$ using variables $x, y$ and ...
1
vote
1answer
31 views

Is every nonogram an erased version of a slightly fuller nonogram?

Say we have an $N\times M$ binary nonogram, where the $i^{th}$ row has to sum to $n_i$, and the $i^{th}$ column has to sum to $m_i,$ so that we have constraints $(n_1,\dots,n_N)$ for rows and ...
0
votes
3answers
59 views

If $g \circ f$ is one-to-one, is $g$ one-to-one?

Let $f:X\to Y, g:Y \to Z$ be functions. I'm trying to prove that if $g \circ f$ is 1-1, then is $g$ 1-1? Well the definition of a one-to-one (injective) function is that if $f:X \to Y$ is a ...
1
vote
0answers
55 views

Graph Theory: Are Infinite Trees Planar?

Graph theory: Are infinite trees planar? I think countable trees are, but not uncountably infinite trees, apparently. How does one construct such a tree?
0
votes
1answer
30 views

Cartesian product of a set containing all real numbers?

Let S be the set of all sequences of real numbers. Let R be the relation $R = \{(a, b) \in S \times S | a_3 = b_3\}$ I'm trying to find out whether R satisfies the properties reflexive, ...
0
votes
1answer
70 views

The Erdős-Szekeres Theorem [duplicate]

What is the best way to prove that the theorem is tight? In other words, how do I find a sequence of length $ n^{2} + 1 $ that does not contain any non-decreasing or non-increasing sub-sequence of ...
0
votes
3answers
40 views

Consider $f : \mathbb{N} → \mathbb{Z}$ defined as $f (n) = \frac{(−1)^n (2n−1)+1}{4}$. Find its inverse.

I cannot find an inverse of this function for $f(n) = x$, where $x$ is an integer, that gives out a natural number. Some guidance would be very helpful... I already know the function is bijective so ...
1
vote
1answer
37 views

System of congruence relations

Solve the system of congruence relations: $2x+3y\equiv 1\pmod {11}$ $x+4y\equiv 4\pmod {11}$ Could someone give a hint how to solve this system. I know that Chinese remainder theorem can't be used ...
0
votes
1answer
27 views

Do I have to know $f$ is injective?

Given: $h: A \to A$ $g: A \to A$ If $f\circ h = f \circ g$ and $f$ is injective and I want to prove that $g = h$, why do I need to know that $f$ is injective? It doesn't matter right?
0
votes
2answers
31 views

Proving 1 function is injective

Given: $f: A \to B$ $h: B \to B$ $g: A \to A$ $g$ and $h$ are injective and onto. If $h\circ f\circ g$ is injective, how should I go around proving that $f$ is injective? I succeeded the opposite ...
0
votes
1answer
69 views

Graph theory undirected graph problem

Let $G=(V,E)$ be an undirected graph , $|V|=n \ge 3$, n is Even. and $deg(v)\ge (n-1)/2$ $$$$ i need to show that G is an Hamilton graph... im here with about 5 other students... and no one has any ...
1
vote
1answer
67 views

Best of seven series in ping pong. Finding probability.

You are playing ping pong with a friend and your chance to win any point is $P$. This is a world series. Find the probability that you score 4 points before your friend has a score of 4. Evaluate ...
1
vote
1answer
60 views

Prove that $(0,1) \subseteq\mathbb R$ and $(4,10) \subseteq\mathbb R$ have the same cardinality.

I've looked at a few examples on here of how cardinality works and I'm still struggling. This is the problem that I'm currently struggling with. I know there needs to be a bijection function. I'm just ...
0
votes
1answer
25 views

How many ways are there to appoint 6 diplomats ten adorian and fifteen tellartie diplomats are available for a treaty delegation.

the question :10 Adorian and 15 Tellarite diplomats are available for a treaty delegation. How many ways are there to appoint six diplomats to the delegation if there must be the same number of ...
0
votes
0answers
62 views

Hat Check Random Variable Experiment

$\varepsilon$ is the hat check experiment with n = 4 hats.Let X count the number who do not get their own hat and let Z be the indicator of the event A={ neither peron 1 nor person 3 gets their own ...
1
vote
0answers
30 views

Generating functions and integer partitioning [duplicate]

Show that the number of partitions of a positive integer n where no summand appears more than twice is equal to the number of partitions of n where no summand is divisible by 3 So I begin by ...
0
votes
1answer
25 views

Proving 3 functions combined are injective

Given: $f: A \to B$ $h: B \to B$ $g: A \to A$ $g$ and $h$ are injective and onto. If $f$ is injective, how should I go around proving that $h\circ f\circ g$ is injective?
1
vote
2answers
38 views

IRV failing monotonicity criterion

I am looking for the simplest possible example of instant runoff voting failing the monotonicity criterion. By “simplest possible” I mean the scenario with the fewest number of candidates $(3)$ and ...
0
votes
1answer
136 views

Set of words over the alphabet $\{a,b\}$

Let $\mathcal{L}$ denote the set of words over the alphabet $\{a,b\}$ that contain exactly $k$ occurrences of $b$. Obviously, the number of words in $\mathcal{L}$ which have exactly $n$ letters is ...
0
votes
1answer
133 views

Generating function for $t$-ary tree

A $t$-ary tree is a plane rooted tree such that every node has either $t$ or $0$ succesors. A node with $t$ succesors is called internal nodes. How many leaves has a $t$-ary tree with n internal ...