Questions tagged [enumerative-combinatorics]

Filter by
Sorted by
Tagged with
-1 votes
0 answers
39 views

A Near Closed-Form Expression of Strict Partition Function Inquiry [closed]

I am an independent researcher working in various fields of mathematics and sciences. I am working on a strict partition problem. I believe I have found a very fast exact solution that is a near-...
7 votes
1 answer
379 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
454 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 ...
6 votes
1 answer
866 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 ...
5 votes
1 answer
181 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 ...
0 votes
0 answers
20 views

Algorithm of finding and counting cycles of varying lengths in dynamic or evolving graphs?

In this paper Alon, N., Yuster, R. & Zwick, U. Finding and counting given length cycles. Algorithmica 17, 209–223 (1997)., the authors present various methods for efficiently locating and tallying ...
5 votes
3 answers
394 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$, ...
11 votes
1 answer
675 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 ...
7 votes
0 answers
128 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\...
0 votes
0 answers
55 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.
2 votes
0 answers
57 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 ...
5 votes
0 answers
148 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, $\...
1 vote
0 answers
65 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&...
1 vote
2 answers
233 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^{...
0 votes
2 answers
231 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 ...
3 votes
0 answers
159 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 ...
9 votes
0 answers
264 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 ...
2 votes
0 answers
222 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 ...
7 votes
1 answer
149 views

Is there an infinite combinatorics of common transseries expansions?

By now there is a rich understanding of generating functions in combinatorics, and the way that operations in power series are 'shadows' of richer constructions on combinatorial objects. This lifting ...
2 votes
1 answer
296 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(\...
7 votes
1 answer
474 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 ...
5 votes
2 answers
279 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$ ...
3 votes
3 answers
715 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 $\...
3 votes
0 answers
208 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,\...
7 votes
1 answer
698 views

Is there a natural relationship between OEIS A127670 and Cayley's tree formula?

I apologize in advance that this question must sound highly amateurish, but I am wondering if there is any connection between the formula https://oeis.org/A127670 , which counts the number of fixed $n$...
14 votes
2 answers
875 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 ...
3 votes
0 answers
114 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 ...
0 votes
0 answers
163 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 ...
3 votes
1 answer
260 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, \ \...
6 votes
2 answers
285 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 ...
1 vote
0 answers
104 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 ...
0 votes
1 answer
343 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=...
4 votes
0 answers
158 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 ...
14 votes
3 answers
1k views

On the finite sum of reciprocal Fibonacci sequences

I want to check if $$\left\lfloor \left( \sum_{k=n}^{2n}{\frac{1}{F_{2k}}} \right)^{-1} \right\rfloor =F_{2n-1}~~(n\ge 3) \tag{$*$}$$ where $\lfloor x \rfloor$ is th floor function. The Fibonacci ...
4 votes
2 answers
302 views

Number of partitions of $n$ and number of different integers in 1-avoiding partitions

Consider the number of integer partitions of $n$, usually denoted by $p(n)$ and generated by $$\sum_{n\geq0}p(n)x^n=\prod_{k\geq1}\frac1{1-x^k}.$$ I have encountered an interesting enumeration. Take ...
3 votes
1 answer
571 views

Sum of all products of k distinct integers in [1,n] [duplicate]

Let $S=\{1,2,3,...,n\}$ be the set of integers up to $n$ and $p_k(a_1,...,a_k)=a_1\cdots a_k$ the product of $k$ distinct integers $a_1,...,a_k \in S$. There are $\binom{n}{k}$ possibilities to ...
7 votes
0 answers
213 views

Why are these two determinants equal?

This question is a follow up on Mark Wildon's comment from an earlier MO question. As usual, let $(q)_k=(1-q)(1-q^2)\cdots(1-q^k)$ with $(q)_0:=1$. Also, define the Gaussian polynomials by $$\binom{n}...
4 votes
1 answer
185 views

On a double sum involving binomial coefficients

For natural $n$, let \begin{equation} p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l) \sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1} \end{equation} where $k:=\lfloor(n+1)/...
1 vote
1 answer
260 views

Counting $n$-edge directed graphs

I would like to count the $n$-edge directed graphs. The graphs might contain self-loops (edges connecting a vertex to itself) and multiple edges (multiple edges connecting the same pair of vertices). ...
10 votes
2 answers
887 views

Has anyone tabulated 2-knots? Would anyone like to try?

I'd love to have a list of 'small' $2$-knots, for some sense of small. It's not clear what one should filter by, but there are two obvious candidates Write a movie presentation, and count the frames. ...
0 votes
2 answers
174 views

Asymptotic approximation of a convolution of binomial coefficients

I would like to find the following limit which is somewhat similar to the usual Vandermonde's convolution for binomial coefficients. Define $L$ as follows. $$ L \triangleq \lim_{N\to\infty} \frac{1}{2^...
2 votes
0 answers
74 views

Skewed plane partition with only row fillings reversed

The number of plane partitions in a bounded box is well-studied and dates back to MacMahon, at the start of this paper by Sam Hopkins and Tri Lai, p9, they summarized current results on the ...
4 votes
0 answers
92 views

"Convolving" a general Catalan with classical Catalan

Consider what is sometimes known as generalized Catalan sequence $$\mathcal{{\color{red}C}}_{a,b}:=\frac{2b+1}{a+b+1}\binom{2a}{a+b}.$$ Observe that $\mathcal{{\color{red}C}}_{n,0}$ reduces to the ...
2 votes
1 answer
201 views

Catalan and path pairs in polynomials

Define $\mathbf{K}_n$ to be the set of all $(2n+1)$-tuple sequences $\mathbf{a}=(a_0,a_1,\dots,a_{2n})\in\{-1,1\}^{n+1}$ satisfying: (a) there are $n$ occurrences of $-1$ and $n+1$ of $+1$; (b) all ...
1 vote
0 answers
74 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-...
3 votes
0 answers
88 views

Number of planar bipartite graphs

How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color? How many non-isomorphic classes exist?
6 votes
1 answer
240 views

Intuitive explanations of the Carlitz-Scoville-Vaughan theorem

Crossposted from MSE: I recently came across Ira Gessel's slides on a theorem he says should "be considered one of the fundamental theorems of enumerative combinatorics." The Carlitz-...
2 votes
0 answers
160 views

Lattice paths avoiding holes

Consider lattice paths from $(0,0)$ to $(2n,2n)$ with steps $N=(0,1)$ and $E=(1,0)$ avoiding the points $(2i-1,2i-1)$ for all $1\leq i\leq n$. There are Catalan many $C_{2n}=\frac1{2n+1}\binom{4n}{2n}$...
16 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 ...
4 votes
0 answers
180 views

Fuss-Catalan: how does equality of these determinants hold?

There are many ways that the Catalan numbers seemed to have been generalized, one among them is through what Graham-Knuth-Patashnik (in Concrete Mathematics) dubbed as the Fuss-Catalan numbers $\frac1{...

1
2 3 4 5
10