Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
166 questions with no upvoted or accepted answers
2
votes
0
answers
108
views
number of ways to cover an $m × n$ rectangle
Given a positive integer $k\ge2$, let be $f_k(m,n)$ the number of ways to cover an $m × n$ rectangle with $mn/k$ tiles ( $1×k$ or $k×1$)
$f_2(m,n)$ is kasteleyn formula
$f_k(m,n)$?
- 683
2
votes
0
answers
87
views
Reference request on Plancherel measure for partitions whose parts differing by more than $1$
Given an (unrestricted) integer partition $\lambda$ of $n$, let $f_{\lambda}$ denote the number of standard Young tableaux (SYT) of shape the Young diagram $Y(\lambda)$ of $\lambda$. Then,
$$\sum_{\...
- 43.1k
2
votes
0
answers
413
views
A (really!) cute identity between product of binomials
As an off-shot of my earlier MO question, I have found a "really cute" identity. The connection is revealed in the limit $q\rightarrow 1$.
So, I would like to ask:
QUESTION. Is there a ...
- 43.1k
2
votes
0
answers
50
views
Calculating permanents via Branch and Bound
Permanents can be interpreted as counting directed cycle covers of an asymmetric graph with unit cost edge weights.
That interpretation leads to a branch and bound algorithm for calculating the ...
- 13.2k
2
votes
0
answers
55
views
Compact expression for triples of subsets with total sum zero
I am looking whether there is any compact way to write the following: Suppose we have an abelian group $G$. For a subset $A\subset G$ let $S_A$ be the sum of its elements. I want to find the number of ...
- 847
2
votes
0
answers
143
views
Enumerative geometry and restricted plane partitions
Donaldson-Thomas theory is an enumerative theory for virtual counts of ideal sheaves (with trivial determinant) of the structural sheaf $\mathcal{O}_{X}$ of some smooth projective manifold $X$.
There ...
- 502
2
votes
0
answers
81
views
Number of nonisomorphic weighted hypergraphs of certain type
Let $G=(V,E)$ be an unlabeled simple hypergraph with weighted vertices and given properties:
$|v|⩾max(d(v);\;3)\;∀v∈V$, where $|v|$ denotes weight of vertice $v$ and $d(v):=\#(e:\;v∈e)$ - number of ...
- 651
2
votes
0
answers
290
views
Can ${2n \choose n}$ ever be divisble by $2n+1$ (for positive integer $n$)?
The question in the title arose from some semi-recreational number theory. A quick check on a spreadsheet shows the answer is negative for $1\leq n \leq 20$; I haven't tried to use any more serious ...
- 25.8k
2
votes
0
answers
171
views
Enumeration and encoding of simplicial complexes
I'd like to know how to enumerate and encode all (abstract) simplicial complexes of a given kind.
To start as simple as possible, consider the familiy $\mathcal{S}_n^{d}$ of simplicial complexes which ...
- 9,720
2
votes
0
answers
119
views
Counting the number of simple labelled bipartite graphs 𝐺𝑛,𝑚 with 𝑘 edges such that 𝑑1 vertices have degree 1
I have tried to count the number of simple labelled bipartite graphs $G_{n,m}$ with $k$ edges such that $d_1$ vertices have degree 1.
Has this problem been studied?
So far the only related paper I ...
- 21
2
votes
0
answers
141
views
A combinatorics identity
Let $G$ be a finite group, for any positive integer $n$ we have a wreath product $G\wr \Sigma_{n}$. It is well know that the conjugacy classes of $G\wr \Sigma_{n}$ is classified by sequences $\{m_{r}(...
- 311
2
votes
0
answers
32
views
On the number of connected functional digraphs recoverable from the preimage set size structure
I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$.
For example,
$P_j=\left[f^{-j}(...
- 23
2
votes
0
answers
66
views
Annihilator of the of the generating function not holonomic
The following is a generating function in $x,h$ with infinite parameters
$q_1,q_2\ldots,$ and $w_1, w_2,\ldots$.
$$\Psi(x, h)= \sum_{d=0}^{\infty} s_{(d)} (q_1, q_2, \ldots) \exp \bigg( \sum_{r=1}^{\...
- 685
2
votes
0
answers
85
views
Integer compositions with quadratic sum constraint
A statistical question I'm studying has led me to the following counting problem: Let $\lambda_j := \binom{j}{2}$. For integers $1 \le q \le n$ and $1 \le b \le \lambda_n$, determine $X[n,q,b]=$ the ...
- 121
2
votes
0
answers
111
views
Enumerating group actions with constrained images, up to symmetries
Consider the following combinatorial problem:
Let $G$ be a finite group, and $X = \sqcup_{i\in I} X_i$ be a finite set.
Suppose that for each $g\in G$ and $i\in I$ we have sets $Y_{g,i} \subset X$, ...
- 7,800
2
votes
0
answers
187
views
Direct proof that a certain generating function is D-finite
Consider the set $T^{2,3}_n$ of all non-planar rooted trees with $n$ leaves labelled by $1,2,\ldots,n$ where each internal vertex can have two or three children. If we think of the binary / ternary ...
- 16.9k
2
votes
0
answers
92
views
Counting labelled graphs according to sets of size 3
In this question we are counting labelled simple graphs. No concept of isomorphism is involved.
Let $G(n,e,t)$ be the number of labelled simple graphs with $n$ vertices, $e$ edges, and $t$ sets of ...
- 37.7k
2
votes
0
answers
970
views
Is the stationary distribution of this Markov chain uniform?
First, a little bit of background: Since 2012, Canada has decided to phase out the penny for its coinage system. Product prices may still use arbitrary cents, especially since prices do not typically ...
- 29
2
votes
0
answers
457
views
combinatorial rectangles
Consider the set $S$ of all $m\times m$ matrices with $0-1$ entries with exactly $T$ combinatorial rectangles of all $0$s or all $1$s that partition each matrix in a non-overlapping manner.
Is there ...
- 21
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
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
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
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
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
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
1
vote
0
answers
77
views
Distribution of colour pairs from a random matching
Given $a$ many red balls and $b$ many blue balls, with $a+b$ even, suppose we chose a random matching between the $a+b$ balls. What is the distribution of the number of red-red and red-blue (and blue-...
- 129
1
vote
0
answers
100
views
Super Catalan (super ballot) numbers
We refer to this article by Ira Gessel. In section 6, page 10, equation (28), the Super Catalan numbers are defined as
$$S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}.$$
On page 12, equation (31), there goes ...
- 43.1k
1
vote
0
answers
40
views
Probability of generating the same DAG after picking a topological ordering 3 times in a row
Consider the following process:
Choose a random permutation $p$ of $\{1, 2, \dots, n\}$ out of $n!$ options.
Choose a random directed acyclic graph $G$ that has $p$ as a topological ordering out of $...
- 1,171
1
vote
0
answers
77
views
Existence of full-weight codeword in a linear q-ary code
I'm new to coding theory but would like to ask the following question:
Let $C$ be a linear $q$-ary code over $\mathbb{F}_q$ of length $n$ and dimension $k$ where $\mathbb{F}_q$ is a finite field with $...
- 191
1
vote
0
answers
67
views
Counting pieces when an object is cut n ways
I was reading a passage from an old essay by Martin Gardner on the calculus of finite differences, and it seems to me that there is more that can and should be said about seemingly anomalous values of ...
- 19.7k
1
vote
0
answers
203
views
Generalizing "partition into odd parts=partition into distinct parts"?
The number of partitions into distinct parts is known to agree with the number of partitions with odd parts. For instance, this follows from
$$\prod_{k=1}^{\infty}(1+q^k)=\prod_{n=1}^{\infty}\frac1{1-...
- 43.1k
1
vote
0
answers
85
views
Varieties of trees with logarithmic degree function
I am interested in varieties of trees with a logarithmic degree function. I am currently looking at Bergeron, Flajolet, and Salvy's work "Varieties of increasing trees." They discuss exactly ...
- 81
1
vote
0
answers
142
views
A holonomic function and its singularity
The following series where $q_i , h$ are constant parameters. $G(z)$ is a rational function.
$$F(x):=\sum_{d= 1}^\infty \sum_{k=1}^d (-1)^{d-k} \, s_{(k, 1^{d-k})}(\tfrac{q_1}{h}, \tfrac{q_2}{h}, \...
- 685
1
vote
0
answers
69
views
LGV scheme: Any situations where the weights shift differently for each path?
In Cylindric partitions, Proposition 1, Gessel and Krattenthaler prove a formula for lattice paths on a cylinder
In our particular problem, we again have paths $((P_{1},k_{1}),...,(P_{r},k_{r}))$ but ...
- 5,474
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
- 13.9k
1
vote
0
answers
90
views
Dimension of a certain space of symmetric functions: Part II
This is the second installment of my earlier MO question.
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. Denote the set of all partitions with distinct parts by $\...
- 43.1k
1
vote
0
answers
94
views
Number of extremal $\{0,1\}$ matrices having permanent $1$ property
Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$?
I think it might be $\mathsf{poly}(n!)$ bounded.
Is there a function ...
- 13.9k
1
vote
0
answers
139
views
Polynomial systems and algebraic functions
An algebraic function $y(x)$ is defined as the solution of a polynomial equation of the form $p(x,y)=0$, that is one making the identity $p(x,y(x))=0$ true --- in either analytical or formal power ...
- 333
1
vote
0
answers
134
views
Counting unions of unlabelled connected graphs
My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...
- 183
1
vote
0
answers
100
views
Balls and bins, with cardinality constraints
Suppose I have $n$ sets of $k$ balls each, with each one of the $nk$ balls distributed uniformly at random among $m$ bins. Further suppose that I have a probability vector $p=(p_1,\dots,p_m)$. I am ...
- 4,049
1
vote
0
answers
53
views
Standard terminology for these "coarsening" and "refining" operations for compositions and ordered set partitions?
Let $[M]:=\{1,2,\dots, M\}$. (Part of the twelvefold way) as we all know, there is a bijection between surjective functions $[N] \to [B]$ and ordered set partitions of $[N]$ into $[B]$ blocks (of ...
1
vote
0
answers
177
views
Combinatorial bijection on monotone sequences
Let $(n),\mu$ be the partition of $n$ define $H_g^{m}((n);\mu)$ count's the number of tuples $(\tau_1,\ldots,\tau_r)$ of transposition in symmetric group $S_n$ with the following conditions
$$ (1,2,\...
- 685
1
vote
0
answers
29
views
Extension of definition of Holonomic closure
My question is about finding the annihilator of a series. Let me begin with what is known and then ask my question. Let $s_d(\frac{q_1}{h},\ldots )$ denote schur function for partition $\lambda =[d]$ ...
- 685
1
vote
0
answers
681
views
Generate all connected non-isomorphic graphs of n vertices modulo local complementation?
I'd like to generate a list of all simple, connected, undirected graphs of $n$ vertices, modulo standard graph isomorphism, and modulo local complementation, which is the following operation: for a ...
- 91
1
vote
0
answers
119
views
Combinatorial problem involving sets (+graph theoretic interpretation)
I have the follwing combinatorial question, which I motivate below.
Let $N:=\lbrace 1,\dots,n \rbrace$ be a set and let $\lambda_1,\dots,\lambda_l$ be a collection of $l:=n+3$ subsets of $N$ with the ...
- 11
1
vote
0
answers
291
views
On the number of Eulerian orderings
This post is a sequel of Eulerian ordering of the integers modulo n.
Let us recall the definition of an Eulerian ordering:
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$....
1
vote
0
answers
43
views
Counting arrangements around a table with constraints
I have $n$ guests seated around a circular table. I want to serve them meals so that given any two guests $u$ and $v$, either
i. $u$ and $v$ have different meals, or
ii. $u$'s two neighbors have a ...
- 325
1
vote
0
answers
90
views
Partition of sets of monomials
Given a degree $d>0$ and $x_1,\dots,x_n$, consider the set $S$ of monomials
\begin{equation*}
x_1^{i_1} \cdots x_n^{i_n}
\end{equation*}
with $0\leq i_j\leq d$ for $1\leq j\leq n$ (the exponents ...
- 53
1
vote
0
answers
180
views
closed form expression for a sum? (combinatorics)
For non-negative integers $m$ and $n$, and positive real numbers $a$, $b$, define
$$\theta(m,n,a,b) := \underbrace{\sum_{p=0}^m \sum_{q=0}^n}_{p+q \; {\rm even}} \binom{m}{p} \binom{n}{q} \binom{p+q}{(...
- 511
1
vote
0
answers
249
views
Is there a way to simplify this apparently huge characteristic polynomial calculation?
Say I am given the $0/1$ adjacency matrix of an undirected graph. Also I am given a representation $\rho$ of some group $G$ and an orientation has been arbitrarily chosen along each edge. Let $E^{...
- 1,893