A287231 -id:A287231 - cp's OEIS frontend

A290847 Number of dominating sets in the n-triangular graph.

1, 7, 57, 973, 32057, 2079427, 267620753, 68649126489, 35172776136145, 36025104013571583, 73784683970720501897, 302228664636911612364581, 2475873390079769597467385417, 40564787539999607393632514635067, 1329227699017403425105119604848703905

Offset: 2

Andrew Howroyd, Aug 12 2017

nonn

A dominating set on the triangular graph corresponds with an edge cover on the complete graph with optionally one vertex removed.

Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Johnson Graph
Eric Weisstein's World of Mathematics, Triangular Graph

Cf. A000085, A006129, A193154, A287231, A287689, A290056, A290716.

b[n_]:=Sum[(-1)^(n - k)*Binomial[n, k]*2^Binomial[k, 2], {k, 0, n}]; a[n_]:=b[n] + n*b[n - 1]; Table[a[n], {n, 2, 20}] (* Indranil Ghosh, Aug 12 2017 *)

\\ here b(n) is A006129
b(n) = sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2));
a(n) = b(n) + n*b(n-1);

from sympy import binomial
def b(n): return sum((-1)**(n - k)*binomial(n, k)*2**binomial(k, 2) for k in range(n + 1))
def a(n): return b(n) + n*b(n - 1)
print([a(n) for n in range(2, 21)]) # Indranil Ghosh, Aug 13 2017

a(n) = A006129(n) + n * A006129(n-1).

a(n) = 2^binomial(n,2) - Sum_{k=2..n} binomial(n,k)*A006129(n-k).

A297565 Number of maximum matchings in the n-triangular graph.

Original entry on oeis.org

1, 3, 8, 144, 47520, 16656192, 3321907200, 21173194506240, 7866775374741504000, 1714731229742768455680000, 149617202324844553489612800000, 1023015704130692419403265343488000000, 822671651496871196689402715812984258560000000, 267398413297417500827783894166564037306456473600000000

Offset: 2

Eric W. Weisstein, Dec 31 2017

nonn

Eric W. Weisstein, Table of n, a(n) for n = 2..18
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Triangular Graph

Cf. A287231, A297484.

\\ groups all orientations of n-complete graph by out degree configuration.
CompleteOrientationsByOutDegrees(n)={ \\ high memory usage and slow for n > 10
local(M=Map());
my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
my(recurse(p, i, q, v, e)=if(i<0, acc(x^e+q, v), my(t=polcoeff(p, i)); for(k=0, t, self()(p, i-1, (t-k+x*k)*x^i+q, binomial(t, k)*v, e+t-k))));
my(iterate(v, k, f)=for(i=1, k, v=f(v)); v);
iterate(Mat([1, 1]), n-1, src->M=Map(); for(i=1, matsize(src)[1], my(p=src[i, 1]); recurse(p, poldegree(p), 0, src[i, 2], 0)); Mat(M))
}
a(n)={
my(v=vector(n\2, n, (2*n)!/(2^n*n!)));
my(c(p)=my(h=(poldegree(p)+1)\2); my(r=n-1-sum(i=1, h, polcoeff(p, 2*i-1))); if(r%2, n*r/2, 1)*if(r<2, 1, v[r\2])*prod(i=1, h, v[i]^(polcoeff(p, 2*i)+polcoeff(p, 2*i-1))));
my(M=CompleteOrientationsByOutDegrees(n-1));
sum(i=1, matsize(M)[1], M[i, 2]*c(M[i, 1]))
} \\ Andrew Howroyd, Jan 02 2018

a(10)-a(15) and offset corrected by Andrew Howroyd, Jan 02 2018

a(16)-a(18) from Eric W. Weisstein, Jan 06-08 2018

cp's OEIS Frontend

A290847 Number of dominating sets in the n-triangular graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula