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

18
votes
0answers
1k views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
11
votes
0answers
625 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
10
votes
0answers
177 views

A group acting on functions of functions of functions

Given a group acting on a set $X$, there is a standard way to define an action of the group on the set of functions of $X$. This can be extended to the set of functions of functions of $X$ as I show ...
7
votes
0answers
128 views

Approximating intervals and squares by increasingly dense disjoint finite sets with special properties

Apologies for the length of the question. Consider interval $I=[0,1]$. For any $n \in \mathbb{N}$ we can always find two finite sets $S_{1n} \subset I$ and $S_{2n} \subset I$ such that: a) $S_{1n}\...
7
votes
0answers
81 views

Showing that poset of set of supports of a vector space is semimodular

Let $W$ be a subspace of the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is a field of characteristic $0$. The support of a vector $v = (v_1,\ldots, v_n) \in \mathbb{K}^n$ is given by $\text{supp}(...
7
votes
0answers
245 views

Minimal “sumset basis” in the discrete linear space $F_2^n$

Let's $$ C\subseteq F^n_2, $$ $$ 2C=C+C=\{\bar\alpha+\bar\beta\ | \bar\alpha,\bar\beta\in C\}. $$ I need to find $C$ such that $2C=F_2^n$ and $|C|$ is minimal. I have found the following bounds:$$|C|\...
7
votes
0answers
197 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
7
votes
0answers
179 views

A variation on the Look and Say Sequence and some questions about it.

For information on the sequence mentioned in the title, see http://en.wikipedia.org/wiki/Look-and-say_sequence. This is an original problem. Suppose instead of "describing" the numbers in a string in ...
6
votes
0answers
227 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, \...
6
votes
0answers
60 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
6
votes
0answers
112 views

Discrete analogue of Green's theorem

Following formula concerning finite differences is in a way a discrete analogue of the fundamental theorem of calculus: $$\sum_{n=a}^b \Delta f(n) = f(b+1) - f(a) $$ We can think about the Green's ...
6
votes
0answers
14k views

Relationship Between The Z-Transform And The Laplace Transform

Below I've quoted Wikipedia's entry that relates the Z-Transform to the Laplace Transform. The part I don't understand is $z \ \stackrel{\mathrm{def}}{=}\ e^{s T}$; I thought $z$ was actually an ...
5
votes
0answers
77 views

Show that $\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$

Question: Show that $$\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$$ (Here the sum is over all non-empty subsets of the set of the $n$ smallest positive ...
5
votes
0answers
124 views

Maximal Hamming distance

Here is a combinatorial problem: let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming ...
5
votes
0answers
83 views

Decrease of entropy when iterating a random discrete function

Let $m$ be a positive integer. Let $S$ be the set of non-negative integers $x$ less than $m$, with $|S|=m$. Let $X_0$ be the discrete uniform distribution over $S$, with $P(x)=\begin{cases} 1/m & \...
4
votes
0answers
65 views

Central limit theorem for perfect matching counts

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the ...
4
votes
0answers
65 views

Is there a relationship between local prime gaps and cyclical graphs?

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial ...
4
votes
0answers
63 views

Given $S=\{0,1,2,3,4,5\}$, find the partition induced by the equivalence relation $R$

I am currently taking discrete math and have been given the following question to answer. Given $S=\{0,1,2,3,4,5\}$, find the partition induced by the equivalence relation $R$ where $R=\{(0,0),(0,4),(...
4
votes
0answers
48 views

Need a book recommendation for the Symmetric Group (Permutations)

I am looking for a textbook to read about permutations. Looking for something to cover such topics as: Representation of permutations (2-line arrays, cycles, bipartite graphs), inverses, involutions, ...
4
votes
0answers
86 views

About two combinatorial counting problems.

Here are the problems: Suppose $X$ is a set of $n$ elements, and $S_1,...,S_m$ are $m$ subsets of $X$ of average size at least $n/w$. Show that if $m\geq 2kw^k$, then there are $k$ distinct $i_1,...,...
4
votes
0answers
93 views

How to determine if these graphs are isomorphic?

I had this question on my last Discrete exam: (the missing vertex on graph G is vertex d) I did prove that the graphs were isomorphic, but my teacher said that I matched up my vertices wrong. ...
4
votes
0answers
62 views

Proving $f$ cannot be onto

If $f$ maps finite sets $A$ to $B$ and $n(A) < n(B)$, prove that $f$ cannot be onto. Proof by contradiction: If $f: A→B$ and $n(A) < n(B)$, $f$ is onto. Since, by definition of a function, $...
4
votes
0answers
156 views

Worst case in decanting puzzles (pouring water from one jug to others).

A classic puzzle is to start with $3$ jugs of nonzero integer capacity ($A \ge B \ge C$) and have some water (integer) in each jug (the initial position). The goal is to get to some final (integer) ...
4
votes
0answers
101 views

Prove that for all integers, if $a$ is even and $b$ is odd then $a^{2}+3b$ is odd.

Theorem: For all integers, if $a$ is even and $b$ is odd then $a^{2}+3b$ is odd. So far my proof is as follows: Let $a$ be any even integer Let $b$ be any odd integer By the definition of even ...
4
votes
0answers
100 views

An interesting math problem I created for an old-school RPG game.

The point of this is to try to have the best stats as possible at the beginning of the game and stay at level 1 before doing any quests. Starting group at creation menu: ...
4
votes
0answers
177 views

How to solve a non-homogeneous second-order linear difference equation with both a forward and a backward difference?

Quite a long title for this: I'm looking for the general solution of the following difference equation: $$ax_{t+1} -bx_t + x_{t-1} = c + u_t$$ where $a,b,c$ are real constants and $u_t$ is a bounded ...
4
votes
0answers
67 views

Symmetry groups of discrete functions

I'm looking for basic information about symmetry groups of discrete functions. It is difficult to search for such information, because searching for "symmetry group" gives results that refer almost ...
4
votes
0answers
48 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
4
votes
0answers
69 views

How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n} $ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any ...
4
votes
0answers
136 views

Find generating function For sequences

Can anyone out here help? The exercise says: "Find the generating function for each of the sequences below (the general term is given)" Now, the question is how do you find one for those: a) $U_n = 3$...
4
votes
0answers
103 views

Using discrete calculus to study convergence of series and sequences

From some personal investigation, I've noticed that all convergence tests for infinite series (at least, the real kind) can be rephrased in terms of the discrete derivative $∆f(x)$ of a function $f(x)$...
4
votes
0answers
113 views

How to get maximum sums from groups of numbers without exceeding a total?

This is an abstract computer code application that I'm trying to solve, but I think the following real life example kind of helps to illustrate the type of problem I'm working with. In this example, ...
4
votes
0answers
71 views

Nimber of selective compound games

Background/Definitions. Let $\alpha,\beta$ ordinal numbers. The Hessenberg sum $\alpha \# \beta$ is defined recursively as the smallest ordinal which is $>\alpha' \# \beta$ and $> \alpha \# \...
4
votes
0answers
98 views

Upper bounds on rate of q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (MRRW) which states that the rate $R(\delta)$ ...
4
votes
0answers
216 views

Convex hull of balls

The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball ...
3
votes
0answers
24 views

Proving Logical equivalence [5-26]

I have to prove a problem statement with logical equivalences but I seem to keep getting stuck. Here is the problem: $$ [(q \to p) \land \lnot p] \to (p \land q) \equiv p \lor q $$ Here is the work I ...
3
votes
0answers
47 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
3
votes
0answers
44 views

Some Trouble Understanding set theory

I'm currently in a discrete mathematics class and we've recently been discussing set theory. I feel like I have basic understanding of how to actually prove set relations when a question asks to do so....
3
votes
0answers
54 views

Properties of the Discrete Logarithm Problem

I am self-studying Hoffstein's An Introduction to Mathematical Cryptography, and this is problem 2.3 (p. 107-08). Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$ with order $r$. (a)...
3
votes
0answers
43 views

maximum edges in a planar graph without 3 and 4 cycles

What is the largest possible number of edges in a plane graph without 3-cycles and 4-cycles? I've been unsuccessfully trying to solve this problem from my book. I know that every plane graph without ...
3
votes
0answers
137 views

Random Variable: Ordered List of ints.

You are given an ordered list of integers : 1, 2, ...100. You then randomly permute (reorder) the integers. a.) Define a random variable that indicates whether or not a pair of integers in the list ...
3
votes
0answers
98 views

Minimum and maximum bound on mean of product of three pairwise uncorrelated random variables

There are three pairwise uncorrelated random variables $X, Y, Z$ $$E(X) = E(Y) = E(Z) = 0$$ $$E(X^2) = E(Y^2) = E(Z^2) = \sigma^2$$ How we could find minimum and maximum bound on $E(XYZ)$? I ...
3
votes
0answers
18 views

Within the number of different ways to order in line the letters of the word NOVATOLOGY, in how many ways G and N are not successive?

Within the number of different ways to order in line the letters of the word NOVATOLOGY, in how many ways G and N are not successive? I was thinking - let's put aside N and G. There are $\frac{8!}{3!}$...
3
votes
0answers
52 views

proof: If $k ∈ \mathbb Z,$ then $\gcd(4k − 1, 4k + 1) = 1.$

Claim: If $k \in \mathbb Z$, then $\gcd(4k − 1, 4k + 1) = 1$. Proof: First of all, $1$ divides every integer so that $1$ divides both $4k + 1$ and $4k − 1$. That is, $1$ is a common divisor of $4k + ...
3
votes
0answers
39 views

The Remainder of $\frac{2000!}{5^{397}}$ (Just Checking my theory)

The remainder of $\frac{2000!}{5^{397}}$ This is a question from my homework. The remainder of $\frac{2000!}{5^{397}}$ My answer is there is no remainder. Solution: There are 400 numbers that can ...
3
votes
0answers
84 views

List the elements in the sets

I'm getting caught up in the notation here. Not entirely sure what it is saying. My interpretation: (a,b) is an element of (the binary product) N x N then this "|" trips me up My guess: the "a" ...
3
votes
0answers
28 views

Trouble at translating natural language to propositional logic and proving conclusion from it.

Given this set of premises: Something in the forest I hadn't observed was not the dark ruler Something which had been noted means worth to be remembered Something I had seen in the forest not ...
3
votes
0answers
38 views

Prove that $2\mid x$ and $5\mid x$ if and only if $10\mid x$

I have to do it without using Fundamental Theorem of Arithmetic. Can someone check my work? Prove if $2\mid x$ and $5\mid x$, then $10\mid x$. Let $x \in \mathbb{Z}$. Suppose $2\mid x$ and $5\mid x$....
3
votes
0answers
44 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
3
votes
0answers
42 views

Multiplicative Inverse of Polynomials in Finite field

Find the multiplicative inverse of $x + 2$ in the field $\Bbb Z_5[x]/(x^2 + 2)$. I have done the following so far: \begin{align*} x^2+2 &= (x+2)(x+3) + 1\\ (x+2)(x+3) &\equiv -1 \pmod {x^2+2}...