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

Confusion on in order problem with combinations

In a permutation of the set ${1, 2, . . . , n}$, a pair $i$, $j$ is out of order if $i < j$ but $i$ occurs after $j$ in the permutation. In a random permutation of the set ${1, 2, . . . , n}$ with ...
0
votes
1answer
37 views

Having trouble understanding how to disprove/prove if a formula is a function.

Is $\frac 1{x^2-2} $ a function from $\mathbb{R}\to \mathbb{R}$? Is it a function from $\mathbb{Z}\to \mathbb{R}$? I have been thinking about this but, I can't find any example for which you can have ...
0
votes
2answers
19 views

First Order Logic and equivalence rules

I have a couple of questions about first order logic equivalence rules. How do you distribute the $\neg$ correctly with the $\exists$ and $\forall$ quantifiers? If let's say I have $$\neg[\forall ...
0
votes
2answers
72 views

If Mr. X was born on April 16, 1987 what day is 2016 days after he was born?

I have a confusion about the way of solving the following mathematical problem: If Mr. X was born on April 16, 1987 what day is 2016 days after he was born? How will I solve these kind of ...
0
votes
0answers
21 views

Choose a point which minimizes the sum of distances between it and other points in set explanation

I was wondering, suppose I have a set of integers, {1, 70, 97, 98, 99, 101, 102}, what is the integer to choose such that the distance is minimised for a subset ...
0
votes
0answers
20 views

The multi-binomial theorem, prove multiples of 11

Over $\mathbb{Z_{11}}$ $ $, $ \\\\$ $f(x)= x^{11} - x $ has solutions $0, 1, 2, \cdots , 10.$ (by Wilson) $$$$ So, we can rewrite $f(x)=x(x-1)(x-2)(x-3)\cdots(x-10)$ That is $$x^{11} - x = ...
0
votes
1answer
26 views

Double counting proof of binomial problem

The assignment is to prove the following assertion using the method of double counting and explaining which pairs were counted. $$\dbinom{n+1}{k+1} = \sum_{i = k}^{n} \dbinom{i}{k}$$ Left side is ...
1
vote
2answers
29 views

The number with minimum sum of differences

Let $a_1,a_2,...,a_n\in\mathbb{R}$. I wonder how to find the number $x$ with $$|x-a_1|+...+|x-a_n|=\mbox{min}\{|a-a_1|+...+|a-a_n|\mid a\in\mathbb{R}\},$$ namely the sum of the differences with ...
2
votes
1answer
22 views

A basic combinatorics problem: number of solutions of form $ \pm 1 $ to and additive equationn

In my combinatorics and discrete mathematics class I was asked this question which I cannot seem to be able to solve: Let us define N variables $ \{ s_k \}_{k=1}^{N} $ each having two possible ...
0
votes
1answer
12 views

Treewidth Of Graphs And Chordal Completion

https://en.wikipedia.org/wiki/Treewidth The above page explains what a tree decomposition is, and states that treewidth of G is equal to the minimum clique number, minus one, of a chordal ...
-1
votes
1answer
36 views

Discrete Mathematics Stamp problem [closed]

I am very confused on how to solve. Use the Principle of Mathematical Induction to prove that every amount of postage of 18 cents or more can be formed using just 4-cent and 7-cent stamps.
8
votes
2answers
154 views

What is the subword complexity function of this infinite word?

Let $w_{0}$ denote the finite word $01$ in the free monoid $\{ 0, 1 \}^{\ast}$, and for $i \in \mathbb{N}$ define $w_{i}$ as the word obtained by adjoining the first $\left\lfloor ...
0
votes
1answer
23 views

Let $G$ be a graph with $n$ vertices. Prove that $\chi(G) \ge \frac{n}{\alpha(G)}$

$\chi$ is the chromatic number of $G$, and $\alpha$ is the independence number of $G$. I know that if $G$ has a proper coloring, then the set of vertices with a particular color is an independent ...
0
votes
1answer
44 views

Discrete Math Problem Find a formula for (1 / (1 · 2)) + (1 / (2 · 3)) + (1 / (3 · 4)) + . . . + (1 /(n(n + 1) ) [duplicate]

Find a formula for (1 / (1 · 2)) + (1 / (2 · 3)) + (1 / (3 · 4)) + . . . + (1 /(n(n + 1) ) by examining the values of this expression for small values of n, where n is a positive integer. Use ...
0
votes
3answers
20 views

Why is the Relation R4 Reflexive?

Given A = {1,2,3,4} R4 = {(1,1), (1,2), (2,2), (3,3), (4,4)}. My understanding is that in the case where if R4 was {(1,1), (2,2), (3,3), (4,4)}, then R4 would be reflexive because every element is ...
1
vote
2answers
68 views

Solve by Mathematical Induction: $2^n+1 \leq 3^n$

I'm very confused on how to prove this. By using Mathematical Induction prove that, for all positive integers $n$ the following inequality holds: $$2^n + 1 ≤ 3^n$$
0
votes
1answer
26 views

Why is the Relation R3 Transitive?

Given $A = \{1,2,3,4\}$ in the Relation $\mathcal{R} = \{(1,1),(2,2),(3,3),(4,4)\}$ I understand why $\mathcal{R}$ is Reflexive, Symmetric but why is it also transitive? In my understanding for a ...
0
votes
1answer
25 views

If $G$ is a graph with exactly one vertex of odd degree, does G have both an Eurelian trail and an Eurelian tour?

I believe the answer must be yes, because I'm having a difficult time finding a counterexample that contains only one vertex of odd degree. So I need to figure out how to prove this. All I've got so ...
0
votes
1answer
20 views

Let S be a set of k elements, where k is a whole number. Suppose n is not an element of S. Show that S union s has k + 1 elements.

Let S be a set of k elements, where $$k \in \omega$$ Suppose $$n \notin S$$Show that $$S \cup \{n\}$$ has k + 1 elements. I'm honestly last as to where I should start. I was thinking of maybe a ...
-1
votes
1answer
42 views

How to solve the recurrence $T(n) = 2T(n/3)+n$ [duplicate]

Base case of $T(1)=1$ As a part of your solution establish, a pattern for what the recurrence looks like after the $k$-th iteration Express final answer as $\Theta(n)$ $T(n) = 2T(n/3)+n $ How to ...
1
vote
2answers
43 views

Proving $1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = 2\binom{n + 2}{3}$by math induction?

I am working on a problem, but I don't know whether or not to use math induction on it. Here's the problem: Prove that for all integers $n \geq 1$, $$1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = ...
3
votes
4answers
44 views

Using a combinatorial argument

I am having some difficulty with this problem: Use a combinatorial argument to show that $$\binom{m + n}{r} = \binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r - 1} + \dots + ...
-4
votes
0answers
29 views

How can this summation equation be proved by mathematical induction? [duplicate]

How can I prove this by mathematical induction? Sorry the wording is not very spacious, but it says "for all integers n." $$\sum_{j=1}^{n}{j^3}= \left(\frac{n(n+1)}2\right)^{2} \text{ for all ...
3
votes
2answers
44 views

Proving $\sum_{i=0}^n \binom{n}{i} = 2^n$ by math induction

I am having some trouble using math induction to prove the following problem: $$\sum_{i=0}^n \binom{n}{i} = 2^n$$ Where n $\geq$ 0 I know the first thing with math induction is substitute the base ...
1
vote
1answer
61 views

$10$ people are standing in a queue when three new checkouts open. In how many ways can the three new queues be formed?

Problem: $10$ people are standing in a queue when three new checkouts open. 8 people rush to the new checkouts and the new queues end up with at least two people in each. In how many ways can ...
-1
votes
1answer
19 views

Big O notaion O(n) and logaritms [closed]

Can someone explain me the subjects Big O notation and logarithms please? I can't understand those subjects For example if I have a question like this: recall that logan is the power to which you ...
0
votes
1answer
100 views

Tennis tournament probability. Question is about part B

In your tennis club there are two other members. One of them is a very good player. His name is Roger (think Federer) and you have a 0.1 probability of winning a match against him. The other player is ...
-5
votes
3answers
96 views

Prove that $3^x$ divides $(3x)!\,\,\,\, \forall x \ge 1$ [closed]

Prove that $3^x$ divides $(3x)!\,\,\,\, \forall x \ge 1$ For example, $3$ divides $6 = 3!$
0
votes
1answer
26 views

What is the probability to pick a collection of 12 balls as above with at least 2 red balls and exactly one blue ball?

What is the probability to pick a collection of 12 balls as above with at least 2 red balls and exactly one blue ball? Here is my solution ${{12+3-1}\choose{12-2-1-1}}$ Is this correct?
0
votes
0answers
62 views

Writing a closed polynomial from a difference table

Here is a difference table for a function $S(N)$. Your job is to fill in the table, and then write out the closed polynomial expression corresponding to $S(N)$. The third level difference row is ...
1
vote
2answers
28 views

How many ways are there to pick 12 balls from large piles of (identical) red, white and blue balls?

Would the below be correct? Since there are $3$ types of balls from $12$, you would do $12$ choose $9$ and then multiply by $3$? $$\binom{12}{9} \cdot 3$$
2
votes
2answers
26 views

How many integers are multiples between a specific set?

I have a question that I have tried, but it doesn't have an answer and I can't check my work. The question is: ...
1
vote
1answer
51 views

Inverse Vectorization Vec^-1

Hope that you will find this post in good health. I am Mr.Adnan from Pakistan with research background in Control systems. I am working on one problem in which Hadamard weights are using. During ...
0
votes
1answer
11 views

Let m be a positive integer and a, b, c, and d be integers. If a = c (mod m) and b = d (mod m), then prove a∙b = c∙d (mod m).

To prove this I believe I just need to show that (cd-an)/m is an integer. Just FYI the definition I got from the book of a = c (mod m) is: m divides c - a.
0
votes
4answers
38 views

Prove that if $k\in \mathbb{N}, n=3k \rightarrow \frac{n!}{(3!)^k} \in \mathbb{N}$

Prove using a combinatoric argument that if $k\in \mathbb{N}, n=3k \rightarrow \frac{n!}{(3!)^k} \in \mathbb{N}$ $$=\frac{(3k)!}{3^k2^k}$$ Any ideas are appreciated, I'm stuck here, thanks!
0
votes
2answers
23 views

Equivalence relations on intersections

Let $R_1$ and $R_2$ be equivalence relations on a set $S$. Their intersection is on the relations considered as sets of ordered pairs. Identify the equivalence classes of the relation $R_1 \cap R_2$. ...
-5
votes
1answer
34 views

Pseudocode algorithm for the product of the first n positive integers [closed]

This is for discrete mathematics: Write a pseudocode algorithm to compute the product of the first n positive integers. How many multiplications does your algorithm perform? I tried starting off ...
0
votes
0answers
12 views

Are these linear homogenous recurrence relations?

I'm having trouble understanding the formal definition because it is a bit wordy for me. However, the way I understood it is that to be homogenous, all the terms must have the same exponent. This is ...
0
votes
1answer
30 views

Did I solve this linear homogeneous recurrence relation correctly?

I'm not sure how to enter math on this site because I'm pretty new, but I typed my solution up on word. My solutions:
0
votes
1answer
23 views

How to prove order of element $o(a^k)=m$

Let $a ∈ G$ has a order $n=mk$ where $m, k\ge 1$ prove that order of $a^k$ is $m$ My attempt: Ok, it's clear that $$(a^k)^m = a^{mk} = a^n = e$$ Thus $o(a^k)\le m$ now how do I come up ...
0
votes
1answer
38 views

How to solve this recurrence relation for a general $n$

We have a recurrence relation: $$a_n=1$$ $$a_{n-1}=x$$ $$a_{n-i}=xa_{n-i+1}-a_{n-i+2} $$ for $i=2,3,\ldots,n.$ How to find $a_0$ in terms of $x$? For a fixed $n$, I can solve it but it turns out ...
0
votes
2answers
38 views

Evaluate $2488^{2016}\equiv ?\pmod 7$ [closed]

Evaluate $2488^{2016}\equiv ?\pmod 7$. How do I solve these kind of questions ? Is that modular exponentiation or modular arithmetic ?
2
votes
3answers
50 views

How many strings of length 8

The question - how many strings of length 8, from 4 letter alphabet, using each letter twice. There is to be exactly one pair of same letters next to each other (example of valid string: AABCDBCD). I ...
2
votes
5answers
76 views

Verify that $(a^2 + b^2)(c^2 + d^2)$ = $(ac - bd)^2 + (ad + bc)^2$ for any integer $a$,$b$,$c$,$d$

Part 1 - Verify that $(a^2 + b^2)(c^2 + d^2)$ = $(ac - bd)^2 + (ad + bc)^2$ for any integer $a$,$b$,$c$,$d$ Part 2 - Write 25988 as the sum of the two squares (of integers). A bit confused with ...
1
vote
3answers
67 views

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$ So far I have: Base case (n = 1) = $8^{1} | (4(1))!$ = $8 | 24$ which is true. Induction Step: $8^{n + 1} | (4(n + ...
0
votes
1answer
21 views

evaluate the numbers from the coefficient

I need to solve this problem and I know the answer is -220 but I want to know how to find n and r in the coefficient of $x^3$ $y^9$ in the expansion of $(x-y)^{12}$. I know how to do a problems with ...
0
votes
1answer
49 views

Show that each composite function $f_i \circ f_j$ is one of the given functions

I'm just going through the problems that I got wrong on my discrete math exam, and I was not sure how to do this one. How would I go about making this chart? The chart has $f_1, \dots, f_5$ going ...
2
votes
1answer
40 views

Give a bijection

Give a bijection between the following sets: (1) $\mathbb{Z}$ and $ \mathbb{Z}\backslash \{0\}$ (2) $\mathbb{Q}$ and $ \mathbb{Q}\backslash \{0\}$ I think that I can the problems with "Hilbert's ...
0
votes
3answers
33 views

Proving that Z with the binary operation is a monoid?

Let $*$ denote the binary operation defined on the set $\Bbb Z$ of integers, where $$x * y = 3xy - 5x - 5y + 10$$ for all integers $x$ and $y$. Prove that $\Bbb Z$, with the binary ...
3
votes
1answer
65 views

Find recurrence relation

Find recurrence relation for strings of length n using 7 letter alphabet. Each character in the string is the same as previous one or the following one. The start is easy - first two characters in ...