The enumerative-combinatorics tag has no usage guidance.

**1**

vote

**1**answer

104 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$.

**6**

votes

**0**answers

115 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 ...

**3**

votes

**1**answer

133 views

### Stirling numbers of the second kind with maximum part size

The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...

**3**

votes

**1**answer

110 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):
$$
...

**0**

votes

**0**answers

55 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 ...

**2**

votes

**0**answers

76 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 ...

**4**

votes

**1**answer

235 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), (±...

**14**

votes

**1**answer

770 views

### Are there enough additive permutations?

I am hoping to learn enough about additive permutations to help with a number theory problem. These permutations also have connections to difference sets, orthomorphisms, transversals, and other ...

**5**

votes

**1**answer

246 views

### Set counting problem with a cap on the intersection between the set and a fixed partition

Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$.
1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there ...

**2**

votes

**1**answer

238 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 ...

**1**

vote

**1**answer

316 views

### Q re Kaprekar's fixed mapping points

Jens Kruse Andersen in his comment in OEIS's A099009 noticed 3 families of numbers among Kaprekar's fixed mapping points (otherwise known as kernels of the Kaprekar's routine):
"Let $d(n)$ denote $n$...

**4**

votes

**1**answer

433 views

### Number of simplicial polytopes with a given f-vector

Plenty of very nice literature is available on the characterization of f-vectors of simplicial complexes of diverse sorts (results by Billera, Bjoerner, Kalai, Stanley, among others). I mention, as an ...

**19**

votes

**3**answers

1k views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...

**12**

votes

**0**answers

173 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. The ...

**18**

votes

**2**answers

417 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 ...

**0**

votes

**1**answer

66 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 ...

**12**

votes

**1**answer

812 views

### Two to the power of a triangular number: bijections

The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds (...

**2**

votes

**2**answers

161 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 ...

**1**

vote

**1**answer

152 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 ...

**0**

votes

**0**answers

55 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 ...

**7**

votes

**1**answer

2k views

### Counting non-isomorphic graphs with prescribed number of edges and vertices

I'd love your help with this question.
Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $p$ vertices and $q$ edges are there where $p+q=n$?
Thank you very much.
Crossposted at ...

**2**

votes

**1**answer

260 views

### Distinct determinants of circulants

If $M$ is a circulant integer matrix of size $n\times n$ whose entries are randomly chosen from $\{0,1\}$ value, how many different determinants does $M$ possibly take value in?
For $n=1,2,3,4$, I ...

**14**

votes

**2**answers

234 views

### Generating functions for objects with irrational sizes

A problem I'm investigating concerns a combinatorial class in which the 'atoms' have irrational sizes. It seems likely that this is something that has been considered before, but I haven't been able ...

**9**

votes

**0**answers

106 views

### Cycles of length $2^n - 2$ in the De Bruijn graph

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
...

**0**

votes

**1**answer

65 views

### Finding maximal sets of words at minimum distance

Given an alphabet $Q$ with $k$ letters, consider the set $W(n, k)$ of all words in $Q$ with exactly $n$ letters.
In $W(n, k)$ we can define a distance by $dist(x,y) = \#\{ \text{Places where $x$ and ...

**10**

votes

**2**answers

312 views

### Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...

**0**

votes

**2**answers

296 views

### Enumerating m-tuples of Integers Subject to Implication Constraints [closed]

How do I enumerate all $m$-tuples of positive integers $(a_1,...,a_m)$ subject to the following constraints?
For each $i$ in $\{ 1,\ldots,m \}$, there is a number $n_i \geq 0$ such that $a_i \leq ...

**3**

votes

**1**answer

117 views

### Number of linearly bisected subsets in finite vector space $F_2^n$

We consider the $n$-dimenstional finite vector space $\mathbb{F}_2^{n}$ over the finite field of two elements. For a subset $A\subseteq \mathbb{F}_2^{n}$ of even size $|A|=2m$ and a linear form $l\in(\...

**2**

votes

**1**answer

131 views

### Counting elements with certain word length in abelian groups

Given a (finite) abelian group $G = \langle S \mid R \rangle$, has the problem of counting the number of elements which can be expressed as a word (in $S$) of length $\leq k$ been studied? If so, ...

**3**

votes

**2**answers

982 views

### Polya's theory of counting and commutative algebra

Do you know if there exist algebraic studies of the ring of the power series which emerge when using the theory of Polya for enumeration of sets with certain symmetries? For instance if some ideals ...

**0**

votes

**0**answers

43 views

### Enumeration of simple graphs with given degree distribution/sequence [duplicate]

Is there any exact formula for asymptotic/exact enumeration of simple graphs with given degree sequence? I just found some results about it, but the formula is hold on for some conditions, for example ...

**1**

vote

**1**answer

193 views

### Counting matrices of special types

How many symmetric and non-symmetric $n\times n$ matrices with $0/1$ entries are there such that every row is distinct and every column is distinct? (I am looking for a proof as well).
If only every ...

**3**

votes

**0**answers

145 views

### Estimating the growth rate of nondeterministic finite automata

Given a nondeterministic finite automaton $\mathcal{A}$ (or a regular expression, or a regular grammar), can we efficiently compute the number $|L_k(\mathcal{A})|$ of accepted words of length $k$?
No,...

**3**

votes

**1**answer

292 views

### bounded partitions and bounded signed partitions of integers

Define a bounded signed partition of length $m$ and of bounded height $h$ of an integer $n$ by a relation:
$$n = \pm a_{1} \pm a_{2} \pm a_{3} \pm \dots \pm a_{m}$$ where each $a_{i}$ is a integer in ...

**8**

votes

**0**answers

164 views

### What is known about the number of permissible simplicial complexes given the number of k-cells?

Motivation: I am working on a problem that reduces to finding simplicial complexes given some data (details are unnecessary), but all I have managed to wrangle from my input is the number of cells of ...

**1**

vote

**0**answers

178 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^{...

**14**

votes

**0**answers

572 views

### “Special” meanders

One of the open problems in combinatorics is enumeration of meanders.
Here on MO I only could find them under the heading not-especially-famous-long-open-problems-which-anyone-can-understand.
Since ...

**3**

votes

**1**answer

144 views

### Enumerating matrices function of ranks

Is there an expression/approximate expression for number of real matrices $M\in\{0,1\}^{n\times n}$ of rank $r\leq n$?
Is it known if $M$ is restricted to symmetric/skew-symmetric matrices?
Does ...

**1**

vote

**0**answers

76 views

### What's the complexity of the one sink directed subgraph isomorphism problem?

I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...

**3**

votes

**2**answers

223 views

### Picking codewords that are close

I posted this question in http://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.
Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and ...

**2**

votes

**0**answers

139 views

### Counting number of ways to place bags and marbles inside bags so all bags contain an odd number of marbles

There was a famous trick question posed once in math.stackexchange here. The question can be loosely translated to "Is it possible to place nine marbles into four bags so that each bag has an odd ...

**2**

votes

**0**answers

55 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 ...

**2**

votes

**0**answers

118 views

### Number of degree $k$ functions [closed]

Given a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, there is a real multivariate multilinear polynomial that is associated with in through interpolation.
Example: $AND(x_1,x_2,\dots,x_{n-1},x_n)...

**1**

vote

**0**answers

237 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 ...

**2**

votes

**0**answers

180 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 ...

**1**

vote

**0**answers

151 views

### Distinct Numbers

Let $x_{ij}\in\{0,1\}$ for ${i=1}$ to ${m}$ and for ${j=1}$ to $n$. How many different values does $$\prod_{i=1}^m\sum_{j=1}^nx_{ij}$$ cover?
Is there an $a_{ijk}\in\Bbb R$ (there is a $a_{ijk}\neq0$ ...

**1**

vote

**1**answer

118 views

### A recurrence relation on Catalan numbers

In the classical problem of bracketing $n$ numbers, I know the reponse is $C_{n-1}$. I find this
$$C_{n-1}=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{i+1}\binom{n-i}{i}C_{n-1-i}$$
but I ...

**1**

vote

**1**answer

57 views

### Number of different normalized inner products

Let $u,v\in\{0,1\}^n$ be $0-1$ vectors with $n$ components.
Let $I=\langle u,v \rangle$. Clearly $I$ can take values in $\{0,1,\dots,n-1,n\}$.
How many different values can $$I'=\frac{\langle u,v \...

**4**

votes

**1**answer

118 views

### Determining the number of hamiltonian paths of $K_n-C_n$

I would like to know information regarding the function $h(n)$ where $h(n)$ is the number of hamiltonian cycles the graph $K_n$ has after removing the edges that make up a hamiltonian cycle of $K_n$. ...

**1**

vote

**2**answers

227 views

### On the number of monic polynomials

Let $a,b,c,d\in\Bbb N$ with $c<b$.
Let $N_+(a,b,c,d)$ be the number of monic polynomials $f\in \Bbb Z[x]$of degree $d$ with non-negative coefficients such that $$f(a)=b$$ $$f(0)=c$$
What is the ...