

A078993


Starting at the chess position shown, a(n) is the number of ways Black can make n consecutive moves, followed by a checkmate in one move by White.


1



0, 0, 0, 0, 0, 2, 5, 8, 28, 24, 108, 66, 357, 176, 1088, 464, 3160, 1218, 8901, 3192, 24564, 8360, 66836, 21890, 180037, 57312, 481464, 150048, 1280736, 392834, 3393509, 1028456, 8965324, 2692536, 23633532, 7049154, 62197413, 18454928, 163482992, 48315632, 429300136
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

Starting position: White queen at g8, king at h1; Black pawn at h7, king at h6. Black may not move into check.


REFERENCES

Problem composed by N. D. Elkies.


LINKS

Table of n, a(n) for n=0..40.
R. P. Stanley, Extremal [Chess] Problems
Index entries for linear recurrences with constant coefficients, signature (0, 6, 0, 12, 0, 9, 0, 2).


FORMULA

G.f.: sum(a(n)*x^n, n=0..infinity) = x^5*(2+5*x4*x^22*x^3)/((1x^2)*(12*x^2)*(13*x^2+x^4)).
a(2*n) = 3  2^(n+2) + F(2*n+3) for n>0 and a(2*n+1) = 2*(F(2*n1)1) with F(n) the Fibonacci numbers.


EXAMPLE

For n = 5 we have the move orders: (1): 1.Kh5 2.Kh4 3.Kh3 4.h5 5.h4; (2): 1.Kh5 2.Kh4 3.h5 4.Kh3 5.h4; both followed by Qg2# and a(5) = 2.
For n = 6 we have the move orders: (1): 1.Kh5 2.Kh4 3.Kh3 4.h6 5.h5 6.h4; (2): 1.Kh5 2.Kh4 3.h6 4.h5 5.Kh3 6.h4; (3): 1.Kh5 2.Kh4 3.h6 4:Kh3 5.h5 6.h4; (4): 1.Kh5 2.h6 3.Kh4 4.Kh3 5.h5 6.h4; (5): 1.Kh5 2.h6 3.Kh4 4.h5 5.Kh3 6.h4; all followed by Qg2# and a(6) = 5.


CROSSREFS

Cf. A000045 (Fibonacci), A027941 (Fibonacci(2*n+1)1).
Sequence in context: A093365 A209865 A128600 * A066846 A304043 A290594
Adjacent sequences: A078990 A078991 A078992 * A078994 A078995 A078996


KEYWORD

nonn


AUTHOR

N. J. A. Sloane, Jan 18 2003


EXTENSIONS

Formula corrected, examples, formulas and crossrefs added and edited by Johannes W. Meijer, Feb 06 2010 and Feb 08 2010


STATUS

approved



