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

41
votes
0answers
954 views

Why are asymptotically one half of the integer compositions gap-free?

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 ...
10
votes
0answers
185 views

$1^2+2^2+\cdots+24^2=70^2$ and squarily squaring the torus

The unique nontrivial solution to $1^2+2^2+\cdots+n^2=m^2$ is $(n,m)=(24,70)$. (This fact has connections to modular forms, special functions, lattices and string theory.) Martin Gardner, in the ...
9
votes
0answers
96 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
349 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
84 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 ...
8
votes
0answers
554 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
62 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
191 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
156 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
69 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
57 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
37 views

Limit of a Discrete Dynamical System, Part 2

In my previous post (i.e., Limit of a Discrete Dynamical System) the following system was considered: ...
4
votes
0answers
66 views

Local informatics Olympiad and Algorithm

I see one of recent local informatics Olympiad question. i have a trouble to solve it. any idea? hint? or solutions? thanks to all creative man. We have two function $P_1, P_2$ and input an array $n$ ...
4
votes
0answers
84 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
72 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
31 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
40 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
75 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
54 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
236 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
7k 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
165 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
197 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
24 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
39 views

Does $\theta(n)$ = $1/x$ make any sense?

So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to: $f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$ Find the correct theta notation for the ...
3
votes
0answers
108 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...
3
votes
0answers
80 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
38 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
75 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 ...
3
votes
0answers
51 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 ...
3
votes
0answers
37 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
33 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
25 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
41 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
42 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 ...
3
votes
0answers
77 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
224 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
88 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
120 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
82 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
143 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
70 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
68 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
212 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
180 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
204 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
154 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
331 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
193 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$ ...