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

learn more… | top users | synonyms (1)

-2
votes
1answer
62 views

Recursion, Common Term, Combinatorics [on hold]

May we find the common term for recursive sequence? if yes that how to find the common term of recursive sequence such: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 ... in a ...
2
votes
1answer
170 views

Expected value (probability) maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like $$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$ Here $f(k,x)$ is actually a probability coming from a ...
1
vote
0answers
490 views

Maximal disjoint Hyperplanes

Given a set of $n^{r}$ points $X_{r} = \{ x_{1}, \cdots, x_{n^{r}} \}$ occupying a codim $t^{r}$ subspace in $\mathbb{R}^{n^{r}}$. Let $M_{r}$ be the set of $t^{r}$-tuples of these points.. So ...
1
vote
0answers
34 views

A specific class of $(0,1)$-matrices

Let $T_n$ be the class of $(0,1)$-matrices of order n with no row sum equal to a column sum. Is there any name or research about this kind of matrix? For any $A\in T_n$, let $S_A$ be the sum of all ...
1
vote
0answers
99 views

Probability of correlated residues

Given $N,c\in\Bbb N$, where $c\ll(\log N)^{1/b}$ for any $b>1$ is fixed, what is the probability that given $A_1,A_2,A_3\in\Bbb N$ with ...
0
votes
0answers
22 views

probability of reaching a point in a 2d grid in a certain number of steps [on hold]

I have a random walk process in a 2d grid with N steps where N is small. How can I calculate the probability that any given cell was reached in N, N-1, N-2 ... 1 steps. That is, I would like to be ...
7
votes
1answer
575 views

Counting subspaces

We are given the finite vector space $V = V(n,p) = \mathbb{F}_p^n$ and two fixed subspaces $W_1, W_2 \subseteq V$ of dimensions $m_1$, $m_2$ respectively. Suppose that the dimension of $W_1 \cap W_2$ ...
3
votes
0answers
36 views

Asymptotics of a Bivariate Generating Function

I have the following generating function, $$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$ and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ ...
2
votes
0answers
78 views

Permutation equivalence classes with kendall-tau distance

I asked this question on Stack Exchange a few days ago with no help. I am not sure if the question seems too trivial or of not enough general interest to get any attention. Anyway, any sort of ...
1
vote
2answers
112 views

How do powers affect asymptotics in generating functions?

Let $a_n$ be a sequence of non-negative real numbers, and $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ its exponential generating function. Also, suppose $B(x) = \sum_{n=0}^{\infty} b_n ...
0
votes
1answer
85 views

Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...
4
votes
1answer
123 views

Number of bases of a matroid

I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.
4
votes
1answer
346 views

Is the face poset a Heyting algebra?

Is the face poset of a simplicial or nice enough cellular complex a Heyting algebra in some natural way? Edited to add: For the benefit of illustration, here's a few face posets: the boundary of a ...
11
votes
1answer
210 views

Complexity of planar scissor congruence

Two (not necessarily convex) poygons of equal area are scissor-congruent, i.e. both can be cut along a finite number of straight lines or segments into isometric pieces. What can be said about the ...
3
votes
0answers
101 views

How many different sums of parts of a vector

I hope this question isn't too basic for MO. I also asked it on math.se previously. This mathematical puzzle was given to me by a friend a while ago and I can't work out how to solve it. Does anyone ...
0
votes
0answers
62 views

Showing that a sequence of random variables with increasing expected value converges to a Poisson random variable

Consider a sequence $\{X_n\}_{n \geq 1}$ of nonnegative, integer-valued random variables. For any random variable $Y$ and $k \geq 1$, let $(Y)_k = Y(Y-1)(Y-2)\dots(Y-k+1)$ be the $k^\mathrm{th}$ ...
1
vote
1answer
336 views

Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected. The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...
14
votes
0answers
207 views

An algebraic strengthening of the Saturation Conjecture

The Saturation Conjecture (proved by Knutson-Tao) asserts that $c_{n\mu,n\nu}^{n\lambda}\neq 0\Rightarrow c_{\mu,\nu}^{\lambda} \neq 0$, where $c$ denotes a Littlewood-Richardson coefficient and $n$ ...
14
votes
0answers
143 views

Minimal number of intersections in a convex $n$-gon?

For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
0
votes
0answers
62 views

A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...
2
votes
1answer
115 views

Is the top interval of a finite distributive lattice an hypercube lattice?

Let $(L,\wedge,\vee)$ be a finite distributive lattice. Let $M$ be the (unique) maximum element. An element $a \in L$ is called maximal if $a \le a' < M$ implies $a = a'$. Let $b = ...
1
vote
0answers
24 views

What is the minimum number of filled cells in a partial Latin rectangle with autotopism group $\cong C_2$ and autoparatopism group $\cong S_3$?

Definitions: a partial Latin rectangle is an $r \times s$ matrix containing symbols from $[n] \cup \{\cdot\}$ such that each row and each column contains at most one copy of any symbol in $[n]$. The ...
1
vote
0answers
170 views

system with solutions $\{x-a:0\leqslant a\leqslant z-1\}$ [closed]

What must be $F$ there where $0=F(1,x,0)=F(x-0,x,z)=F(x-1,x,z)=F(x-2,x,z)=F(x-3,x,z)=$ $\dots$ $=f(x-z-1,x,z)=0$? Define $F$ in the domain where a continuous function exists that behaves so for ...
2
votes
0answers
52 views

A question on the behavior of intersections of certain block design

Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that: $\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$. $\forall i \neq j \in [m]$, $|S_i \cap S_j| ...
2
votes
1answer
190 views

Existence of functions on finite sets with specific propertise

Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, ...
23
votes
5answers
1k views

Integers in a triangle, and differences

I read about the following puzzle thirty-five years ago or so, and I still do not know the answer. One gives an integer $n\ge1$ and asks to place the integers $1,2,\ldots,N=\frac{n(n+1)}{2}$ in a ...
54
votes
9answers
3k views

What are some examples of interesting uses of the theory of combinatorial species?

This is a question I've asked myself a couple of times before, but its appearance on MO is somewhat motivated by this thread, and sigfpe's comment to Pete Clark's answer. I've often heard it claimed ...
12
votes
2answers
403 views

Number of nonzero terms in polynomial expansion (lower bounds)

Let $f(x) = a_1x^{z_1} + a_2x^{z_2} + \cdots + a_kx^{z_k}$ be a polynomial with coefficients $(a_1, \ldots, a_k) \in \mathbb{F}_q^*$ and $z_i$ are distinct positive integers. If I need to compute the ...
0
votes
2answers
334 views

Worst case difference in rank by column-row swapping

Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns. Consider $\mathscr{M}[m^\sigma]$ to be collection of ...
6
votes
1answer
127 views

Writing the quotient of solutions of linear ODEs as the solution of a nonlinear ODE

Let $A(x)$ and $B(x)$ be solutions to homogeneous linear ODEs with polynomial coefficients, i.e., $A(x)$ satisfies $$p_KA^{(K)} + p_{K-1}A^{(K-1)} + \cdots + p_1A' + p_0A=0$$ and $B(x)$ satisfies ...
1
vote
0answers
218 views

Incidence geometry and matrices

Supposing I have a $0/1$ or $\pm1$ matrix $A$ of size $m\times n$, is there a minimum $d$ (that works for every $m\times n$ $A$) such that there exists $m$ lines $r_1,\dots,r_m$, $n$ lines ...
8
votes
1answer
580 views

Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally: Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...
1
vote
1answer
297 views

Analytic Number Theory without Pigeonhole Principle [closed]

I don't know if this is an appropriate question for this website, but I will try my luck. I am an undergraduate student, and recently I became interested in analytic number theory. When I started ...
1
vote
0answers
73 views

Efficiently counting all paths of length n in a graph with vertex visitation contraints [closed]

I have a graph G with two classes of vertices. The first class represents no resource limitation entities and can be visited an unlimited number of times in any path traversal. The second class of ...
12
votes
2answers
291 views

Asymptotics of coefficients of implicitely defined generating function

I have two integer sequences $\{a_n\}_{n=0}^\infty$ and $\{b_n\}_{n=0}^\infty$. Explicit formulas for the $a_n$ are known and their asymptotic growth is fully understood. My wish is to also understand ...
2
votes
1answer
97 views

Inducing representations from the stabilizer of a partition

For each positive integer $i$, let $A_i$ be a fixed representation of the symmetric group $S_i$. I won't tell you exactly what $A_i$ is, but let's say that I have a very explicit description of its ...
8
votes
2answers
224 views

Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$). Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges of $m$ convex sub-polygons of $P$ which ...
5
votes
1answer
141 views

Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...
1
vote
2answers
107 views

Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties: The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it). $T$ has a ...
3
votes
2answers
930 views

Polya's theory of counting and commutative algebra

Do you know if there exist algebraic studies of the ring of the power series which emerge when using the theory of Polya for enumeration of sets with certain symmetries? For instance if some ideals ...
5
votes
0answers
168 views

Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...
1
vote
0answers
147 views

Nimbers and Surreal Numbers [closed]

I have been researching Combinatorial Game Theory. One common theme is the assignment of values to games in order to classify the game as a win for a specific player. One such way is class of surreal ...
5
votes
1answer
133 views

Algorithm that generates a n-simplex that cover n-polytope?

Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?
2
votes
1answer
59 views

Images of interval edge coloring

I found out the definition of interval edge colorings, concept put by Kamalian in various papers but could not find a graph depicting an example. Where can I find pictures of explicit examples of ...
3
votes
2answers
85 views

Are there references for the properties of words formed in finite groups using L-systems? (In particular, the algae L-system.)

Let $G$ be a (finite) group, and $a, b \in G$ be any two elements. Consider the sequence defined by \begin{eqnarray*} s_0 &=& a, \\ s_1 &=& b, \text{and} \\ s_{n+2} &=& s_{n+1} ...
8
votes
1answer
196 views

Smallest strongly regular graph whose automorphism group is not vertex transitive?

I'm looking for a small strongly regular graph whose automorphism group is not vertex-transitive. This answer to a different question shows that the Chang graphs on 28 vertices are such graphs. Is ...
12
votes
1answer
433 views

Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly $$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...
2
votes
1answer
82 views

Enumerator Polynomials for Linear Anytime Codes

Let $C = \{c \in \mathbb{F}^n_2 : Hc=0\}$ be a binary linear code where $H \in \mathbb{F}^{k \times n}_2$ is a block lower-triangular matrix of full rank called the parity-check matrix of $C$. Clearly ...
12
votes
1answer
329 views

Generalized geometries

Let $S$ be a non-empty set. A geometry of type $n$ for $n\geq 1$ on $S$ (consisting of at least $n$ elements) is a set ${\mathfrak P}\subseteq {\mathcal P}(S)$ such that all members of $\mathfrak ...
9
votes
5answers
1k views

Use of everywhere divergent generating functions

Generating functions are well-known to be much useful in combinatorics. But, maybe just since I am illiteral, all the applications coming in mind deal with power series, which are not just formal, but ...