Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

0
votes
0answers
105 views

Question regarding contiguous forms

I read about contiguous forms in Achill Scürmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...
0
votes
1answer
1k views

How to find out the sum involving floor function [closed]

I came up with an equation while solving a question. The question is - suppose we have n numbers, from 1 up to n. How many groups of 3 numbers (repetition allowed) can be formed whose sum will be n. ...
0
votes
0answers
253 views

5 player round-robin tournaments

Is there any literature on the order structure coming from round-robin tournaments? I play games on littlegolem and the tournaments are mostly 5x5 round-robins. I noticed at the end, after sorting ...
0
votes
0answers
554 views

Decomposing max-convolution of sum of functions ?

Hello. $R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100. $R$ is a linear combination of $F_1, F_2, F_3$. Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$ where $w_1,...
0
votes
0answers
114 views

A search for optimal order ideals

At the behest of Gerhard Paseman I'll describe the problem that I alluded to in name for a partial order. Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers $\mathbb{N}$...
0
votes
0answers
295 views

Showing that Paley Graphs are Edge-Transitive

I would like to show that Paley graph are rank $3$ graphs (i.e. Vertex-Transitive, Edge-Transitive and Non-Edge-Transitive). Showing that they are vertex transitive is easy - every $x \mapsto x+k$ is ...
0
votes
0answers
181 views

Generate combinations with repeated symbols?

I would like to generate fixed size sequences contained a fixed number of repeated symbols. For example how to generate sequences of size N containing exactly p symbols of one type q symbols of ...
0
votes
0answers
236 views

Fast removal of weighted edges in a graph in a way such that all shortest paths are preserved

This problem is analogous to fast removal of the minimum number of edges in a weighted graph such that if the graph were to be drawn on paper with edge lengths linear in proportion to their weights, ...
0
votes
0answers
513 views

Proof of Upper bound of price of anarchy in local connection game

I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic ...
0
votes
0answers
251 views

12 and 13-bit balanced Gray codes

I am trying to find a transition sequence for both 12 and 13 bit balanced Gray codes. I know there are some excellent papers on the topic of deriving these sequences available on the internet, but I ...
0
votes
0answers
302 views

Estimating a multinomial sum

I have the following sum \begin{equation} \sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda} \...
0
votes
0answers
150 views

Finding the bottleneck in a chain of functions

I have a problem that involves finding a bottleneck. It appears to me to be a linear bottleneck assignment problem, but recognizing (and solving) such problems is far outside my area of expertise. If ...
0
votes
0answers
184 views

Packing Icons Onto A screen

You are trying to pack icons onto a screen that is divided into n horizontal rows of uniformly varying size. The rows narrow by a fixed ratio as one goes up the screen from the bottom. Since the icons ...
0
votes
3answers
321 views

boolean functions and averaging / counting

Hey guys, I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...
0
votes
0answers
1k views

Ignore this question [closed]

This question is a hacky way to create some tags for you to use. Move along.
0
votes
1answer
385 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
0
votes
2answers
605 views

Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by $$\frac{k}{2n-k}{2n-k \choose n}.$$ The number of Dyck paths from the ...
-1
votes
1answer
330 views

Limit involving the totient function and combination

Hi, Do you think the following limits are correct? $\displaystyle\lim_{d\to\infty}\frac{\sum\limits_{k=1}^{d} {\phi(N) \choose k} {d-1 \choose k-1}}{\phi(N)^d}=0$ $\displaystyle\lim_{N\to\infty}\...
-1
votes
1answer
445 views

cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]

Cardinal Equivalence Theorem For each boolean formula, |quantifications| = |assignments|. The set of valid quantifications has some cardinality, call that |Q(B)...
-1
votes
2answers
249 views

Selection problem in a collection of non-empty sets

Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ of non-empty subsets of $X$ with the following properties? $a\in {\cal F} \implies |a|\geq 2$, $...
-1
votes
1answer
113 views

Version of Hall's marriage theorem in arbitrary finite graphs [closed]

Let $G=(V,E)$ be a finite, simple, undirected graph such that $\bigcup E = V$ (that is, every vertex belongs to at least one edge). For $v\in V$ we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and for $S\...
-1
votes
2answers
157 views

Expected number of balls left out when choosing $n$ times from $n$ balls

I am given $n$ balls. For $n$ times, I pick one of them with uniform probability and put it back after picking it. Let $U$ be the number of balls I have never picked, so $U\in \{0,\ldots,n-1\}$. We ...
-1
votes
1answer
138 views

Chromatic number of transposition graph of permutations

For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be the set of all bijections (permutations) $\pi:[n]\to [n]$. For any set $X$ let $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. We let ...
-1
votes
1answer
291 views

Incidences of Lines / Circles in the Plane

During linear algebra class, I was explaining that given 2 equations + 2 unknowns where we expect there to be a unique solution but sometimes there can be 0 solutions or a line's worth. At some ...
-1
votes
1answer
278 views

Does anyone recognize this generating function [closed]

$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$ Reccurence formula is $a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose \...
-1
votes
1answer
102 views

Multiset to set operator [closed]

Is there an operator that transform a Multiset into a set by choosing all the distinct elements? Is there a better/more accurate way to write it than this: We denote the set $S$ by choosing the ...
-1
votes
1answer
322 views

Infinite sum and product associated with the Weierstrass elliptic function [closed]

Can anyone help me figure out how the identity below was obtained? $ \frac{1}{\sqrt{(e_1-e_3)(e_2-e_3)}} = R \prod \limits_{n=1}^{\infty} \left(1 - \frac{1}{R^{4n}} \right)^{-4}\left(1 + \frac{1}{R^{...
-1
votes
1answer
91 views

Lower bound on the distance set using incidences of points and circles

Suppose that $P$ is a set of $N$ points in the plane. Can we get a lower bound for the cardinality of the distance set $d(P)$ from the Szemerédi–Trotter theorem? Here is my try. The Szemerédi–Trotter ...
-1
votes
1answer
78 views

Existence of a graph with strong restrictions

Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that: all nodes but $v$ have full degree $k$ ($v$ having a lower ...
-1
votes
1answer
126 views

How compute combinatorial expression [closed]

How compute $\sum_{j=1}^k \binom{x}{j}\binom{k-1}{j-1}\alpha^j, \quad x, \alpha\in\mathbb{R}$
-1
votes
1answer
92 views

Discrepancy in non-homogeneous arithmetic progressions

I have a doubt, Roth's discrepancy theorem [1] says that there is a subset of arithmetic progressions $A \in [n]$ where any function $f:N\rightarrow \left \{ -1,1 \right \} $ implies $ \left | \...
-1
votes
1answer
209 views

Does the divergence of the sum of reciprocals of a set of integers imply this density statement about the set?

Suppose $A \subseteq \mathbb{N}$ is such that $\displaystyle{\sum_{n \in A} n^{-1}} = \infty$. Suppose $B \subseteq \mathbb{N}$ is infinite. Is there a set $X \subseteq [1,\infty)$ and a increasing ...
-1
votes
1answer
355 views

Number of blocks in a t-(v,k,l) design with empty intersection with a given set U [closed]

Question Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$? The answer is: $\...
-1
votes
3answers
564 views

A binomial sum expression

Does anyone know how to show the following combinatorial equality, $\sum_{i=0}^{n}\left(n-i\right)^{2}\binom{2n}{i}=n\cdot4^{n-1}$? By the way, this is not a homework problem, otherwise one would be ...
-1
votes
1answer
484 views

Name for probabilistic version of Pascal's identity and differentiation formula for binomial distribution

I'm trying to find a standard name or standard reference for two simple-to-prove relations involving binomial distributions. Define: $b(n,r,p) := \binom{n}{r}p^r(1 - p)^{n-r}$ i.e., it is the ...
-1
votes
1answer
669 views

Conjugate vertices and distinguishing properties

Motivation (added) A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$. A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by $2^...
-1
votes
1answer
98 views

Subgroup of the semidirect product of two subgroups with coprime orders [closed]

It is well known that if $\gcd (|H|,|K|)=1$ then all subgroups of $H\times K$ are of the form $H^{\prime }\times K^{\prime }$ such that $H^{\prime}$ is a subgroup of $H$ and $K^{\prime}$ is a subgroup ...
-1
votes
1answer
90 views

Chromatic Number of graph of a set of squares [closed]

We are given a set of squares in the plane with sides parallel to the x-y axes. We know that intersection of every three of them is empty. Show that we can color these squares with red, blue and ...
-1
votes
1answer
50 views

Size of smallest set in critical covering of $\omega$

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal ...
-1
votes
1answer
232 views

Order-Perserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...
-1
votes
2answers
83 views

Is there a formula that determines the size of the leafage of a graph's spanning tree? [closed]

In general terms, all the spanning trees of a graph G have the same number of leaves. Is there any formula that allows us to know the number of leaves in terms of |V| and |E| for any spanning tree of ...
-1
votes
1answer
338 views

Basketball shots and stopping rule [closed]

Moved over from StackExchange. You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can ...
-1
votes
1answer
143 views

Algorithm to find symmetric function given specialization

I have a symmetric function f(c1,c2,c3,c4,c5) which, when c1 < c2 < c3 < c4 < c5, has the form p1(c1)+p2(c2)+p3(c3)+p4(c4)+p5(c5), where the p_i's happen to be polynomials of degree <=5....
-1
votes
1answer
360 views

partition of a set

First, we see this example. Suppose we have a set of 6 elements, we can get 3 subsets of it, each of which has 2 elements, but no two sets overlap. But if our set has 5 elements, we want to get 3 ...
-1
votes
0answers
62 views

how to compute the number of possible trees in a tree graph? [on hold]

Let's suppose that I have a tree with n nodes. The root of my tree does not change in time. It is the same. However, the rest of nodes change their positions (...
-1
votes
0answers
60 views

Find bound on my tail distribution

hope you have a nice day. I try to find an (exponentially) decreasing bound on a tail distribution. Reason: I want to create and find the expected cumulative regret (and confidence bounds) for a ...
-1
votes
1answer
265 views

Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun. Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$. Is it true that, for every $n \ge 8$, there is at least one even permutation $\...
-1
votes
1answer
63 views

Transforming random variables for having good property?

For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that \begin{align} \Omega&\triangleq \{(x,y): A(x,y)=1\},\\ \Lambda&\triangleq \{x: B(x)=1\}. \end{...
-1
votes
0answers
44 views

Multiplicities of ordered pairs in pairing of two multisets

This is a repost from a question on math.stackexchange. Problem: I have two multisets, $X$ and $Y$. Each is a $k$-combination with repetition of a set $N=\{1,2,3,\dots,n\}$, where $n$ can be greater, ...
-1
votes
0answers
53 views

Is there any relationship between the Hungarian Algorithm and the Hesse Diagram method for ranking and sorting?

The Hungarian algorithm is used for the assignment problem. I would like to know whether the Hesse diagram method can be used to rank and sort as the Hungarian algorithm can.