The tag has no usage guidance.

learn more… | top users | synonyms

14
votes
1answer
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
1answer
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 ...
1
vote
1answer
330 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$...
14
votes
0answers
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 ...
12
votes
0answers
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 ...
9
votes
0answers
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$. ...
8
votes
0answers
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 ...
6
votes
0answers
124 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 ...
6
votes
0answers
217 views

Counting Selections of Entries such having an Extremal Permutation of length n^2+1

Let $S_{n^2+1}$ be permutations of length $n^2+1$. By Erdos-Szekeres Theorem. any $s \in S_{n^2+1}$ would have a monotone subsequence(increasing or decreasing)of length $n+1$. Say a permutation $s$ of ...
5
votes
0answers
177 views

How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such ...
5
votes
0answers
837 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
4
votes
0answers
182 views

Counting Problems where Labeled is Known but Unlabeled is Not

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula. To contrast, counting unlabeled trees is considerably harder....
4
votes
0answers
174 views

When can we determine an $f$-vector or rank-generating function from its unordered list of coefficients?

Let $f_i$ be the number of $i$-dimensional faces in a $d$-dimensional simplicial complex $\Delta $. Recall that the $f$-vector of $\Delta $ is the vector $(f_{-1},f_0,f_1,\dots ,f_d)$ where $f_{-1}=...
3
votes
0answers
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
0answers
128 views

Counting perfect matchings with integrals

Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to ...
3
votes
0answers
102 views

Enumerating simple algebraic groups and their irreducible representations

Motivation Everything is over an algebraically closed field. Given a faithful representation $G \to \textrm{GL}(V)$, one may try to pin down what the group $G$ exactly is (e.g., the in the case of ...
2
votes
0answers
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 ...
2
votes
0answers
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
0answers
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
0answers
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
0answers
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^{...
1
vote
0answers
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 ...
1
vote
0answers
238 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 ...
1
vote
0answers
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
0answers
261 views

An Pure intriguing counting problem of index sets

Hi Guys. The problem here seems like a homework, but I think that it is not that easy.It comes from a theorem I recently proved.The content of the theorem is not important, the issue is that I have no ...
0
votes
0answers
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 ...
0
votes
0answers
57 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 ...