

A333329


Number of winnable configurations in Lights Out game (played on a digraph) summed over every labeled digraph on n nodes.


0



1, 3, 43, 2619, 654811, 662827803, 2699483026843, 44102911693372059, 2886238576935227688091, 756075355087132847491422363, 792522435884210281153847457333403, 3323493099535510709729189614466101940379, 55754039618636998102358059592995073452269940891
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Here a digraph may have at most one self loop (cf. A002416). A winnable configuration is a subset of lit vertices that can be turned off by some toggling sequence. In this version of the game, the digraph D is not necessarily symmetric so that the number of winnable configurations is 2^rank(A^t) where A^t is the transpose of the adjacency matrix of D.
In the limit as n goes to infinity, the probability that a random configuration on a random digraph is winnable is: Sum_{j>=0} (1/2^j) * (Product_{i>=j+1} (12^i))/(Product_{i>=1} (2^i  2^(ji))) = 0.610321...


LINKS

Table of n, a(n) for n=0..12.
A. Giffen and D. Parker, On Generalizing the Lights Out Game and a Generalization of Parity Domination, 2009.
L. Keough and D. Parker, An Extremal Problem for the Neighborhood Lights Out Game, arXiv:1908.03649 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Lights Out Puzzle


FORMULA

a(n) = Sum_{k=0..n} A286331(n,k)*2^k.
a(n) ~ c * 2^(n*(n+1)), where c = 0.610321518048266425924048782090628564983520109965690835927574616905934...  Vaclav Kotesovec, Apr 07 2020


MATHEMATICA

Table[Table[2^k*Product[(2^n  2^i)^2 /(2^k  2^i), {i, 0, k  1}], {k, 0, n}] // Total, {n, 0, 12}]


CROSSREFS

Sequence in context: A307248 A009720 A300873 * A201173 A290777 A309401
Adjacent sequences: A333326 A333327 A333328 * A333330 A333331 A333332


KEYWORD

nonn


AUTHOR

Geoffrey Critzer, Mar 15 2020


STATUS

approved



