Questions tagged [enumerative-combinatorics]
The enumerative-combinatorics tag has no usage guidance.
504 questions
3
votes
0
answers
179
views
A boolean representation of the Möbius function on a finite lattice
Let $(L,\wedge , \vee)$ be a finite lattice with minimum $\hat{0}$ and maximum $\hat{1}$.
Consider the Möbius function $\mu$ on $L$ defined inductively by $$\mu(\hat{1}) = 1 \text{ and } \mu(a) = - \...
5
votes
1
answer
246
views
Are there graphs whose matching polynomials are Legendre?
It is well-known (at least well-known enough to be on Wikipedia) that there are quite simple graphs whose matching polynomials
$$M(G;x) = \sum_{m\geq 0} (-1)^m \#\{\text{matchings with $m$ edges}\}\,...
- 205
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
4
votes
1
answer
216
views
Counting inversions in a certain patterned matrix
Let $p$ and $q$ be relatively prime. Consider the $p\times q$ matrix $A$ containing the entries $1, 2, 3, \dots, pq$, which is formed via $a_{11} = 1, a_{22} = 2, \dots, a_{p-1,q-1} = pq-1, a_{pq} = ...
- 41
11
votes
1
answer
330
views
a Hankel matrix of involution numbers
Let $I_k$ denote the enumeration of involutions among permutations in $\mathfrak{S}_k$. I always enjoy these numbers. Of course, here is yet another cute experimental finding for which I ask validity. ...
- 43.1k
5
votes
1
answer
177
views
an algebra generated by some known series
Denote the e.g.f. for the number of (unordered) rooted labeled trees on $n$ nodes by
$$\Phi(x)=\sum_{n\geq1}\frac{n^{n-1}}{n!}x^n.$$
And, the related series $\Psi(x)=\sum_{n\geq1}\frac{n^n}{n!}x^n$. ...
- 43.1k
3
votes
1
answer
253
views
What is the value of this sum involving q-binomials?
Let $n\ge 2r$ be positive integers.
Is there a closed form for following finite summation involving in q-binomial coefficients
$$\sum_{s=0}^r(-1)^sq^{\frac{s(s+1)}{2}}{n-2r+s\brack n-2r}_q{n\brack r-...
- 1,093
6
votes
1
answer
328
views
Expanding into monomials
Given a multi-variable function $F$, denote the number of monomials by $N(F)$. For example, $N(x(x+y))=N(x^2+xy)=2$ and
$$
N(x(x+y)(x+y+z))=N(x^3+2x^2y+x^2z+xy^2+xyz)=5.
$$
Define the functions $f_n=...
- 43.1k
3
votes
1
answer
197
views
Generalized Shared Birthday
Suppose a year has $d$ days. How many people should be in a room so that there are at least $2k$ people in the room with birthdays shared with each other (all could be same day or there could be $k$ ...
user94040
3
votes
0
answers
142
views
Probability of hitting two vectors
Call an element of $ \{-m,\dots,0,\dots,m\}^{2^n}$ a vector. Assume $m = O(2^{2^n})$.
Let $u_1,u_2$ be vectors.
Let $\{v_1,\dots,v_{2^n}\}$ and $\{w_1,\dots,w_{2^n}\}$ be linearly independent ...
- 13.9k
3
votes
2
answers
543
views
Number of $\{0,1\}$ matrices with distinct rows and distinct columns
How many $M\in\{0,1\}^{r\times c}$ are there such that each row and each column of $M$ is distinct?
How many classes of matrices in $\{0,1\}^{r\times c}$ up to permutation equivalence are there such ...
user94040
7
votes
1
answer
371
views
Does the percentage of groups of order at most $n$ of even order aproach $1$?
Let $E_n$ be the number of isomorphism classes of groups of even order at most $n$, let $G_n$ be the number of isomorphism classes of groups of order at most $n$ and $T_n$ be the number of isomorphism ...
- 1,835
7
votes
0
answers
124
views
in search of intepretations and connections for $k$-central binomials
Fix a positive integer $k$. Then, the sequences
$$c(n,k)=\frac{k^n}{n!}\prod_{m=1}^{n-1}(1+km)=[x^n]\left(\frac1{1-k^2x}\right)^{1/k}$$
are referred to as "$k$-central binomial coefficients",...
- 43.1k
7
votes
1
answer
366
views
a new representation for Eulerian numbers?
The Eulerian numbers enjoy many different presentations among which I write the two-variable recursive definition: $A(n,0)=1$ and $A(n,k)=0$ for $k<0$ so that
$$A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)....
- 43.1k
13
votes
2
answers
1k
views
an identity for a sum over partitions
Write an integer partition $\lambda\vdash n$ in two different ways:
(1) $\lambda=\lambda_1\geq\lambda_2\geq\lambda_3\cdots\geq\lambda_k\geq1$
(2) $\lambda=1^{m_1}2^{m_2}3^{m_3}\cdots n^{m_n}$ for ...
- 43.1k
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
9
votes
0
answers
275
views
pattern-avoiding permutations vs multi-core partitions
Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. ...
- 43.1k
9
votes
1
answer
299
views
in need of a direct combinatorial/bijective proof
The following are very familiar and basic items, individually.
(1) The number $a(n)$ of rectangles (parallel to axes) in an $n\times n$ square grid.
(2) The number $b(n)$ of cubes (parallel to axes) ...
- 43.1k
2
votes
1
answer
238
views
"flavored" equivalence classes of permutations
We say two permutations $\pi_1$ and $\pi_2$ in the symmetric group $\mathfrak{S}_n$ are $k$-equivalent, denoted
$\pi_1 \sim_k \pi_2$, if one can be
determined from the other after a finite number of ...
- 43.1k
7
votes
1
answer
232
views
counting monomials and integrality
For $n\in\mathbb{Z}^{+}$, consider the polynomials
$$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$
QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?
...
- 43.1k
5
votes
1
answer
286
views
Number of bipartite graphs with a neighborhood property
Consider a bipartite graph of order $2n$ with equal bipartitions $C_1$ and $C_2$, where, $$C_i = \{v_{i,1}, v_{i,2}, v_{i,3} \dots v_{i,n}\}; i = 1, 2.$$
Given two vertices $v_{i,p}$ and $v_{i,q}$, $...
- 363
4
votes
2
answers
1k
views
Expected number of substring in random string
Consider random string of length $n$ over alphabet of size $|\mathcal{A}|=a$ ($a^n$ strings in total). What's expected number of distinct substrings of this string? What's expected number of distinct ...
- 331
6
votes
1
answer
303
views
Maximum number of elements in union of subspaces
Let $V$ be a $m$-dimensional vector space over $\mathbb{F}_q$ and $1<\ell<m-1$. Let $r$ be a positive integer such that $r\ell\leq m$.
QUESTION. What is the maximum number of elements in the ...
- 71
4
votes
1
answer
597
views
genus zero permutation and noncrossing partition
Question
Let $g$ to be an element of permutation group $S_n$, and $\tau = (1,2,3,\cdots,n)$ is the circular permutation. $g$ and $\tau g$ have $n+1$ cycles in total(fixed point is also a cycle), ...
- 165
1
vote
3
answers
189
views
A problem with an edge labeling on the boolean lattices
Let $B_n$ be the boolean lattice of rank $n$. Let $\hat{0}$ and $\hat{1}$ be the minimum and the maximum, respectively.
We identify the notion of edge with the notion of interval $[a,b]$ of cardinal $...
5
votes
1
answer
151
views
Counting the orbits of a set of tabloids under the action of a Young subgroup
Let $\lambda = (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k)$ and $\mu = (\mu_1 \geq \mu_2 \geq \cdots \geq \mu_\ell)$ be partitions of a positive integer $n$. As in Fulton's book on Young ...
2
votes
1
answer
83
views
Birkhoff Lattice of a forest
In my research, I stumbled upon a particular kind of poset and I was wondering, whether there is something in the literature (I could not find anything so far).
They are distributive lattice $L$ ...
- 243
7
votes
1
answer
169
views
Enumerative characterisation of boolean lattices II
This is a sequel of this post.
The boolean lattice $B_n$ is graded with rank numbers $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$, and $n2^{n-1}$ edges.
Question: Is a graded lattice with the ...
5
votes
1
answer
247
views
Enumerative characterisation of boolean lattices
The boolean lattice of rank $n$ (noted $B_n$) is the subset lattice of $\{1,2, \dots , n \}$.
See the Hasse diagram of $B_3$ below:
The Hasse diagram of $B_n$ is of length $n$, with $2^n$ vertices ...
3
votes
1
answer
408
views
Counting graphs according to recursion depth
Consider the set $S$ of multigraphs defined recursively as follows:
Example Graph Class
A graph $G$ is in $S$ if(f)
$G$ is a loop on a single vertex, or
$G$ may be obtained by ...
- 151
12
votes
0
answers
270
views
Number of updown sequences of $1,1,2,2,\cdots,n,n$
I would like to count the updown sequences of the set $\{1,1,2,2, \cdots, n,n \}.$
Sequence $a_1, a_2, a_3, \ldots$ is an updown sequence if the sequence satisfies the following: $ a_1 \lt a_2 \gt a_3 ...
- 121
8
votes
2
answers
540
views
Combinatorial proof of fact about Eulerian numbers?
Let $A(m,n)$ denote the Eulerian numbers.
I'm looking for a simple combinatorial proof of the following fact.
Fact. If $p$ is prime and $0\le k < p-1$, then $A(p-1,k) \equiv 1 \pmod{p}$.
The ...
- 82.6k
3
votes
1
answer
693
views
Size of automorphism group of random regular graph
If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$?
--
I want to know what is the ...
- 13.9k
3
votes
0
answers
230
views
On weight enumerators of codes
Are there $[n,k]_q$ constant rate $\frac kn$ and constant alphabet linear code families with automorphism group of size $\Omega((n-n^\beta)!)$ that have minimum distance $d=O(n^\alpha)$ and number of ...
- 13.9k
6
votes
2
answers
2k
views
Convergence issues with infinite product of formal series
Question first:
Show that if $s_1 < s_2 < \dots$ is an increasing sequence of positive integers and $P(x)$ is a nonzero polynomial then we cannot have
$$ P(x) \equiv \prod_{j=1}^\infty (1 - ...
- 1,207
6
votes
0
answers
342
views
What is known about the $q$-analogue of the simplex?
I am interested in the field with one element. I am thus interested in combinatorial interpretations of the Gaussian binomial coefficients. Richard Stanley's "Enumerative combinatorics" mentions ...
4
votes
1
answer
1k
views
Analytic Combinatorics: upper bound for sum of absolute values of two complex functions: $|z f'(z)| + |2 f(z) - zf'(z)| \leq 2f(|z|)$
Let $f \colon \mathbb C \to \mathbb C$ be a complex-valued analytic function with non-negative coefficients of Taylor series at 0 (suppose that radius of convergence is $+\infty$ for simplicity):
$$
...
- 247
0
votes
0
answers
135
views
Number of polyhedra with N faces?
A. Up to isomorphism, how many polyhedra with N faces are there? Assume each face can be a triangle, square, pentagon, hexagon, etc... Furthermore each edge can be resized to any nonzero positive ...
- 101
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
7
votes
1
answer
480
views
Imprimitive solutions to $x^2+y^3=z^7$
Poonen, Schaefer, & Stoll give the primitive solutions to $x^2+y^3=z^7$:
$$
(±1, −1, 0), (±1, 0, 1), ±(0, 1, 1), (±3, −2, 1), (±71, −17, 2),\\
(±2213459, 1414, 65), (±15312283, 9262, 113), (±...
- 9,114
2
votes
1
answer
300
views
Number of subsets that sum to $0$
Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...
user76479
4
votes
1
answer
271
views
The class of $(-1,0,1)$-matrices with all row sums and column sums equal to $0$
Let $n$ be an even positive integer and $W_n$ be the class of all $n\times n$ matrices with entries from the set $\{-1,0,1\}$ such that all row sums and column sums are equal to $0$.
For each $M\in ...
- 1,997
1
vote
1
answer
126
views
Counting bounded genus non-isomorphic graphs
What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.
user76479
7
votes
2
answers
480
views
Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?
Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
- 13.9k
5
votes
2
answers
237
views
Are the Gessel sequence integers composite for all $n\ge 3$?
The Gessel sequence is known for Ira Gessel's Lattice Path Conjecture of $2001$, which has been proved by Kauers, Koutschan and Zeilberger in $2009$ with the aid of a computer. Later, other proofs ...
- 12.1k
13
votes
0
answers
323
views
Reference request: exponential growth rates of subword-closed languages are integers
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters (...
- 2,339
1
vote
1
answer
220
views
Reference request: $\chi^{\lambda'}(\sigma) = (-1)^{n-\ell(\sigma)} \chi^\lambda(\sigma),$ for characters of the symmetric group
I'm looking for a text I could cite that explicitly states the following result: for $\chi^\lambda$ the irreducible character of the symmetric group indexed by the partition $\lambda$, and for $\sigma ...
- 2,151
20
votes
2
answers
920
views
Counting problems where unlabeled is easier than labeled
I was encouraged to post this question by Jim Propp during a meeting of the Cambridge Combinatorics and Coffee Club. It is a counterpoint to the MathOverflow question "Counting Problems where Labeled ...
- 24.2k
2
votes
2
answers
1k
views
Number of ways of tiling a $2 \times n$ rectangle using rectangles with integer sides
How many ways are there of tiling a $2 \times n$ rectangles using rectangular tiles with positive integer side lengths?
I've done some work on this and have found a way of calculating this that's ...
- 4,943
1
vote
1
answer
575
views
Is there a nice choice-free argument to count the number of sublattices?
It's a well known fact that the number of index $n$ sublattices of a rank two lattice $\Lambda$ is given by $\sigma_1(n) = \sum_{d\mid n} d$.
Here is a proof of this fact:
Proof: choosing a basis of ...
- 6,290