The enumerative-combinatorics tag has no wiki summary.

**0**

votes

**0**answers

18 views

### Find the probability generating function of a GW process [migrated]

Consider a Galton-Watson process with offspring distribution
$Possion(1)$. That is, $\textbf{p}(k) = \frac{e^{-1}}{k!}$. Given this information, and that $P(z) = ...

**6**

votes

**1**answer

237 views

### A parity counting problem for subsets over finite fields

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$.
For a subset $T\subseteq {\mathbb F}_p$, define
$$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb ...

**26**

votes

**6**answers

1k views

### Combinatorial Morse functions and random permutations

This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...

**10**

votes

**0**answers

305 views

### “Special” meanders

One of the open problems in combinatorics is enumeration of meanders.
Here on MO I only could find them under the heading not-especially-famous-long-open-problems-which-anyone-can-understand.
Since ...

**10**

votes

**1**answer

646 views

### Two to the power of a triangular number: bijections

The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds ...

**8**

votes

**1**answer

105 views

### Exact enumerations from two-dimensional stat mech models

Exact enumerations corresponding to the dimer model on a hexagonal grid, the dimer model on a square grid, and the four-vertex (aka square ice) model on a square grid are known, namely: lozenge ...

**13**

votes

**1**answer

431 views

### Are the asymptotics of A003238 known?

Sequence A003238 of the OEIS counts ``rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins
1, 1, 2, 3, 5, 6, 10, 11, 16, ...
and it is ...

**1**

vote

**1**answer

117 views

### Truncated sums of symmetric polynomials; reference request for an algebraic derivation

EDIT: This is a case of being too wrapped up in a formulation
($e_j,p_i,$ and the like) to try something simple. It did not
occur to me to pull exp to the outside in the weeks I have
stared at this. ...

**12**

votes

**5**answers

879 views

### Is the following invariant of rooted trees a complete invariant?

Recall that rooted trees may be generated by starting with a trivial rooted tree (just a vertex), along with the operations of grafting a number of trees (identify their roots) and adding a new vertex ...

**5**

votes

**2**answers

204 views

### Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?

**17**

votes

**2**answers

853 views

### Is this similar to a known combinatorial identity?

(Apologies if this is too obscure.)
In joint work with Izzet Coskun we came across the following kind of combinatorial identity, but we weren't able to prove it, or to identify what kind of identity ...

**1**

vote

**2**answers

357 views

### Enumeration of labeled connected bipartite graphs given partite sets

What would be the closed-form expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n - m $?

**0**

votes

**2**answers

286 views

### Morse matching with 0-cells and (n-1)-cells

Suppose one has a Morse matching (acyclic matching) of a poset $P$ of rank $n$ in which the only unmatched cells are 0-cells and $(n-1)$-cells, the same number $k$ of each one.
If $P$ is connected ...

**3**

votes

**2**answers

333 views

### Counting polynomials with same coefficient sum and a given value at a point

Call an univariate polynomial $f(x) = \sum_{i=0}^{n}a_{i}x^{i} \in \Bbb{Z}[x]$ symmetric if $a_{i} = a_{n-i}$ and $a_{0} = a_{n} > 0$.
For a given $\sum_{i=0}^{n}a_{i}$ and $a_{i} \geq 0$, how ...

**3**

votes

**1**answer

170 views

### bounded partitions and bounded signed partitions of integers

Define a bounded signed partition of length $m$ and of bounded height $h$ of an integer $n$ by a relation:
$$n = \pm a_{1} \pm a_{2} \pm a_{3} \pm \dots \pm a_{m}$$ where each $a_{i}$ is a integer in ...

**4**

votes

**1**answer

173 views

### Statistics on partitions equidistributed with number of even parts

Fix a positive integer $n$. For a partition $λ$ of $n$, let $e(λ)$ be the number of even parts in $λ$. Using bijections, we can show the statistic $e(λ)$ is equidistributed on the set of partitions of ...

**2**

votes

**2**answers

158 views

### Enumerating 0-1 finite boxes without null rays.

Here rays are called lines.
Call $M(a_1,a_2)$ the number for matrices of length $a_1$ and height $a_2$, made of $0$ and $1$, having neither null vector nor null co-vector. In other words any line (row ...

**22**

votes

**3**answers

1k views

### What can be proved about the Ramanujan conjecture using elementary means?

The Ramanujan conjecture states that the coefficients $\tau(n)$ in the identity
$$q\prod_{m=1}^\infty(1-q^m)^{24}=\sum_{n=1}^\infty\tau(n)q^n$$
satisfy the inequality $|\tau(n)|\leq d(n)n^{11/2}$, ...

**1**

vote

**1**answer

146 views

### Statistics on Lehmer codes

I am looking at words $\alpha_1 \ldots \alpha_n$, where $\alpha_j \in \{ 1, \ldots, j \}$. Thinking of $\alpha_j$ as a height, these words can be interpreted as left-to-right paths on the positive ...

**17**

votes

**1**answer

417 views

### Salié permutations and fair permutations

In October 2010, I published a Monthly problem that introduced the concept of a fair permutation, which is a permutation $\pi$ such that for every $i$, either $\pi(i) > i$ and $\pi^{-1}(i) > i$, ...

**10**

votes

**6**answers

640 views

### max # of words with restricted total content

This is the sort of problems in combinatorics with a rather innocent look that turn out to be quite challenging - at least for a bunch of physicists! :)
Suppose we have a multiset $\mathbf{M}$ on a ...

**4**

votes

**0**answers

157 views

### When can we determine an $f$-vector or rank-generating function from its unordered list of coefficients?

Let $f_i$ be the number of $i$-dimensional faces in a $d$-dimensional simplicial complex $\Delta $. Recall that the $f$-vector of $\Delta $ is the vector $(f_{-1},f_0,f_1,\dots ,f_d)$ where ...

**0**

votes

**1**answer

90 views

### Enumeration of quadrangulations with a boundary and simple faces.

I wish to enumerate all quadrangulations of a $2p$ gon with $n$ internal vertices. Quadrangles are required to have simple faces. Simple face means all four vertices of each quadrangle are distinct.
...

**5**

votes

**0**answers

124 views

### How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such ...