A098485 - OEIS

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 consists of a single component. Two positions (s,t), (u,v) are considered as adjacent if max(abs(s-u), abs(t-v)) <= 1.

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 7 X 7 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 row-wise, column-wise 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) c 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: A346591 A152002 A171127 * A293399 A120712 A115698

Adjacent sequences: A098482 A098483 A098484 * A098486 A098487 A098488

KEYWORD

nonn,tabl

AUTHOR

Hugo Pfoertner, Sep 14 2004

STATUS

approved