A183109 -id:A183109 - cp's OEIS frontend

A289196 Number of connected dominating sets in the n X n rook graph.

1, 9, 325, 51465, 30331861, 66273667449, 556170787050565, 18374555799096912585, 2414861959450912233421141, 1267166974391002542218440851129, 2658149210218078451926703769353958085, 22299979556058598891936157095746389850916425

Offset: 1

Eric W. Weisstein, Jun 28 2017

nonn

A set of vertices in the n X n rook graph can be represented as a n X n binary matrix. The vertex set will be dominating if either every row contains a 1 or every column contains a 1. - Andrew Howroyd, Jul 18 2017

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A360875.

Cf. A183109, A262307, A286189, A287065.

(* b = A183109, T = A262307 *) b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}]; T[, 1] = T[1, ] = 1; T[m_, n_] := T[m, n] = b[m, n] - Sum[T[i, j]*b[m-i, n-j]*Binomial[m-1, i-1]*Binomial[n, j], {i, 1, m-1}, {j, 1, n-1}]; a[n_] := T[n, n] + 2*Sum[ Binomial[n, k]*T[n, k], {k, 1, n-1}]; Array[a, 12] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)

G(N)={S=matrix(N, N); T=matrix(N, N); U=matrix(N, N);
\\ S is A183109, T is A262307, U is m X n variant of this sequence.
for(m=1, N, for(n=1, N,
S[m, n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
T[m, n]=S[m, n]-sum(i=1, m-1, sum(j=1, n-1, T[i, j]*S[m-i, n-j]*binomial(m-1, i-1)*binomial(n, j)));
U[m, n]=sum(i=1, m, binomial(m, i)*T[i, n])+sum(j=1, n, binomial(n,j)*T[m, j])-T[m,n] )); U}
a(n)=G(n)[n, n]; \\ Andrew Howroyd, Jul 18 2017

a(n) = A262307(n,n) + 2*Sum_{k=1..n-1} binomial(n,k) * A262307(n,k). - Andrew Howroyd, Jul 18 2017

Terms a(6) and beyond from Andrew Howroyd, Jul 18 2017

A297008 Number of edge covers in the complete tripartite graph K_{n,n,n}.

Original entry on oeis.org

4, 2902, 117207580, 268752741193822, 37231937318464496521924, 323097476641999571450657507823382, 178177528846515370073473806783721111760309500, 6274803675843247716007930604166972482973014660984656159102

Offset: 1

Eric W. Weisstein, Dec 23 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..25
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Eric Weisstein's World of Mathematics, Edge Cover

Cf. A048291, A183109.

b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*If[n == 0, 1, (2^(m - j) - 1)^n], {j, 0, m}];
c[n_, s_] := Sum[Binomial[n, k]*Binomial[n, s - k]*b[k, s - k], {k, Max[0, s - n], Min[n, s]}];
a[n_] := Sum[c[n, 2*n - i]*Sum[(-1)^j*Binomial[i, j]*(2^(2*n - j) - 1)^n, {j, 0, i}], {i, 0, 2 n}];
Array[a, 10] (* Jean-François Alcover, Dec 27 2017, after Andrew Howroyd *)

\\ here b(m,n) is A183109.
b(m, n)={sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n)}
c(n, s)={sum(k=max(0, s-n), min(n, s),binomial(n, k)*binomial(n, s-k)*b(k, s-k))}
a(n)={sum(i=0, 2*n, c(n, 2*n-i)*sum(j=0, i, (-1)^j*binomial(i, j)*(2^(2*n - j) - 1)^n))} \\ Andrew Howroyd, Dec 24 2017

Terms a(4) and beyond from Andrew Howroyd, Dec 24 2017

A225783 Triangle read by rows: T(n,m) is the number of n X m binary (0,1) matrices that represent perfect parity patterns.

Original entry on oeis.org

0, 1, 0, 0, 2, 0, 0, 0, 0, 15, 0, 0, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 112, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0

Offset: 1

R. J. Mathar, Jun 13 2014

An n X m matrix of zeros and ones is perfect if no row or column consists entirely of zeros (as counted in A183109). It is a parity pattern if every 0 is adjacent (vertically or horizontally) to an even number of 1s and every 1 is adjacent to an odd number of 1s.

			The T(5,3) = 4 perfect parity 5 X 3 patterns are
0 0 1
0 1 1
1 0 1
1 1 0
1 0 0
------
0 1 1
1 0 0
1 0 1
0 0 1
1 1 0
--------
1 0 0
1 1 0
1 0 1
0 1 1
0 0 1
--------
1 1 0
0 0 1
1 0 1
1 0 0
0 1 1

R. J. Mathar, Table of n, a(n) for n = 1..106
R. Chapman, D. E. Knuth, Problem 11243, Perfect parity patterns, Am. Math. Monthly 115 (7) (2008) p 668.
R. J. Mathar, Discussion and JAVA source code

A283654 Triangle T(n,m) read by rows: number of n X m binary matrices with no rows or columns in which all entries are the same (n >= 1, 1 <= m <= n).

Original entry on oeis.org

0, 0, 2, 0, 6, 102, 0, 14, 906, 22874, 0, 30, 6510, 417810, 17633670, 0, 62, 42666, 6644714, 622433730, 46959933962, 0, 126, 267582, 99044946, 20218802310, 3204360965106, 451575174961302, 0, 254, 1641786, 1430529674, 630917888610, 208308918928634, 60134626974122946, 16271255119687320314

Offset: 1

Robert FERREOL, Mar 14 2017

			The T(2,3)=6 matrices are
1 0 1
0 1 0
and the matrices obtained by permutations of rows and columns.
First values in triangle
0;
0, 2;
0, 6, 102;
0, 14, 906, 22874;
0, 30, 6510, 417810, 17633670;
0, 62, 42666, 6644714, 622433730, 46959933962;
0, 126, 267582, 99044946, 20218802310, 3204360965106, 451575174961302;

Diagonal gives A283624.

Cf. A183109.

T0:=(n,m)->add((-1)^(m+k)*binomial(n,k)*(2^k-1)^m, k=0..n):
T:=(n,m)->2*T0(n,m)+2^(n*m)+(2^n-2)^m+(2^m-2)^n-2*(2^m-1)^n-2*(2^n-1)^m:
seq(seq(T(n,m), m=1..n),n=1..10);

T[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}]; Flatten[Table[2*T[n, m] + 2^(n*m) + (2^n - 2)^m + (2^m - 2)^n - 2*(2^m - 1)^n - 2*(2^n - 1)^m, {n, 10}, {m, n}]] (* Indranil Ghosh, Mar 14 2017 *)

T(n, m) = sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
tabl(nn) = {for(n=1, nn, for(m=1, n, print1(2*T(n,m) + 2^(n*m) + (2^n - 2)^m + (2^m - 2)^n - 2*(2^m - 1)^n - 2*(2^n - 1)^m,", ");); print(););};
tabl(10); \\ Indranil Ghosh, Mar 14 2017

import math
f=math.factorial
def C(n,r): return f(n)//f(r)//f(n - r)
def T(n,m): return sum([(-1)**j*C(m,j)*(2**(m - j) - 1)**n for j in range (0, m+1)])
i=1
for n in range(1,11):
    for m in range(1, n+1):
        print(str(i)+" "+str(2*T(n, m) + 2**(n*m) + (2**n - 2)**m + (2**m - 2)**n - 2*(2**m - 1)**n - 2*(2**n - 1)**m))
        i+=1 # Indranil Ghosh, Mar 14 2017

T(n,m) = T(m,n) = 2*A183109(n,m) + 2^(n*m) + (2^n-2)^m + (2^m-2)^n - 2*(2^m-1)^n - 2*(2^n-1)^m.

T(n,1)=0, T(n,2)=2^n-2, T(n,3)=6^n-6*(3^n-2^n).

cp's OEIS Frontend

A289196 Number of connected dominating sets in the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A297008 Number of edge covers in the complete tripartite graph K_{n,n,n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A225783 Triangle read by rows: T(n,m) is the number of n X m binary (0,1) matrices that represent perfect parity patterns.

Views

Author

Keywords

Comments

Examples

Links

A283654 Triangle T(n,m) read by rows: number of n X m binary matrices with no rows or columns in which all entries are the same (n >= 1, 1 <= m <= n).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula