Search Results

Here is a simple recursion that you can use to compute the value. Let $T(n)$ denote the number of tilings of a $2 \times n$ rectangle, using rectangles with integer sides. If no rectangles of height …

Yes, this should be true. Here is an explanation why. Equivalently, we want to assign weights $-1,0,1$ to the edges of $K_{n,n}$ such that the sum of the weights at each vertex is $0$. One way to d …

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given …

The answer is $2^n -n$. Let $I$ be the $n \times n$ identity matrix and let $D$ be a diagonal whose non-zero entries are indexed by $S$. Further suppose that $D$ does not have exactly one zero entry …

I like Jonah Ostroff's proof, but here is an inductive proof (for the heck of it). Let $c(n)$ and $d(n)$ respectively denote the number of connected and disconnected graph on $n$ vertices. Evident …

Using the Combinatorica package in Mathematica, the command NumberOfGraphs$[p,q]$ returns the number of non-isomorphic graphs with $p$ vertices and $q$ edges. If you want to implement this yourself, …

There is a short proof of a stronger result by Norine, Seymour, Thomas, and Wollan that there is an exponential upper bound for every proper minor-closed class. For every proper minor-closed class …

Regarding the algorithmic question, a recent paper of Brent, Pomerance, Purdum, and Webster presents a subquadratic algorithm to compute the number of distinct products $M(n)$ of the $n \times n$ mult …

A generalization of Per Alexandersson's comment is to take the isomorphism class of any graph (or digraph) $G$. There is exactly one such unlabelled graph, so it is obviously harder to count the labe …

Yes. Towards a contradiction, suppose $n \geq 2$ is such that $a_{n+1}$ is prime. Say, $a_{n+1}=p$. Then, $(3n+5)(n+2)p=4(6n+5)(2n+1)a_n$. Evidently, $p$ does not divide $a_n$ since $a_{n+1} > a_n …

Here is a probabilistic 'proof' of the result. Let $\sigma$ be a permutation of $[k]$. Every triple $(\pi, s_1, s_2)$ for $\sigma$ is determined by the common element $a$ of $s_1$ and $s_2$, the pos …

There are $2^{\binom{n}{2}}$ labelled graphs on $n$ vertices. Since isomorphic graphs have isomorphic graphic matroids, $c_n$ is at most the number of non-isomorphic graphs on $n$ vertices (see OEIS …

Here is a proof for when $\sigma$ is the identity permutation on $[k]$. Let $(\pi, s_1, s_2)$ be a valid triple for $k$. For each such triple, we can extend $\pi$ to a permutation $\pi'$ of $[2k+1]$ …

Here is a bijective proof. Label the vertices of $C_{2n}$ as $1, 2, \dots, n, 1', 2', \dots, n'$ in clockwise order and let $M$ be a matching of size $k<n$ in $C_{2n}$. Since $M$ is not a perfect mat …

The following puzzle can be solved by the same technique. A mountain range is a piecewise linear function $f$ defined on a closed interval $[a,b]$ which satisfies $f(a)=f(b)=0$, and $f(c) > 0$ for al …