Gordon F. Royle - cp's OEIS frontend

User: Gordon F. Royle

Gordon F. Royle's wiki page.

Gordon F. Royle has authored 18 sequences. Here are the ten most recent ones:

A132043 Number of bitransversal (transversal and dual transversal) matroids on n unlabeled elements.

Original entry on oeis.org

2, 4, 8, 17, 38, 95, 268, 917, 4086

Offset: 1

Gordon F. Royle, Oct 30 2007

nonn

A transversal matroid is a matroid whose independent sets are the partial transversals of a family of subsets of [1..n], while a bitransversal matroid is a transversal matroid whose dual is transversal. The principal (or fundamental) transversal matroids enumerated by A049312 form an important subset of bitransversal matroids.

Jensen, P. M., Binary fundamental matroids. Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 281-296, Colloq. Math. Soc. Janos Bolyai, 25, North-Holland, Amsterdam-New York, 1981

Cf. A049312.

A128953 Number of 3-connected bipartite graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 6, 12, 85, 471, 5373, 75145, 1543382, 41554738

Offset: 6

Gordon F. Royle, May 10 2007

			a(6) = 1 because the complete bipartite graph K_{3,3} is the only 3-connected bipartite graph on 6 vertices.

Cf. A005142.

A122113 Number of pairwise non-isomorphic biconnected planar bipartite graphs on n vertices.

Original entry on oeis.org

1, 1, 4, 6, 28, 77, 386, 1787, 10354, 62040, 404093, 2725484, 19078248

Offset: 4

Gordon F. Royle, Oct 18 2006

Biconnected means "at least 2-connected". The corresponding sequence for 3-connected bipartite planar graph is A007028, where the term "polyhedral graph" is used as shorthand for "3-connected planar graph".

			a(4) = 1 because the 4-cycle is the only planar and bipartite graph on 4 vertices that is at least 2-connected and a(5) = 1 because the complete bipartite graph K2,3 is the only such graph on 5 vertices.

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.

Cf. A007028.

a(15)-a(16) added using tinygraph by Falk Hüffner, May 09 2019

A122423 Number of unigraphic degree sequences among all graphs (connected or otherwise) on n vertices.

Original entry on oeis.org

1, 2, 4, 11, 28, 72, 170, 407, 956, 2252

Offset: 1

Gordon F. Royle, Sep 03 2006

A degree sequence is unigraphic if there is only one graph (up to isomorphism) with that degree sequence.

Michael Koren, Pairs of Sequences with a Unique Realization by Bipartite Graphs, Journal of Combinatorial Theory B, 21, 224-234, 1976.
Michael Koren, Sequences with a Unique Realization by Simple Graphs, Journal of Combinatorial Theory B, 21, 234-244, 1976.
Shuo-Yen R Li, Graphic Sequences with Unique Realizations, Journal of Combinatorial Theory B, 19, 42-68, 1975.
Eric Weisstein's World of Mathematics, Unigraphic Graph.

Cf. A365548 (number of unigraphic graphs on n nodes that are connected).

Cf. A309757 (number of connected graphs that have distinct degree sequences among all connected graphs).

A108941 Maximum number of spanning trees in a cubic graph on 2n vertices.

Original entry on oeis.org

16, 81, 392, 2000, 9800, 50421, 248832, 1265625, 6422000, 32710656

Offset: 2

Gordon F. Royle, Jul 20 2005

a(5) = 2000 is realized by Petersen graph, a(7) = 50421 is realized by the Heawood graph.

			When n=2, the only cubic graph on 2n vertices is the complete graph K4 with 16 spanning trees.

Cf. A020871.

A092337 Triangle read by rows: T(n,m) = number of 3-uniform hypergraphs with m hyperedges on n unlabeled nodes, where 0 <= m <= C(n,3).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 1, 3, 7, 21, 43, 94, 161, 249, 312, 352, 312, 249, 161, 94, 43, 21, 7, 3, 1, 1, 1, 1, 3, 10, 38, 137, 509, 1760, 5557, 15709, 39433, 87659, 172933, 303277, 473827, 660950, 824410, 920446, 920446, 824410, 660950

Offset: 3

Gordon F. Royle, Mar 18 2004

A 3-uniform hypergraph is a set of 3-subsets of the nodes with isomorphism determined by permutations of the node set. The numbers are calculated using Polya enumeration from the cycle index of the symmetric group Sym(n) in its action on 3-subsets of an n-set, which can easily be computed by MAGMA or GAP. A000665 is the sum of each row of the triangle.

			Triangle T(n,m) begins:
1, 1;
1, 1, 1, 1,  1;
1, 1, 2, 4,  6,  6,  6,   4,   2,   1,   1;
1, 1, 3, 7, 21, 43, 94, 161, 249, 312, 352, 312, 249, 161, 94, 43, 21, 7, 3, 1, 1;

Edgar M. Palmer, On the number of n-plexes, Discrete Math., 6 (1973), 377-390.

Cf. A000665, A051240.

Needs["Combinatorica`"]; Table[A = Subsets[Range[n], {3}];
  CoefficientList[CycleIndex[Replace[Map[Sort,System`PermutationReplace[A, SymmetricGroup[n]], {2}],Table[A[[i]] -> i, {i, 1, Length[A]}], 2], s] /.
Table[s[i] -> 1 + x^i, {i, 1, Binomial[n, 3]}], x], {n,3,7}] // Grid (* Geoffrey Critzer, Oct 28 2015 *)

A087981 E.g.f.: exp(-2*x) / (1-x)^2.

Original entry on oeis.org

1, 0, 2, 4, 24, 128, 880, 6816, 60032, 589312, 6384384, 75630080, 972387328, 13483769856, 200571078656, 3185540657152, 53800242216960, 962741176500224, 18195808235880448, 362183230599856128, 7572922094360723456, 165945771111208714240, 3802923921298533384192, 90965940197460917878784, 2267151124921333646884864

Offset: 0

Gordon F. Royle, Oct 28 2003

Permanent of an (n+1) X (n+1) (+1, -1)-matrix with exactly n -1's on the diagonal and 1's everywhere else.
It is conjectured by Kräuter and Seifter that for n >= 5 a(n-1) is the maximal possible value for the permanent of a nonsingular n X n (+1, -1)-matrix. I do not know for which values of n this has been confirmed - compare A087982. - N. J. A. Sloane
The Kräuter conjecture on permanents is true (see Budrevich and Guterman). - Sergei Shteiner, Jan 17 2020
The maximal possible value for the permanent of a singular n X n (+1, -1)-matrix is obviously n!.
Degree of the "hyperdeterminant" of a multilinear polynomial on (\P^1(\C))^n, or equivalently of an element of (\C^2)^{⊗ n}: see Gelfand, Kapranov and Zelevinsky. - Eric Rains, Mar 15 2004
(-1)^n * a(n) = Polynomials in A010027 evaluated at -1. - Ralf Stephan, Dec 15 2004
a(n) is the number of n X n (-1, 0, 1)-matrices containing in every row and every column exactly one -1 and one 1 such that the main diagonal does not contain 0's. - Vladimir Shevelev, Apr 01 2010
a(n) is the number of colored permutations with no fixed points of n elements where each cycle is one of two colors. - Michael Somos, Jan 19 2011
Binomial transform is A000255. Hankel transform is A059332. - Paul Barry, Apr 11 2011
Exponential self-convolution of subfactorials (A000166). - Vladimir Reshetnikov, Oct 07 2016

			G.f. = 1 + 2*x^2 + 4*x^3 + 24*x^4 + 128*x^5 + 880*x^6 + 6816*x^7 + ...
Since a(1) = 0, then, for n = 2, we have a(2) = -(-2)^3/4 = 2; further, for n = 3, we find a(3) = (3*6/5)*2 - (-2)^4/5 = 36/5 - 16/5 = 4. - _Vladimir Shevelev_, Apr 01 2010
a(4) = 24 because there are 6 derangements with one 4-cycle with 2^1 ways to color each derangement and 3 derangements with two 2-cycles with 2^2 ways to color each derangement. - _Michael Somos_, Jan 19 2011

I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkhauser, 1994; see Corollary 2.10 in Chapter 14 (p. 457).

T. D. Noe, Table of n, a(n) for n = 0..100
Mikhail V. Budrevich and Alexander E. Guterman, Kräuter conjecture on permanents is true, arXiv:1810.04439 [math.CO], 2018.
Steven Finch, Rounds, Color, Parity, Squares, arXiv:2111.14487 [math.CO], 2021.
I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Hyperdeterminants, Advances in Mathematics 96(2) (1992), 226-263; see Corollary 3.10 (p. 246).
Arnold R. Kräuter, Permanenten - Ein kurzer Überblick, Séminaire Lotharingien de Combinatoire, B09b (1983), 34 pp.
Arnold R. Kräuter and Norbert Seifter, Some properties of the permanent of (1,-1)-matrices, Linear and Multilinear Algebra 15 (1984), 207-223.
Norbert Seifter, Upper bounds for permanents of (1,-1)-matrices, Israel J. Math. 48 (1984), 69-78.
Edward Tzu-Hsia Wang, On permanents of (1,-1)-matrices, Israel J. Math. 18 (1974), 353-361.
Wikipedia, Hyperdeterminant
Index entries for sequences related to binary matrices

Cf. A087982, A087983, A176097.

Cf. A000007, A000023, A000166, A024000, A137775. - Michael Somos, Jan 19 2011

seq(simplify(KummerU(-n, -n-1, -2)), n = 0..24); # Peter Luschny, May 10 2022

Range[0, 20]! CoefficientList[Series[Exp[-2 x]/(1 - x)^2, {x, 0, 20}], x]
Table[(-2)^n HypergeometricPFQ[{2, -n}, {}, 1/2], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 07 2016 *)

{a(n) = if( n<0, 0, n! * polcoeff( exp( -2 * x + x * O(x^n) ) / ( 1 - x )^2, n ) )} /* Michael Somos, Jan 19 2011 */

Krauter and Seifter prove that the permanent of an n X n {-1, 1} matrix is divisible by 2^{n - [log_2(n)] - 1}.
Let c(n) be the permanent of the {-1, +1}-matrix of order n X n with n diagonal -1's only. Let a(n) be the permanent of the {-1, +1}-matrix of order (n+1) X (n+1) with n diagonal -1's only. Then by expanding along the first row (like determinant, but with no sign) we get c(n+1) = -c(n) + n a(n-1), a(n) = c(n) + n a(n-1), with c(2) = 2, a(2) = 2. {c(n)} has e.g.f. exp(-2x)/(1-x), see A000023. Also a(n) = c(n+1) + 2*c(n).
The following 4 formulas hold: a(n) = Sum_{k = 0..n} C(n, k)*D_k*D_{n-k}, where D_n = A000166(n); a(n) = n!*Sum_{j = 0..n} (n+1-j)*(-2)^j/j!; a(0) = 1, a(1) = 0 and, for n > 0, a(n+1) = n*(a(n) + 2*a(n-1)); a(0) = 1 and, for n > 0, a(n) = (n*(n+3)/(n+2))*a(n-1) - (-2)^(n+1)/(n+2). - Vladimir Shevelev, Apr 01 2010 [edited by Michael Somos, Jan 19 2011]
G.f.: 1/(1-2x^2/(1-2x-6x^2/(1-4x-12x^2/(1-6x-20x^2/(1-.../(1-2n*x-(n+1)(n+2)x^2/(1-... (continued fraction). - Paul Barry, Apr 11 2011
E.g.f.: 1/U(0) where U(k)=  1 - 2*x/( 1 + x/(2 - x - 4/( 2 + x*(k+1)/U(k+1)))) ; (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Oct 28 2012
G.f.: 1/Q(0), where Q(k) = 1 + 2*x - x*(k+2)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 22 2013
G.f.: 1/Q(0) where Q(k) = 1 - 2*k*x - x^2*(k + 1)*(k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 10 2013
G.f.: S(x)/x - 1/x = G(0)/x - 1/x, where S(x) = sum(k >= 0, k!*(x/(1+2*x))^k  ), G(k) = 1 + (2*k + 1)*x/( 1+2*x - 2*x*(1+2*x)*(k+1)/(2*x*(k+1) + (1+2*x)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 26 2013
a(n) = (-2)^n*hypergeom([2, -n], [], 1/2) = 4*(-2)^n*(1 - 2*hypergeom([1, -n-3], [], 1/2))/(n^2+3*n+2) = (4*(-2)^n + Gamma(n+4, -2)*exp(-2))/(n^2+3*n+2). - Vladimir Reshetnikov, Oct 07 2016
a(n) ~ sqrt(2*Pi) * n^(n+3/2) / exp(n+2). - Vaclav Kotesovec, Oct 08 2016
a(n) = KummerU(-n, -n - 1, -2). - Peter Luschny, May 10 2022

More terms from Jaap Spies, Oct 28 2003
Further terms from Gordon F. Royle, Oct 29 2003
Definition via e.g.f. from Eric Rains, Mar 15 2004
Changed the offset and terms to correspond to e.g.f, Michael Somos, Jan 19 2011

A084657 Number of unlabeled 2-connected claw-free cubic graphs on 2n vertices.

Original entry on oeis.org

0, 1, 1, 1, 1, 3, 2, 4, 8, 10, 16, 34, 51, 99, 198

Offset: 1

Gordon F. Royle, Jun 02 2003

nonn

Gordon Royle, Combinatorial Data

Cf. A084657, A058929.

A084658 Number of unlabeled 3-connected claw-free cubic graphs on 2n vertices.

Original entry on oeis.org

0, 1, 1, 0, 0, 1, 0, 0, 2, 0, 0, 4, 0, 0, 14

Offset: 1

Gordon F. Royle, Jun 02 2003

nonn

Gordon Royle, Combinatorial Data

Cf. A084657, A058931.

A084659 Number of labeled claw-free cubic graphs on 2n nodes (not necessarily connected).

Original entry on oeis.org

1, 0, 1, 60, 2555, 466200, 62791575, 14536021500, 8381453705625, 3284480337138000, 1942832950684250625, 2143745512307546647500, 1743194710893176557891875, 2022583790860881671548125000

Offset: 0

Gordon F. Royle, Jun 02 2003

nonn

R. J. Mathar, Table of n, a(n) for n = 0..26 Nov 26 2018
B. D. McKay, Edgar M. Palmer, Ronald C. Read and Robert W. Robinson. The asymptotic number of claw-free cubic graphs, Discrete Math., 272 (2003), 107-118.
Edgar M. Palmer, Ronald C. Read and Robert W. Robinson. Counting claw-free cubic graphs, SIAM J. Discrete Math. 16 (2002), 65-73.

Cf. A057848.

cfc[0] := 1; cfc[1] := 0; cfc[n+1] := (6*n-5)*binomial(2*n+1,3)*cfc[n-1] + 60*(2*n^2-7)*binomial(2*n+1,5)*cfc[n-2] + 420*(12*n-31)*binomial(2*n+1,7)*cfc[n-3] - 60480*(4*n-19)*binomial(2*n+1,9)*cfc[n-4] - 3326400*(6*n^2-54*n+127)*binomial(2*n+1,11)*cfc[n-5] - 172972800*(9*n^2-108*n+347)*binomial(2*n+1,13)*cfc[n-6] - 54486432000*(n-1)*binomial(2*n+1,15)*cfc[n-7] + 59281238016000*(n-7)*binomial(2*n+1,17)*cfc[n-8] + 422378820864000*(18*n-97)*binomial(2*n+1,19)*cfc[n-9] + 6563766876226560000*binomial(2*n+1,21)*cfc[n-10] + 673229602575129600000*binomial(2*n+1,23)*cfc[n-11];

Recurrence is given in Maple code below. For asymptotics see the 2003 paper.

cp's OEIS Frontend

User: Gordon F. Royle

A132043 Number of bitransversal (transversal and dual transversal) matroids on n unlabeled elements.

Views

Author

Keywords

Comments

References

Crossrefs

A128953 Number of 3-connected bipartite graphs on n unlabeled nodes.

Views

Author

Keywords

Examples

Crossrefs

A122113 Number of pairwise non-isomorphic biconnected planar bipartite graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A122423 Number of unigraphic degree sequences among all graphs (connected or otherwise) on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

A108941 Maximum number of spanning trees in a cubic graph on 2n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

A092337 Triangle read by rows: T(n,m) = number of 3-uniform hypergraphs with m hyperedges on n unlabeled nodes, where 0 <= m <= C(n,3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A087981 E.g.f.: exp(-2*x) / (1-x)^2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A084657 Number of unlabeled 2-connected claw-free cubic graphs on 2n vertices.

Views

Author

Keywords

Links

Crossrefs

A084658 Number of unlabeled 3-connected claw-free cubic graphs on 2n vertices.

Views

Author

Keywords

Links

Crossrefs

A084659 Number of labeled claw-free cubic graphs on 2n nodes (not necessarily connected).

Views

Author

Keywords

Links