Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

51
votes
9answers
5k views

Why do Bernoulli numbers arise everywhere?

I have seen Bernoulli numbers many times, and sometimes very surprisingly. They appear in my textbook on complex analysis, in algebraic topology, and of course, number theory. Things like the criteria ...
24
votes
11answers
3k views

What does the generating function $x/(1 - e^{-x})$ count?

Let $x$ be a formal (or small, since the function is analytic) variable, and consider the power series $$ A(x) = \frac{x}{1 - e^{-x}} = \sum_{m=0}^\infty \left( -\sum_{n=1}^\infty ...
0
votes
0answers
18 views

Proving equivalence of two sums involving Krawtchuk polynomials and binomial co-efficients

I seem to have chanced upon a new characterization for Kravchuk polynomials. [http://en.wikipedia.org/wiki/Kravchuk_polynomials]. To begin with, let us define the function $\omega(n,p)$ as [Assuming ...
7
votes
3answers
307 views

Inclusion-preserving bijection between subsets of cardinality k and n-k

Let $n$ be a positive integer. A subset of $[n] := \{1,2,...,n\}$ having $k$ elements will be called a $k$-subset. For $n,k \in \mathbb{N}$ with $k \leq \lfloor n/2 \rfloor$, it is clear that one can ...
26
votes
1answer
694 views

“Nyldon words”: understanding a class of words factorizing the free monoid increasingly

BACKGROUND. Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor ...
10
votes
2answers
636 views

Number of isomorphism types of finite groups

Are there some good asymptotic estimations for the number $F(n)$ of non-isomorphic finite groups of size smaller than $n$?
0
votes
0answers
32 views

Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by $$\frac{k}{2n-k}{2n-k \choose n}.$$ The number of Dyck paths from the ...
29
votes
3answers
2k views

A game of stones

How I arrived at this question is a rather long story having to do with the honors calculus class I am teaching. At this point it's sheer curiosity on my part. Here is the game. ...
18
votes
2answers
1k views

Cops and drunken robbers

Consider a game of cops and robbers on a finite graph. The robber, for reasons left to the imagination, moves entirely randomly: at each step, he moves to a randomly chosen neighbour of his current ...
8
votes
1answer
278 views

Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$. Is it possible that there ...
9
votes
2answers
923 views
+50

How to determine if there exists a non-zero vector in the kernel

If you are given a $0$-$1$ circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel? Could this problem ...
2
votes
1answer
134 views

A question about generalized Dyck words

I am interested in counting the following. How many words using $n-1$ copies of $u$ and ${n \choose 2} - n+1$ copies of $d$ begin with $uu$ and, in general, the $k^{th}$ $u$ is among the first ${k ...
-1
votes
0answers
73 views

Estimating the moments of a random variable

Suppose i wanted to estimate the expectation and variance of a random variable $X$. More over suppose i could write a variable $X$ as a sum of indicator random variables $X=\sum_{i=1}^{k} X_{i}$. Are ...
9
votes
4answers
1k views

Simple/efficient representation of Stirling numbers of the first kind

Stirling numbers of the second kind can be expressed by means of a simple hypergeometric (considering $n$ fixed) sum $$S_2(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n. \qquad (1)$$ ...
0
votes
0answers
166 views

On degrees of polynomials with matching zeros in a subset

Let $S\subsetneq \Bbb R^n$ such that $|S|<\infty$ and for all partitions $S_1$ and $S_2=S\backslash S_1$ of $S$, there exits a multilinear polynomial $h$ such that $h(s)=1-h(s'),\mbox{ }\forall ...
0
votes
0answers
64 views

Asymptotic analysis of a sum of complex summands using integral

I'm trying to find the exact asymptotics of a sum: $$A = \sum^n_{i=0} \begin{pmatrix} 2n \\ i \end{pmatrix} x^{i} y^{2n-i} $$ as $n\rightarrow\infty$. Here $x,y$ are complex numbers, $|x|\leq1, ...
0
votes
0answers
41 views

Bounding a ratio by its complement [on hold]

Given some integers $n > \beta + \alpha, \beta > \alpha$ and $\alpha > 0$, is there a real number $\delta$ for which $\frac{n-\alpha}{n-\beta} \geq (\frac{\beta}{\alpha})^{\delta}$, where ...
0
votes
0answers
61 views

Number of graphs with M edges that does not contain K-clique [on hold]

If we consider the space of graphs $G(n,M)$ where $M$ denotes the number of edges. Is there any known way of calculating the number of graphs within this space that does not contain any k-cliques? Can ...
14
votes
1answer
492 views

Is it possible to define higher cardinal arithmetics

In number theory there are several operators like ‎addition, ‎multiplication and ‎exponentiation defined from ‎$‎‎‎\omega‎‎\times‎‎\omega‎$ ‎to ‎‎$‎‎‎\omega‎$. Each ‎of ‎them ‎is defined as an ...
2
votes
1answer
170 views

Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally: Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...
2
votes
1answer
180 views

Counting Ribbon graphs

Let $G$ be a ribbon graph (sometimes called fat graph) with $v$ vertices and $e$ edges. Furthermore each vertex is of degree $d$. Q) What is the number of $G$ with the above properties? I mean does ...
2
votes
3answers
540 views

Koebe–Andreev–Thurston theorem - where can I find a proof?

Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
12
votes
3answers
589 views

Conjecture regarding closest point inside a discrete ball to a line

I'm a PhD student in image processing, where I've stumbled into a problem that seems to be essentially number theory. I've hunted around online and while I've found many results on similar problems, ...
3
votes
1answer
151 views

Determinant of the oriented adjacency matrix of a tree

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries $$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\ -1 ...
-1
votes
0answers
39 views

How can i simplify the sum of modified partial bell polynomials [closed]

I am trying to prove my conjecture that uses partial bell polynomials as well as modified partial bell polynomials. Putting these bell polynomials into a workable form is a huge problem for me. The ...
16
votes
6answers
2k views

subwords of the fibonacci word

The Fibonacci word is the limit of the sequence of words starting with "0" and satisfying rules $0 \to 01, 1 \to 0$. It's equivalent to have initial conditions $S_0 = 0, S_1 = 01$ and then recursion ...
-1
votes
0answers
58 views

A combinatorial and number theoretical problem [closed]

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. For example,N=10 and the positive integers are ...
0
votes
1answer
111 views

Poisson approximation of random sub-graphs

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...
2
votes
1answer
118 views

A perfect $(n,k)$ shuffle function

Suppose you have a deck of $n$ cards; e.g., $n{=}12$: $$ (1,2,3,4,5,6,7,8,9,10,11,12) \;. $$ Cut the deck into $k$ equal-sized pieces, where $k|n$; e.g., for $k{=}4$, the $12$ cards are partitioned ...
3
votes
0answers
77 views

Partitions with each part dividing the original number

I have a question on partitions that I have not seen being discussed. It deals with those related to divisors. My definition of partitions I am working with is as follow: a sequence of weakly ...
1
vote
0answers
73 views

Reduction argument from a general vertex set V(G) to a prime power in Prof. Keevash's proof on the Existence of Designs

The proof flow of the paper "On the Existence of Designs" by Prof. Keevash as I understand it is the following: -- Reduction from the general case to $V = \mathbb{F}_{p^a}$ (Lemma 6.3) -- Covering ...
0
votes
1answer
174 views

Maximize combinatorial sum for boolean function

I am trying to maximize the function $$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$ for a function ...
13
votes
9answers
1k views

Combinatorial Databases

At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...
0
votes
1answer
42 views

Minimal hypergraphs with respect to separation

Let $H = (V, E)$ be a hypergraph, that is $V$ is a set and $E \subseteq \mathcal{P}(V)$. We say that $H$ is $T_1$ if for $v\neq w$ there are $e_v, e_w \in E$ such that $v\in e_v, w\notin e_v, w\in ...
6
votes
1answer
194 views

To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

This is a cross-post from MSE. In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees. The idea to construct such a ...
8
votes
2answers
366 views

Infected square

I saw the following problem in Mathematical Puzzles from Peter Winkler (very good book, by the way): imagine you infect k cases of a chessboard nxn and the infection spreads to a case if it has at ...
0
votes
0answers
96 views

A question about the duality principle

Suppose $X$ and $Y$ are finite sets and $K:X\times Y\to \mathbb R$ is some function. We get an integral transform from the space of real functions on $X$ to real functions on $Y$ given by ...
0
votes
0answers
76 views

independent subset problems [closed]

I'm interested in the following which i suspect is probably a well studied problem. Given a set $N=\{1,2,...,n\}$ and $M=\{1,2,...,m\}$ consider a map $$f:N\rightarrow 2^{M}$$ (elements of $N$ to ...
9
votes
2answers
247 views

Is there any relationship between the topologies of the clique complex and the independence complex?

Let $G$ be a simple graph on a finite vertex set. The clique complex $X(G)$ is the simplicial complex whose faces are complete subgraphs of $G$, and the independence complex $I(G)$ is the simplicial ...
5
votes
2answers
165 views

Decomposing polyhedral cones into “direct sums” and a polynomial

This question consists of two parts. I'm not breaking it up into two separate ones because posing the second question would essentially require me two rewrite the first one. Also, to some extent, the ...
1
vote
1answer
105 views

NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard. ...
0
votes
1answer
335 views

Tetris in 3D with 5 units [closed]

Background: There are 7 "bricks" used in the game of Tetris. These are the 7 unique combinations of 4 unit squares in which every square shares at least one edge with another square. ("unique" in this ...
22
votes
4answers
15k views

How large is TREE(3)?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...
3
votes
2answers
441 views

Order of a combination when mapping them to whole numbers

You can map whole numbers to combinations when taking them in order. For example, 13 choose 3 would look like: ...
2
votes
0answers
175 views

Minimizing $\{0,1\}$-sequence permutations

Explanation: For a given bit sequence $f$, reposition the bits as to minimize $G$ which can be thought of as a measure of how poorly proportional $f$ is to each of its subsequences. Let $p \in ...
1
vote
1answer
63 views

Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by $(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers, and $i=0,1,\dots,n+1$. Does this simplex admit a regular, ...
2
votes
1answer
820 views

An Intriguing Tapestry: Number triangles, polytopes, Grassmannians, and scattering amplitudes

(Despite seven upvotes, the unproductive, nonconstructive responses and close requests have dominated this entry. Consequently, I've severely reduced the content of this question. Several replies to ...
10
votes
0answers
114 views

Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...
2
votes
2answers
430 views

inverted factorial and trailing zeros problem

First than anything a big Hello for all math fans like me. I've found a problem that is pretty interesting and I can't find the answer. As all of you must know, to counting the trailing zeros of $n$ ...
5
votes
2answers
134 views

Positivity of Ehrhart polynomial coefficients

Are there any results stating that a given family of convex polytopes have Ehrhart polynomials with non-negative coefficients? What methods are available for proving such a property for some family ...