Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
504 questions
0
votes
0
answers
21
views
Maximize mixing in a 12 person dinner party
Is this question well posed? If not, can you improve it? If so, what is the solution?
I am holding a dinner party for 12 people. Their names are A, B,...L. The seats are numbered: 1, 2, ... 12. The ...
- 101
11
votes
3
answers
557
views
In search of a $q$-analogue of a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the all-familiar Catalan numbers. Then, the following identity has received enough attention in the literature (for example, Lagrange Inversion: When and How):
\...
- 31
2
votes
0
answers
83
views
Formula for sum involving products of (symplectic) Schur functions
This question is a continuation of a question asked yesterday which had a very nice answer.
Consider the summation
$$\sum_{\lambda \subset (k)^n} \dim S_{\lambda^t} (\mathbb{C}^k) \cdot \dim S_{[\...
- 12.9k
6
votes
1
answer
131
views
Number of semistandard tableaux of all possible shapes fitting within some rectangle
Suppose $n$ and $k$ are two integers. Then I am interested in having a closed form for the sum
$$\sum_{\lambda \subset k \times n} S_\lambda (\mathbb{C}^n),$$
where $S_\lambda$ denotes the Schur ...
- 24.2k
1
vote
1
answer
231
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.
...
CommunityBot
- 1
6
votes
1
answer
940
views
Does the likelihood of these tables exist?
Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background.
Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...
CommunityBot
- 1
3
votes
0
answers
101
views
Tuple rearrangement: a combinatoric problem emerging from the Hurwitz action on Coxeter groups
I am working on Artin Groups, so called Dual Artin groups and the conjecture that they are isomorphic. Tuples of $n$ group elements can be acted on by the braid group $B_n$ in a particular way called ...
- 31
4
votes
0
answers
104
views
A question about decomposing root system $A_{n}$
Denote $\Phi(n)$ as the root system of Lie algebra $\mathfrak{g}$ of type $A_{n}$. Call a disjoint union $\Phi(n) = \Phi_{1}\sqcup\dotsb\sqcup\Phi_{s}$ a decomposition of $\Phi$ if each $\Phi_{k}$ is ...
- 93
1
vote
0
answers
108
views
Asymptotics for sums of two sets of positive integers
Assume that $A$ and $B$ are subsets of $\mathbb N$, with counting functions verifying $A(x)\gg x^\alpha$ and $B(x)\gg x^\beta$, with $\alpha+\beta<1$. Let $C=A+B$ and $C(x)$ its counting function.
...
- 3,319
4
votes
1
answer
207
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 ...
CommunityBot
- 1
4
votes
0
answers
124
views
LIS-based permutation property
Let $S_n$ be the set of all permutations of $\{1, \ldots, n\}$, thereafter treated as integer sequences. Let $A_n$ be the set of all such permutations $\sigma \in S_n$ that we can choose two ...
- 5,590
2
votes
1
answer
215
views
Number of binary matroids of rank $r$ on a ground set with $n$ elements
How many simple binary matroids are there, up to isomorphism, of rank $r$ on an $n$-element ground set, where $r \le n < 2^r$? Write this number as $a_r(n)$. Is there somewhere where I can get this ...
- 331
3
votes
2
answers
403
views
Closed form for product of Stirling numbers of the second kind
What does the following expression evaluate to:
\begin{equation}
\sum\limits_{k=1}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix}
\end{...
- 18.4k
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 ...
- 148k
3
votes
1
answer
153
views
Number of points covered by $2n$ hyperplanes in $\mathbf{F}_p^n$
For a prime $p$, fix two bases $U=\{v_1,\dots,v_n\}$ and $W=\{w_1,\dots,w_n\}$ of the vector space $V=\mathbf{F}_p^n$. We may assume $U$ is the standard basis without loss of generality.
For $s_1,\...
- 148k
25
votes
7
answers
2k
views
Number of collinear ways to fill a grid
A way to fill a finite grid (one box after the other) is called collinear if every newly filled box (the first excepted) is vertically or horizontally collinear with a previously filled box. See the ...
- 224
4
votes
1
answer
409
views
On the parity of the sum $\sum_{1\le j<k\le p-1\atop p\nmid aj^2+bjk+ck^2}(aj^2+bjk+ck^2)$
QUESTION. Let $p$ be an odd prime and let $a,b,c\in\mathbb Z$. How to determine the parity of the sum
$$S_p(a,b,c)=\sum_{1\le j<k\le p-1\atop p\nmid aj^2+bjk+ck^2}(aj^2+bjk+ck^2)$$
in terms of $a,b,...
- 884
8
votes
0
answers
260
views
Efficient listing of ASMs
Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is ...
- 17k
4
votes
1
answer
376
views
Counting permutations with a fixed number of descents and an extra condition
I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...
- 34.3k
-3
votes
1
answer
116
views
Enumerative number theory term searching [closed]
Given $a,b$ positive numbers such that $gcd(a,b)=1$.Prove that there are infinitely many $n$ positive integers such that $x_n=a+nb$ sequence has many terms such that it is not divisible by any prime'...
- 423
0
votes
0
answers
95
views
Nested Set Permutations and their Enumeration
Let $(S_i)_{i \in \mathbb{N}}$ be a sequence of sets defined recursively as follows:
$S_1 = \{1\}$
$S_{i+1} = S_i \cup \{S_i, i+1\} \quad \forall i \in \mathbb{N}$
A permutation $\sigma$ of $S_i$ is ...
- 34.3k
4
votes
1
answer
406
views
Inverse relationship between Stirling numbers of the first and second kind via generating functions
In combinatorics, a well-known result is that the matrix formed by the Stirling numbers of the second kind $\left(S(n,k)\right)_{n,k\geq 0}$ and the matrix of the signed Stirling numbers of the first ...
- 34.3k
5
votes
0
answers
191
views
Do most semigroups have a zero?
It is widely believed in finite semigroup theory that asymptotically almost all finite semigroups $S$, up to isomorphism, are 3-nilpotent, i.e., they satisfy $\#\{abc\,:\,a,b,c\in S\} = 1$. My ...
- 151
1
vote
0
answers
122
views
Monomial symmetric polynomials evaluation at roots of unity
The monomial symmetric polynomials are defined see Wikipedia.
For an arbitrary partition $\lambda$ with $n$ parts
I'm trying to find the following values:
$$m_{\lambda}(\omega_0,\dotsc,\omega_{n-1})$$
...
- 175
18
votes
2
answers
1k
views
A combinatorial interpretation for $n$-ary trees for negative $n$
The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation
$$
T_n=1+xT_n^n.
$$
This is usually defined for $n\ge 0$, but the functional equation can be ...
- 10.5k
6
votes
2
answers
273
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,731
1
vote
0
answers
139
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 ...
- 63.9k
23
votes
3
answers
3k
views
Proofs of parity results via the Handshaking lemma
I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...
- 32.1k
2
votes
1
answer
208
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, ...
CommunityBot
- 1
1
vote
1
answer
173
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 ...
- 175
1
vote
1
answer
130
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
12
votes
1
answer
730
views
Two remarkable weighted sums over binary words
This question builds off of the previous MO question Number of collinear ways to fill a grid.
Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting ...
CommunityBot
- 1
6
votes
1
answer
330
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 ...
- 13.4k
5
votes
0
answers
307
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 ...
- 791
6
votes
3
answers
526
views
Enumerating all inequivalent planar embeddings of a planar graph
Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...
- 37.7k
16
votes
1
answer
804
views
Existence of a faithful irreducible representation using Möbius function
Let $G$ be a finite group, $L(G)$ its subgroup lattice and $\mu$ the Möbius function.
Consider the Euler totient of $G$ defined as follows:
$$ \varphi(G) = \sum_{H \le G}\mu(H,G) |H| $$
Let $X=\{M_1, \...
- 4,219
3
votes
1
answer
232
views
Counting cycle vertex covers on hypercube
Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...
- 63.9k
0
votes
2
answers
309
views
Integer solutions of system of inequalities
I am trying to solve a problem in combinatorics and I came up with the following system of inequalities:
$0\leq x<y<z\leq n$ and $x+y<n$ and I am trying to count the number of integer ...
CommunityBot
- 1
4
votes
0
answers
211
views
Sum $f(n_1,n_2,\ldots,n_k) 1^{n_1} 2^{n_2} \ldots k^{n_k}$ over partitions
Use the notation $(n_1,n_2,\ldots,n_k) \vdash n$ to denote that $(n_1,n_2,\ldots,n_k)$ is a partition of the positive integer $n$, that is, $n_1+n_2+\ldots+n_k = n$ and $n_1 \ge n_2 \ge \ldots \ge n_k ...
- 34.3k
9
votes
2
answers
344
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 ...
- 667
0
votes
1
answer
162
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 ...
- 34.3k
7
votes
1
answer
424
views
Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history
Two arrangements of (affine) hyperplanes in $d$-dimensional Euclidean space are combinatorially isomorphic (or combinatorially equivalent) if they have isomorphic posets of faces.
Counting the ...
14
votes
2
answers
481
views
Number of matchings of even cycles
By doing some calculations on the generating function of matching polynomials of cycles I made the following interesting observation:
For all positive integers $n>1$ and $k <n $, the number of ...
- 32.1k
5
votes
1
answer
228
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 ...
- 109k
6
votes
3
answers
515
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$, ...
- 16.9k
9
votes
0
answers
144
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\...
- 13.6k
2
votes
0
answers
66
views
Combining (generalized) Polya enumeration with invariant properties
Let's say we want to enumerate maps $f$ between two finite sets $X$ and $Y$ modulo the action of groups $G$ on $X$ and $H$ on $Y$. Additionally we want $f$ to satisfy a certain property $P$ that is ...
- 34.3k
6
votes
0
answers
175
views
Combinatorial classes where not almost all objects are asymmetric
Let $\mathcal{C} = \bigcup_{n=0}^{\infty}\mathcal{C}_n$ be a class of finite (labeled) combinatorial objects, where $\mathcal{C}_n$ is the set of objects on $[n] = \{1,2,\dotsc,n\}$. For example, $\...
- 24.2k
1
vote
0
answers
73
views
Ordered combinatorial classes and partitions
Let $\mathcal{C}$ be a combinatorial class and let $\leq$ be a partial order on $\mathcal{C}$. We say that $(\mathcal{C},\leq)$ is an ordered combinatorial class if for all $x,y\in\mathcal{C}$, $$x&...
- 63.9k
1
vote
2
answers
251
views
Estimation of a combinatoric formula
Assume $n\ge m$, what is the estimation of
$$\sum_{k_1+\dots +k_m\,=\,n,\\ k_1\ge 1,\,\dots,\,k_m\ge 1} C_n^{k_1,\dots,k_m} \left(\frac{1}{k_1}+\frac{1}{k_2}+\dots +\frac{1}{k_m} \right)$$
where $C_n^{...
