A389728 Number of positions of the 15-puzzle at a distance of n multi-tile moves from an initial state with the empty square in one of the corners.

1, 6, 18, 54, 162, 486, 1457, 4334, 12568, 36046, 102801, 289534, 808623, 2231878, 6076994, 16288752, 42897301, 110898278, 280452246, 692243746, 1662949961, 3877105392, 8739560829, 18980345944, 39548054325, 78704340919, 148822892020, 265887723109, 445836441561

Offset

0,2

Comments

A multi-tile move shifts a group of tiles so that the empty square moves to anywhere within its existing row, or existing column.

This is a finite sequence ending at a(43) = 16.

Links

Ben Whitmore, Table of n, a(n) for n = 0..43

Oleg Tarakanov, Complete Breadth-First Search of the Sliding Tile Puzzles

Formula

Sum_{i=0..43} a(i) = A264040(4) = 16!/2.

Crossrefs

Cf. A089484, A264040.

Sequence in context: A003208 A174313 A002933 * A016089 A099856 A292295

Adjacent sequences: A389725 A389726 A389727 * A389729 A389730 A389731

Keyword

nonn,fini,full

Author

Ben Whitmore, Jan 09 2026

Status

approved