

A098485


Triangle T(m,k) read by rows, where T(m,k) is the number of ways in which 1<=k<=m positions can be picked in an m X m square array such that their adjacency graph consist of a single component. Two positions (s,t),(u,v) are considered as adjacent, if max(abs(su),abs(tv))<=1.


10



1, 4, 6, 9, 20, 48, 16, 42, 132, 419, 25, 72, 256, 973, 3682, 36, 110, 420, 1747, 7484, 31992, 49, 156, 624, 2741, 12562, 58620, 273556, 64, 210, 868, 3955, 18916, 92912, 462104, 2927505, 81, 272, 1152, 5389, 26546, 134868, 697836, 3644935, 19082018
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Number of ways to mark the numbers on a square board on a lottery play slip such that one connected graphic pattern is formed. For the lottery "mark 6 numbers of 49 on a 7X7 grid of numbers" that is played in many countries, there are T(7,6)=58620 (out of binomial(49,6)=13983816) different combinations of 6 numbers whose graphic pattern on the board forms one connected component.


LINKS

Table of n, a(n) for n=1..45.
John Burkardt, GRAFPACK Graph Computations.
Hugo Pfoertner, Counts of connected components in selected numbers on square lotto boards..
Hugo Pfoertner, Program to analyze the adjacency graph of selections on lotto boards..


EXAMPLE

a(5)=T(3,2)=20 because there are 20 ways to mark two positions in a 3 X 3 square grid such that the two picked positions are either rowwise, columnwise or diagonally adjacent:
XX0...X00...X00...0XX...0X0...0X0...0X0...00X...00X...000
000...X00...0X0...000...X00...0X0...00X...0X0...00X...XX0
000...000...000...000...000...000...000...000...000...000
.........................................................
000...000...000...000...000...000...000...000...000...000
000...X00...0X0...000...X00...0X0...00X...0X0...00X...0XX
XX0...X00...X00...0XX...0X0...0X0...0X0...00X...00X...000


PROG

FORTRAN program: See link.


CROSSREFS

Cf. A090642, A098487 (selections where all marks are isolated from each other), A291716, A291717, A291718, A292152, A292153, A292154, A292155, A292156.
Sequence in context: A220144 A152002 A171127 * A293399 A120712 A115698
Adjacent sequences: A098482 A098483 A098484 * A098486 A098487 A098488


KEYWORD

nonn,tabl


AUTHOR

Hugo Pfoertner, Sep 14 2004


STATUS

approved



