All Questions
Tagged with enumerative-combinatorics asymptotics
13 questions
3
votes
2
answers
303
views
Asymptotics of A000613
The general linear group $GL_n(\mathbb{F}_2)$ acts on the powerset $2^{{\mathbb{F}_2}^n \setminus \{0\}}$ by multiplication: $A \cdot S := \{Ax \in {\mathbb{F}_2}^n : \, x \in S\}$, for an invertible ...
- 331
0
votes
2
answers
204
views
Asymptotic approximation of a convolution of binomial coefficients
I would like to find the following limit which is somewhat similar to the usual Vandermonde's convolution for binomial coefficients. Define $L$ as follows.
$$ L \triangleq \lim_{N\to\infty} \frac{1}{2^...
- 155
4
votes
0
answers
135
views
Permutations avoiding a family of consecutive patterns
Let $B=\{1324,14325,154326,1654327,\ldots\}$ be the set of permutation patterns of the form $1(m-1)(m-2)\cdots 2m$ for $m\geq 4$. I'm interested in the set $\mathcal P$ of permutations that avoid all ...
- 135
4
votes
0
answers
128
views
Asymptotics of holonomic recurrences and the Birkhoff-Trjitzinsky method
While reading about asymptotics of holonomic recurrences, I had the following impressions that are related to the divulgation of the theory:
I don't know what is the current status of the divulgation ...
7
votes
1
answer
2k
views
How does the number of trees on $n$ vertices *up to isomorphism* grow as $n \to \infty$?
It is well known that the number of labelled trees on $n$ vertices is equal to $n^{n-2}$.
We do not expect any such exact formula for the number of isomorphism types of trees on $n$ vertices. But ...
- 7,857
7
votes
2
answers
212
views
Estimating the number of functions which are at most $c$-to-$1$ for some constant $c \ge 2$
Notation: $[m] := \{1, 2, \dots, m \}$.
How many functions are there $f: [a] \to [b]$? The answer is easily seen to be $b^a$.
How many $1$-to-$1$ functions are there $f: [a] \to [b]$? Again the ...
- 7,857
3
votes
1
answer
197
views
Generalized Shared Birthday
Suppose a year has $d$ days. How many people should be in a room so that there are at least $2k$ people in the room with birthdays shared with each other (all could be same day or there could be $k$ ...
user94040
7
votes
1
answer
371
views
Does the percentage of groups of order at most $n$ of even order aproach $1$?
Let $E_n$ be the number of isomorphism classes of groups of even order at most $n$, let $G_n$ be the number of isomorphism classes of groups of order at most $n$ and $T_n$ be the number of isomorphism ...
- 1,835
7
votes
1
answer
455
views
More asymptotics for trees
This is a follow up to my recent question on the asymptotics of A003238. Lucia gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've ...
- 1,305
14
votes
1
answer
696
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,305
3
votes
1
answer
705
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 ...
- 13.9k
16
votes
2
answers
2k
views
How many triangulations of the genus $g$ surface on $n$ vertices?
By "a triangulation of $X$", I mean a simplicial complex whose geometric realization is homeomorphic to $X$. Tutte showed that the number of combinatorially distinct triangulations $t(n)$ of the $2$-...
- 7,857
7
votes
0
answers
355
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 ...
- 1,414