Number of ways to select 1<=k<=n^2 items that are arranged in an n*n matrix such that the selected items are arranged in j connected components. Two positions (i,j),(k,l) are adjacent if max(abs(i-k),abs(j-l))<=1, i.e. there are 8 neighbor positions. Compiled by Hugo Pfoertner http://www.pfoertner.org/ Change history: Oct 15, 2004 Add n=9 for 9X9 table (18days CPU time on a 500MHz Digital Alphastation) Sep 27, 2004 Full table for n=5, select 8 from 9*9 added, 6*6 and 7*7 extended Sep 16, 2004 Extended to more than n selections for n=2,3,4 examples added at end. Sep 14, 2004 Initial version URL of this file: http://www.randomwalk.de/sequences/a098485.txt Example: In a 4*4 matrix there are 288 different ways to pick 3 positions, such that 2 selected positions are adjacent and the third one is isolated (order does not matter). Marked in table as <> Components mXm C(m*m,n) 1 2 3 4 5 6 7 n A098485 (lines <=n) | 1*1 V 1 1 1 (A098497) 2*2 1 4 (4) A098487 2 6 6 (0) A098487 3 4 4 4 1 1 3*3 1 9 (9) A098487 2 36 20 (16) A098487 3 84 48 28 (8) A098487 4 126 85 32 8 1 5 126 102 20 [4] see examples below 6 84 78 [6] 7 36 36 8 9 9 9 1 1 4*4 1 16 (16) 2 120 42 (78) 3 560 132 <288> (140) <-------- <> Example 4 1820 419 780 542 (79) 5 4368 1156 1772 1164 276 6 8008 2658 3174 1778 398 7 11440 4912 4336 1900 292 8 12870 7098 4354 1310 108 9 11440 7844 3048 532 16 10 8008 6498 1400 110 11 4368 3968 392 8 12 1820 1760 60 13 560 556 [4] 14 120 120 15 16 16 16 1 1 5*5 1 25 25 2 300 72 228 3 2300 256 1080 964 4 12650 973 4206 5484 1987 5 53130 3682 14628 21426 11420 1974 6 177100 13028 46230 66530 40654 9680 978 7 480700 41872 130248 172120 105644 26910 3664 242 8 1081575 120045 320066 373602 209242 50809 7164 620 27 9 2042975 301840 674436 670704 318228 68264 8716 750 36 1 10 3268760 655478 1198312 973342 369044 65282 6820 464 18 11 4457400 1212480 1761584 1115576 320988 43400 3244 128 12 5200300 1885767 2102360 988058 204288 19025 802 13 5200300 2437809 2003509 661988 91940 4994 60 14 4457400 2596224 1504532 327938 28038 664 4 15 3268760 2264726 881314 117088 5588 44 16 2042975 1613334 399624 29272 745 17 1081575 937238 139337 4932 68 18 480700 443194 36988 514 4 19 177100 169762 7312 26 20 53130 52104 1026 21 12650 12558 92 22 2300 2296 4 23 300 300 24 25 25 25 1 1 6*6 1 36 36 2 630 110 520 3 7140 420 2800 3920 4 58905 1747 12854 27470 16834 5 376992 7484 55212 138244 133684 42368 6 1947792 31992 224024 594464 686202 348844 62266 7 8347680 132192 860140 2271360 2821564 1712628 498292 51504 8 30260340 517764 3098556 7826424 9833407 6365303 2216880 380214 21792 9 94143280 1899708 10355584 24388340 29638220 19183572 7075148 1457708 141400 3600 10 254186856 6468872 31771578 68466780 77664834 48062208 17503618 3788580 440928 19458 7*7 1 49 49 2 1176 156 1020 3 18424 624 5940 11860 4 211876 2741 29940 93920 85275 5 1906884 12562 143924 545616 807768 397014 6 13983816 58620 669462 2775454 5093678 4166304 1220298 7 85900584 273556 3016696 12966232 26492392 27239634 13427692 2484382 8 450978066 1254351 13147274 56523800 121526737 140206355 87602940 27392416 3324193 8*8 1 64 64 2 2016 210 1806 3 41664 868 11088 29708 4 635376 3955 59352 254598 317471 5 7624512 18916 305724 1617948 3355604 2326320 6 74974368 92912 1541472 9114222 23952938 28239494 12033330 7 621216192 462104 7633620 47843128 143294732 217551216 159829972 44601420 8 4426165368 2927505 37310936 215752067 677085445 1240407020 1321053209 754210717 177418469 9*9 1 81 81 2 3240 272 2968 3 85320 1152 18928 65240 4 1663740 5389 105650 590612 962089 5 25621596 26546 570132 3988054 10949236 10087628 6 324540216 134868 3029654 24029558 84809238 134752240 77784658 7 3477216600 697836 15927472 135978060 555272332 1153569210 1165577872 450193818 8 32164253550 3644935 82865162 737469582 3295213550 8023923025 10720651092 7320944872 1979541332 9 260887834350 19082018 426105396 3868284314 18272064136 49193848772 77708736916 70709057860 34035484296 6655170642 Examples: 3*3 board: n=5, 3 components: X0X...X0X...X0X...XXX 000...00X...X00...000 XXX...X0X...X0X...X0X n=6, 2 components XXX...X0X...XXX...X0X...X0X...XXX 000...X0X...X00...00X...X00...00X XXX...X0X...X0X...XXX...XXX...X0X 4*4 board n=13, 2 components X0XX...XX0X...XXXX...XXXX 00XX...XX00...XXXX...XXXX XXXX...XXXX...00XX...XX00 XXXX...XXXX...X0XX...XX0X