SpanningThrackles: A C++ repository from dchaws

// Copyright (C) 2011 David C. Haws

//This program is free software: you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation, either version 3 of the License, or
//    (at your option) any later version.
//
//    This program is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with this program.  If not, see <http://www.gnu.org/licenses/>.

// See LICENSE

// David Haws
// 7/14/11
// www.davidhaws.net
// https://github.com/dchaws

The program numspanthrackles impliments my recursive function
for the number of spanning thrackles of a complete bipartite graph.

Let f(m,n) = number of spanning thrackles of the complete bipartite graph.

Then, I proved f(m,n) = \sum_{i=0}^{n-1} f(m-1,n-i).

This follows from the fact that if we order the vertices


m *     * m+1

...   

3 *     * m+n-2
2 *     * m+n-1
1 *     * m+n


If we require the edge (1,m+1) and no other edges incident to 1, then this
reduces to f(m-1,n). If we require the edges (1,m+1),(1,m+2) and no other edges
incident to 1, then this reduces to f(m-1,n-1). ...


Note
f(1,1)   = 1
f(2,2)   = 2
f(3,3)   = 6
f(4,4)   = 20
f(5,5)   = 70
f(6,6)   = 252
f(7,7)   = 924
f(8,8)   = 3432
f(9,9)   = 12870
f(10,10) = 48620


The website http://oeis.org/ determines that this sequence is the
Central binomial coefficients: C(2*n,n) = (2*n)!/(n!)^2.


7/24/11

Now have a proof that in fact
f(s,t) = s + t - 2 \choose s -1.



********** TODO **********
7/25/11
Now that I proved that f(s,t) = s + t - 2 \choose s -1, write a program that
will read in a submatrix of K_{s,t} and output either the number of simplices
in the triangulation, i.e., the number of spanning thrackles, or enumerate them
all. Input should be the adjacency matrix.
dchaws/SpanningThrackles
