Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

30
votes
0answers
664 views

On the number of complete and gap-free compositions

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
9
votes
0answers
264 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 ...
8
votes
0answers
68 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 ...
8
votes
0answers
477 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. ...
7
votes
0answers
185 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
182 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
7
votes
0answers
155 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 ...
5
votes
0answers
55 views

How can I better solve proofs requiring the introduction of algebraic assumptions?

Today I decided to binge on discrete mathematics after a three year hiatus. I tackled three proofs, and all of them required the introduction of assumptions that seemed to not be found in the givens ...
5
votes
0answers
58 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 ...
4
votes
0answers
28 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
32 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
47 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
63 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
50 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
230 views

$n$ players of paper scissor rock

Suppose there are $n$ players $(3\leq{n})$ showing Paper, Scissor or Rock simultaneously. If there is no winner then there is no payoff to any player. If there are winners and losers (e.g. $k$ ...
4
votes
0answers
6k 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 ...
4
votes
0answers
154 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 ...
4
votes
0answers
192 views

Starting my nephew out on the journey to higher mathematics.

My nephew is 8 years old and shows great promise as a student. Sadly, as most of you know most programs in secondary education don't offer any foundational courses for higher mathematics. What ...
3
votes
0answers
28 views

question in product

can any expert just check my solution You bought a car for $\$2500$ down and made payments of $\$299.50$ each month for $36$ months. (a) Find the amount of the payments over the $36$ months. (b) Find ...
3
votes
0answers
24 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
3
votes
0answers
38 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 ...
3
votes
0answers
59 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
votes
0answers
211 views

Maximum size of a bipartite subgraph on a random graph

Show that almost every $G \in \mathscr{G}(n,\frac{1}{2})$ contains no bipartite subgraph with more than $\frac{n^2}{8} + n^{\frac{3}{2}}$ edges. Tried using Markov's inequality by setting a = ...
3
votes
0answers
74 views

Product of Summations for All Subsets

We have a set $X$ of $n$ integers $\{$$x_1$, $x_2$, .. , $x_n$$\}$, for which there are $2^n$ total subsets. The summation $s$ of a subset $X'$ is simply the sum of all integers present in $X'$, ...
3
votes
0answers
114 views

to find the graphs having vertices with same eccentricity

I was reading a paper http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=plik&nIdA=11134&sTyp=HTML&nIdSesji=-1 There is a formula to calculate eccentricity in the section ...
3
votes
0answers
135 views

Number of non-decreasing functions of n boolean variables

If f(a) is greater than or equal to f(b) for two domain elements a,b in X^n {0,1} whenever the number of 1's in a is greater than or equal to the number of 1's in b, that function is called a ...
3
votes
0answers
79 views

Counting number of distinct systems

This is an enumeration problem in conjonction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
3
votes
0answers
128 views

Difference between two sets of data points

I'm making a simple calibration of a z-stage, by measuring a number of points in one direction with a constant $\Delta$Z between each sample. Then I reverse the direction and measure the same number ...
3
votes
0answers
66 views

Define composition of small cyles and making a big graph

I am having following sub graphs and wish to compose all and make a one bigger graph (say G). After that, I want to select the closed path where it is passing along the outer vertices of that ...
3
votes
0answers
63 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)$ ...
3
votes
0answers
209 views

Closed-form expression for sum of Vandermonde matrix elements

Given the Vandermonde matrix: $$\begin{pmatrix}1^0 & 1^1 & 1^2 & ... & 1^n \\ 2^0 & 2^1 & 2^2 & ... & 2^n \\ \vdots & \vdots & \vdots & \ddots & ...
3
votes
0answers
171 views

Find the number of specific permutations

Find the number of all permutations of the set $\left\{ 1,2,...,2n \right\}$ such that does not have compact subsequence: $\langle i, \ i+1\rangle$ or $\langle i+1, \ i\rangle$ for all $1\le i\le ...
3
votes
0answers
202 views

A closed-form expression for a sequence of integers

Let $(a_n)$ be the sequence of minimum values of the expression (depending on $\ell$): \begin{equation*} a_n=\arg\min \bigg\lbrace ((\ell+1)j-n)!\,(n-\ell j)!\quad \text{for}\; ...
3
votes
0answers
137 views

Really simple combinatorics question - Composition of n number strings

I'm doing a bit of revision and want to make sure I'm doing these two questions correctly. They are as follows: Two n-digit (leading zeros allowed) numbers are considered to be equivalent if one ...
3
votes
0answers
309 views

Sylvester's Theorem and Schur Theorem

I'll probably end up asking more programming questions on StackExchange forums than math questions, but I'll lead off with a math question. In my Number Theory class this past semester, I worked on a ...
3
votes
0answers
185 views

Expected value of the minimum of a random set of distances

You are given a rectangular $n_1\times n_2$ grid with one light bulb $b_i$ at every node. Each bulb is on or off with probability $p$ and $1-p$, respectively, and furthermore you know that exactly $m$ ...
3
votes
0answers
189 views

How to find $\beta$ and $\alpha$?

$\mathbb{P}$ is the prime numbers set. $p \in \mathbb{P}$ $a,b,c \in \mathbb{N}$ $n=a p^b+c$ where $c= n\bmod p$ $b$ is the highest power of $p$ who divides $n-c$ How to find $\beta$ where ...
2
votes
0answers
25 views

what does “modular” mean?

I find some similarity of the concept "modular set functions" to the cardinality function. But I don't see the cardinality function is also called "modular" or something else. I wonder what "modular" ...
2
votes
0answers
16 views

what is the significance of Eigen values of autocorrelation matrix?

I am trying to find auto correlation matrix of an image to get Harris corners.Paper I am referring suggest that if eigen values of auto correlation matrix are large the point will be corner point.so ...
2
votes
0answers
23 views

Identification of (Centers of) Cycles in a Discrete Time Dynamical System

I am studying dynamics on nonlinear Discrete Time Dynamical System of the form $$ \vec{X}_{t+1} = D(\vec{X}_t), $$ where D is some nonlinear function. I was looking for a (relatively) quick ...
2
votes
0answers
30 views

Inequality in matroid theory

Working on a proof in matroid theory I found there is a smooth map from an open set of $(\mathbb{C}^{\ast})^{(d−1)(n−d−1)}$ to a disjoint union of tori $(S^{1})^{\binom{n}{d}-n}.$ As a direct ...
2
votes
0answers
45 views

Which of the following 5 statements are true?

I am having trouble finding which of the following statements are true: Which of the following statements are true? [a] Pizza does NOT have mushrooms [b] Pizza does have mushrooms AND ...
2
votes
0answers
28 views

Computation of a 3-dimensional game matrix

For natural numbers $n_1 \leq n_2 \leq n_3$ we define $\beta(n_1,n_2,n_3)$ recursively to be the smallest natural number which is not among the numbers $\beta(m_1,m_2,m_3)$, where $m_1 \leq n_1 \leq ...
2
votes
0answers
35 views

an “alternate derivation” of Poisson summation formula and discrete Fourier transformation

Inspired by this post, I am trying to do a derivation of a Poisson summation formula. My starting point is this: $$ \frac{1}{2\pi} \int^{\infty}_{-\infty} e^{i k x} dx=\delta(k) $$ I simply wish ...
2
votes
0answers
37 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
2
votes
0answers
13 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}$ ...
2
votes
0answers
38 views

Modular arithmetic - Suggestions to begin

I've always wanted to start studying modular arithmetic to try to solve problems like: $$\text{find } n \in \mathbb{N} : 4n^2 \equiv 1 ~(\text{mod }{10^4})$$ I have a good basis in mathematical ...
2
votes
0answers
41 views

Iteratively Replacing Substrings

This problem came up while I was helping someone. Informally, we have a string of characters and a "rule" which replaces a specific string with another one, and we repeat this rule until we can no ...
2
votes
0answers
54 views

Proof of $\sum_{i=1}^{k}(2i-1) = k^2$ and some general questions

My vocabulary in math is lacking quite a lot, so please forgive me if my question is not sufficiently accurate or needlessly verbose. I tried very hard to get the latex flowing, at least that's one ...
2
votes
0answers
22 views

How would I show the relations on this set of S?

I want to show that the set below is reflexive, anti-symmetric, and transitive. Let $S$ be the set of positive integer divisors of $180$ and consider the relation $\mid$ on $S$. I understand that ...