The tag has no wiki summary.

learn more… | top users | synonyms

22
votes
3answers
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}$, ...
20
votes
5answers
938 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 ...
17
votes
1answer
400 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$, ...
17
votes
2answers
828 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 ...
13
votes
1answer
374 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 ...
11
votes
5answers
874 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 ...
10
votes
6answers
637 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 ...
10
votes
0answers
202 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 ...
4
votes
2answers
177 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$?
4
votes
1answer
170 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 ...
4
votes
0answers
117 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 ...
3
votes
2answers
318 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
1answer
154 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 ...
3
votes
0answers
152 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 ...
2
votes
2answers
155 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 ...
1
vote
2answers
323 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 $?
1
vote
1answer
101 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. ...
1
vote
1answer
145 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 ...
0
votes
2answers
272 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 ...
0
votes
1answer
87 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. ...
0
votes
0answers
85 views

Enumerating certain bounded polynomials with partition type property constraints

Let $p(x) = a_{0} + a_{1}x + a_{2}x^{2} + \dots + a_{d}x^{d} + \dots + a_{2d+\alpha}x^{2d+\alpha} \in \mathbb{Z}[x]$ where $\alpha \in \{0,1\}$ with the constraints $(1)$ $0 \leq ...