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

9
votes
0answers
123 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 ...
9
votes
0answers
437 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 ...
9
votes
0answers
683 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. ...
8
votes
0answers
116 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
7
votes
0answers
72 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 ...
7
votes
0answers
70 views

For what numbers is $a_{b}= b_{a}$? (Reference?)

A student recently asked me about solutions to the equation $$a_{b} = b_{a},$$ where the subscript notation $a_{b}$ denotes interpreting the digits of $a$ in base $b$. It turns out there are tons of ...
7
votes
0answers
194 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
165 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
47 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
45 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 ...
5
votes
0answers
112 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, ...
5
votes
0answers
57 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
91 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
71 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
34 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
34 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 ...
4
votes
0answers
60 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
90 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
131 views

diagonal of pseudoinverse of laplacian matrix

I have to find the diagonal of the pseudoinverse of a laplacian matrix evaluated on a directed and weighted graph. My laplacian is defined as: L = D - A where: D is a diagonal matrix; Di,i the sum ...
4
votes
0answers
111 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
35 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
44 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
81 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
63 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
254 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
9k 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
176 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
29 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 ...
3
votes
0answers
32 views

Problem on distributive lattices

I'm trying to prove the following: Show that a lattice is distributive if and only if it does not contain a sublattice isomorphic to either of the two lattices below. I was able to prove that ...
3
votes
0answers
30 views

Does every $9 \times 9$ Latin square contain a $3 \times 3$ submatrix containing each symbol in $\{1,2,\ldots,9\}$?

Q: Does every $9 \times 9$ Latin square on the symbol set $\{1,2,\ldots,9\}$ contain a $3 \times 3$ submatrix containing each symbol in $\{1,2,\ldots,9\}$? This one has $1728$ such submatrices, ...
3
votes
0answers
49 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
3
votes
0answers
100 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) ...
3
votes
0answers
37 views

For which algebras Taylor series and the Fourier series can be generalized?

I'm not a professional mathematician. The question is in the title. But most of all I'd like to know about this for quaternions algebra with non commutative multiplication. I'd like to know about ...
3
votes
0answers
77 views

A Tricky Quetiones on Creative Algorithm in Graph

an agent is works between n producer and m consumers. i'th producer, generate $s_i$ candy and j'th consumer, consumes $b_j$ candy, in this year. for each candy that sales, agent get 1 dollar payoff. ...
3
votes
0answers
23 views

What is the smallest eularian graph?

Which one is smallest eularian? I think that (1,2)-eularian. Thank you for your helps in advance.
3
votes
0answers
43 views

Verify my induction proof for Balanced Ternary expressions

In first place I apologize if you find a grammatical error, my English is not too good for now, but I'm work on it. That also goes for errors in my question (this is my first post). I encounter the ...
3
votes
0answers
93 views

Number of functions from domain to codomain

Let A and B be finite sets. Let a be the size of A. Let b be the size of B. Assume 0 < a < b. (a) How many functions are there with domain A and co-domain B? (b) How many one-to-one functions ...
3
votes
0answers
48 views

Solution of inhomogenous ODE (4th order)

Hello stackexchangers, I have an inhomogenous ODE in 4th order. This ODE is the constitutive law to describe a material by using the "Wiechert model" (p. 15) which is given by $p_0\sigma + ...
3
votes
0answers
119 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
3
votes
0answers
57 views

Simple random walk conditioning on non-return

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0=0$. Let $k$ and $j$ be two positive integers. Let $P_{k,j}$ be the probability that the walker hits the vertex ...
3
votes
0answers
46 views

A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
3
votes
0answers
41 views

Does there exist Latin square critical sets for which deleting any entry results in arbitrarily many completions?

For those familiar with Latin squares terminology, I'll get straight to the point: Q: For all $N \geq 2$, does there exists a critical set $C$ (for a Latin square of any finite order) such that ...
3
votes
0answers
37 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 ...
3
votes
0answers
35 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
30 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
46 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
90 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
238 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
107 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
126 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 ...