Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no summary.
537 questions
9
votes
3
answers
390
views
A question on the plethysm of complete symmetric functions
Based on some small calculations in SageMath, I conjectured that the Schur expansion of $h_n[h_k]$ contains $s_{(k,k,...,k)}$ if and only if $k$ is even. For example, this is easily seen when $n=2$. ...
- 409
3
votes
0
answers
190
views
Analytic continuation of algebraic functions
Consider the polynomial $K(z,u)= u^e- z (p_0+p_1 u+...+p_k u^k)$, where: $k,e$ are nonnegative integers and the coefficients $p_i$ are nonnegative reals such that $0< \sum_i p_i \leq 1$ with $p_0&...
- 373
6
votes
3
answers
1k
views
Peculiar exception in the number of distinct values taken by the sums of the 6th degree roots of unity
For a nonnegative integer $n$, let $N_n$ be the number of distinct values taken by the sums of $n$ 6th-degree roots of unity (with repetitions). First few counts are $N_0=1$, $N_1=6$, $N_2=19$, and ...
- 38.3k
0
votes
1
answer
182
views
Number of unimodal quadruples
Let $n \leq k \in \mathbb{N}$. Define unimodal $n$-tuple of weight $k$ as ordered $n$-tuple of positive integers $d_1, d_2, \dots, d_n$ such that
$$
\sum_{i=1}^{n} d_i = k
$$
and $\exists s \in \{1,2, ...
1
vote
2
answers
298
views
Algorithms to count restricted injections
Let the following data be given.
Two positive integers $m$ and $n$.
A family of sets $B_a \subseteq \{1, \dots, n\}$ (for $a \in \{1, \dots, m\}$).
The task is to count the number $N$ of injective ...
- 143
0
votes
0
answers
136
views
References for generalizations of rook polynomial
I'm preparing a talk on the rook polynomial, and I would like to mention some references on its variants and the reasons they were defined.
I am familiar with the following two generalizations because ...
- 1,309
7
votes
2
answers
765
views
Counterexample to a generalization of Frankl's union-closed sets conjecture
We call a family of sets $\mathcal{F}$ is weakly union-closed if for all $A,B\in\mathcal{F}$ such that $A\cap B=\varnothing$, we have $A\cup B\in\mathcal{F}$.
Conjecture: For finite weakly union-...
- 1,488
7
votes
1
answer
338
views
Stirling number lattice polytope
This was motivated by this recent question: Expansion identity for the Eulerian polynomials of the second order
Question: For each integer $m \geq 0$, is there some $2m$-dimensional lattice polytope $...
- 25.8k
2
votes
0
answers
149
views
Is there a canonical name for this variant of the rook polynomial?
Let $\mathcal{P}$ be a polyomino. Two or more rooks on $\mathcal{P}$ are called non-attacking if no path of edge-adjacent cells of $\mathcal{P}$ connects any pair of them along a row or a column.
Let $...
- 1,309
56
votes
1
answer
2k
views
When did the OEIS get even better?
I'm asking this question out of curiosity, but also (and more importantly) to publicize to the research community something great that OEIS.org is doing.
Recently, I put a sequence into OEIS and got ...
- 2,433
2
votes
0
answers
253
views
$\mathcal{P}$-rook polynomial of a grid
The $\mathcal{P}$-rook polynomial of a polyomino $\mathcal{P}$ is
$$
r_\mathcal{P}(T) = \sum_{k=0}^{r(\mathcal{P})} r_k(\mathcal{P})\ T^k,
$$ where $r_k(\mathcal{P})$ is the number of ways to place $...
- 1,309
3
votes
0
answers
142
views
Does a random rooted tree with sufficiently many leaves almost surely contain a specific rooted tree as a subtree?
Let $\mathcal{T}_n$ be the set of rooted, unlabeled trees with $n$ leaves, where each vertex either has no child or has at least two children. Let $\mathcal{T} = \bigcup_{n \ge 2} \mathcal{T}_n$.
For ...
- 133
1
vote
1
answer
353
views
An approach to a generalization of Frankl's union-closed sets conjecture
Let $I$ be a non-empty finite set, $\mathcal{F}$ be a non-empty union-closed family of subsets of $I$ except the empty set and $n$ real numbers $x_i\geq1,i\in I$. Let $d_i=\sum_{i\in J,J\in\mathcal{F}}...
- 1,488
1
vote
1
answer
219
views
Is the generating function for triple-turn-avoiding grid Hamiltonian paths D-finite?
Let
$$ \mathcal{G}_{k,n}:=\{1,\dots ,k\}\times\{1,\dots ,n\}\subset\mathbb{Z}^{2}, \qquad k,n\ge1, $$
be a $k\times n$ rectangular lattice graph. A Hamiltonian path (a walk that visits every vertex ...
1
vote
0
answers
66
views
Counting edge-simple walks of length $k$ in the complete graph $K_n$ that cover the whole graph
Let $K_n$ be the complete graph on $n$ vertices. I am interested in counting the number of walks of length $k$ in $K_n$ with the following constraint:
Edges may not be repeated (each edge is used at ...
- 675