Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
488
questions
6
votes
2
answers
256
views
Counting a class of backtracking walks
We are interested in a class of walks on the complete graph on $[n] = \{1,2,\dots,n\}$. A walk of length $k$ is an ordered tuple of directed edges
$$
((i_1,i_2),(i_2,i_3),\ldots,(i_k,i_{k+1}))
$$
...
- 1,729
1
vote
0
answers
92
views
Integral convex polytopes formed from the weight diagrams of representations of $\mathfrak {sl}_4$($\mathbb{C}$)
I'm a student studying undergraduate abstract algebra and doing a summer research project in the mathematics department at my school. I'm barely familiar with the rudiments of representation theory; I ...
- 111
1
vote
1
answer
121
views
reference for a formula of the Motzkin triangle on OEIS
Motzkin triangles (OEIS A064189) $[T_{n,k}]$ are the Riordan arrays $(M(x),xM(x))$, where $(M(x))$ is the g.f. for the Motzkin numbers(OEIS A001006). The OEIS page shows that $$T_{n,k}=\frac{k}{n}\...
- 135
1
vote
1
answer
196
views
Looking for q-analog of derangement anagrams for a word
I have already known QPermutationDerangement:
It describes the distribution
$$
d_n(q)=\sum_{\sigma \in D_n} q^{\operatorname{maj}(\sigma)}
$$
Where we sum over all derangements of an $n$ element set.
...
- 173
6
votes
1
answer
290
views
A generalization of derangement number
What is the number of $n \times n$ binary matrices with row and column sums 2 and with only zeros on the diagonal? This simple problem must have been treated somewhere, but I couldn't find any ...
- 1,576
4
votes
1
answer
181
views
Minimum number of possible proper colorings
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $2k-2$ edges such that it can be properly colored using $k$ colors. What is the ...
- 131
5
votes
0
answers
303
views
On $s$-additive sequences
For a non-negative integer $s$, a strictly increasing sequence of positive integers $\{a_n\}$ is called $s$-additive if for $n>2s$, $a_n$ is the least integer exceeding $a_{n-1}$ which has ...
- 781
2
votes
1
answer
188
views
How many cap sets are there?
Most research on cap sets that I'm aware of focuses on the size of a cap set. Are there any results about the number of maximum-cardinality cap sets?
For example, it is known that in the game of SET, ...
- 80.3k
1
vote
1
answer
154
views
Some ideas about parking functions and integer partitions
We know that a integer partition of $\lambda=(\lambda_1, ..., \lambda_m)$ of $n$ satisfying $\lambda_1\geq \cdots \geq \lambda_m$ and $\sum_{i=1}^m\lambda_i=n$. Let $\mathcal{P}(n)$ be the set of ...
- 11
9
votes
2
answers
317
views
Counting $m\times n$ $\bigl({1\atop1}{1\atop0}\bigr)$-free $(0,1)$-matrices
Let $G_{m,n}$ denote the number of $m\times n$ $(0,1)$-matrices that avoid the submatrix $\bigl({1\atop1}{1\atop0}\bigr)$. (Submatrices need not be contiguous.) Here are some small values (not yet on ...
- 525
0
votes
1
answer
150
views
Formula for partitions of integers with no subpartition being a partition of $t$
When it comes to partitions, I know we can impose some modest restrictions (maybe even a couple) on the partitions and obtain counting formula, but I would like to impose some more serious constraints ...
- 23
5
votes
1
answer
201
views
Bijective proof for an identity concerning Stirling numbers of second kind
Let $\genfrac{\{}{\}}{0pt}{}{n}{k}$ the Stirling number of second kind, where $k$ is the number of parts in the partition.
If we take the identity that transforms the polynomial base $x^k$ into the ...
- 1,551
5
votes
3
answers
482
views
Applying $\sum_i \partial_{x_i}$, $\sum_i x_i \partial_{x_i}$ and $\sum_i x_i^2 \partial_{x_i}$ to Schur polynomials
The operators $L_k=\sum_i x_i^k\frac{\partial}{\partial x_i}$, with integer $k$, take symmetric polynomials into symmetric polynomials.
Is it known how to write the result of the application of $L_0$, ...
- 1,519
0
votes
0
answers
75
views
How many rigid 4-regular graphs are there?
I am interested in any formulas for the number of globally rigid 4-regular graphs, or Laman graphs of degree at most 4, on $n$ vertices. The bound can be for graphs with labeled or unlabeled vertices.
- 18.6k
8
votes
0
answers
136
views
How many simplicial spheres with $n$ vertices and $N$ facets?
Let $s_d(n,N)$ be the number of different $d$-dimensional simplicial spheres on $n$ labelled vertices and $N$ facets (= $d$-simplices). I am in search for the best know upper bounds, especially for $d\...
- 12.8k