Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
504 questions
0
votes
0
answers
22
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
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_{[\...
- 553
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 ...
- 553
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.
...
- 423
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
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
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,\...
- 281
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
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,...
- 15.6k
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
-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'...
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 ...
- 1
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 ...
- 151
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})$$
...
- 53
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 ...
- 111
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
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.
...
- 175
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 ...
- 1,608
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 ...
- 91
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
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, ...
- 82.6k
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 ...
- 11
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 ...
- 23
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 ...
- 1,561
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$, ...
- 1,549
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&...
- 11
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^{...
- 185
3
votes
0
answers
171
views
Factorization of symmetric polynomials
Let $\Lambda_n$ be the algebra of all symmetric polynomials in $n$ variables, which we also consider as an infinite-dimensional vector $\mathbb{Q}$-space, whose basis is the Schur polynomials.
The ...
- 656
2
votes
0
answers
281
views
Distribution of peaks in Dyck paths
A Dyck word is a sequence of open and closed brackets such that the brackets come in correctly matched pairs. For example $(()(()))()$ is a Dyck word, while $())(()$ is not. A Dyck path is a visual ...
- 1,295
9
votes
0
answers
355
views
The $n$ queens problem with no three on a line
The $n$ queens problem asks if we can place $n$ queens on an $n\times n$ chessboard such that no two queens attack one another. For example, when $n=8$, here are two solutions (images taken from ...
- 667
2
votes
1
answer
320
views
Can you confirm the positivity of a quantity involving the Stirling numbers of the first kind
Let $s(m,n)$ denote the Stirling numbers of the first kind. For $m,n\in\mathbb{N}$, define
\begin{equation}
\mathcal{Q}(m,n)=(-1)^n\sum_{\ell=0}^{2n} \binom{m+\ell-1}{m-1} s(m+2n-1,m+\ell-1)\biggl(\...
- 1,091
7
votes
1
answer
503
views
Combinatorial consequences of de Branges's Theorem?
I'm usually not a proponent of the mentality “here is a tool, what results can we prove with it?” (as I prefer to start at the other end with a well-motivated problem), but this famously entertaining ...
- 191
3
votes
3
answers
756
views
Ordinary partitions vs partitions into odd parts
Let $\mathcal{P}(n)$ be the set of all unrestricted partitions of $n$ while $\mathcal{O}(n)$ stand for the set of all partitions of $n$ into odd parts. We adopt the power notation for partitions $\...
- 43.1k
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$ ...
- 1,851
3
votes
0
answers
222
views
Number of partitions of set restricted by sum of square of part size
Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\...
- 405
15
votes
2
answers
910
views
Sequences that don't count algebraic structures on finite sets
People count $n$-element groups, $n$-element monoids, $n$-element commutative monoids, etcetera - always up to isomorphism. The algebraic structures I've listed, and many more, are studied ...
- 22.2k
3
votes
0
answers
118
views
Divide Euclidean space by surfaces
It is well known that $n$ hyperplanes in $\mathbb{R}^k$ can divide $\mathbb{R}^k$ into at most $p$ regions where $p$ is
\begin{equation}
1 + n + C^2_n + \cdots + C^k_n
\end{equation}
Is there similar ...
- 185
0
votes
0
answers
170
views
Sum of square of parts, and sum of binomials over integer partition
Let $n$ be positive integer. Consider its integer partitions denoting as $(m_1,\cdots,m_k)$, where $m_1+\cdots+m_k=n$ and the order does not matter. We ignore the case of $(m_1,\cdots,m_k)=n$.
I am ...
- 405
7
votes
2
answers
328
views
The number of boolean function with given Fourier degree
How many boolean functions $\{-1,1\}^n \to \{-1,1\}$ with Fourier degree at most $d$?
By Fourier degree I mean the maximal cardinality of $S$ such that the Fourier coefficient $\hat{f}(S)$ is not ...
- 2,576
1
vote
0
answers
125
views
The number of boolean functions with given decision tree complexity
How many boolean function with $n$ variables with decision tree complexity $k$?
By decision tree complexity of a function $f$ I mean the smallest depth among all deterministic decision trees that ...
- 2,576
3
votes
1
answer
272
views
Enumerating possible number of satisfied linear equations
Consider a system of linear equations of variable $x=(x_1,\cdots,x_n)$ where each $x_i\in\{ 0,1,\cdots,L-1 \}$. Clearly, there are $\frac{n(n-1)}{2}$ number of equations in the system.
$$x_i-x_j=0, \ \...
- 405
0
votes
1
answer
346
views
A combinatorial proof: where art thou?
Start by introducing the finite sums
$$A_n:=\sum_{m=1}^nq^m\prod_{j=1}^{m-1}(1-q^j) \qquad \text{and} \qquad
B_n:=\sum_{m=1}^nq^m\prod_{j=m+1}^n(1-q^j).$$
An algebraic proof is facile: Clearly, $A_1=...
- 43.1k