The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A333329 Number of winnable configurations in Lights Out game (played on a digraph) summed over every labeled digraph on n nodes. 0


%S 1,3,43,2619,654811,662827803,2699483026843,44102911693372059,

%T 2886238576935227688091,756075355087132847491422363,

%U 792522435884210281153847457333403,3323493099535510709729189614466101940379,55754039618636998102358059592995073452269940891

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

%C 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.

%C 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} (1-2^i))/(Product_{i>=1} (2^i - 2^(j-i))) = 0.610321...

%H A. Giffen and D. Parker, <a href="https://www.researchgate.net/publication/289241673_On_Generalizing_the_Lights_Out_Game_and_a_Generalization_of_Parity_Domination">On Generalizing the Lights Out Game and a Generalization of Parity Domination</a>, 2009.

%H L. Keough and D. Parker, <a href="https://arxiv.org/abs/1908.03649">An Extremal Problem for the Neighborhood Lights Out Game</a>, arXiv:1908.03649 [math.CO], 2019.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LightsOutPuzzle.html">Lights Out Puzzle</a>

%F a(n) = Sum_{k=0..n} A286331(n,k)*2^k.

%F a(n) ~ c * 2^(n*(n+1)), where c = 0.610321518048266425924048782090628564983520109965690835927574616905934... - _Vaclav Kotesovec_, Apr 07 2020

%t 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}]

%K nonn

%O 0,2

%A _Geoffrey Critzer_, Mar 15 2020

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 12 10:54 EDT 2021. Contains 343821 sequences. (Running on oeis4.)