A078469 -id:A078469 - cp's OEIS frontend

A108808 Number of compositions of grid graph G_{3,n} = P_3 X P_n.

4, 74, 1434, 27780, 538150, 10424872, 201947094, 3912050356, 75782907270, 1468040672696, 28438383992230, 550898690444420, 10671821831261942, 206730898391393192, 4004720564629102582, 77578083032366404308, 1502816206487087179878, 29112043791259796460440

Offset: 1

N. J. A. Sloane, Jul 09 2005

Reddy, V. and Skiena, S. "Frequencies of Large Distances in Integer Lattices." Technical Report, Department of Computer Science. Stony Brook, NY: State University of New York, Stony Brook, 1989. [Background]
Skiena, S. "Grid Graphs." Section 4.2.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 147-148, 1990. [Background]

Robert Israel, Table of n, a(n) for n = 1..769
J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart. 42 (2004), 222-230.
Frank Simon, Algebraic Methods for Computing the Reliability of Networks, Dissertation, Doctor Rerum Naturalium (Dr. rer. nat.), Fakultät Mathematik und Naturwissenschaften der Technischen Universität Dresden, 2012, Table 6.12. - From _N. J. A. Sloane_, Jan 04 2013
Eric Weisstein's World of Mathematics, Grid Graph. [Background]
Index entries for linear recurrences with constant coefficients, signature (23,-75,91,6,-4).

Cf. A078469, A110476, A221157 (Grid graph G_{4,n}).

z:= <1|1|1|1|1|1>: w:= <1,1,0,1,0,1>:
M:= Matrix([[ 2, 3, 3, 3, 4, 5 ],
[ 3, 4, 5, 5, 6, 6 ],
[ 1, 0, 2, 0, 0, 0 ],
[ 3, 5, 5, 4, 6, 6 ],
[ 2, 1, 4, 1, 2, 0 ],
[ 2, 5, 2, 5, 6, 8 ]]):
seq(z . M^i . w, i=0..31); # Robert Israel, Dec 03 2015

From Brian Kell, Oct 20 2008: (Start)
a(n) = z * M^(n-1) * w,
where
z is the 1 x 6 row vector [ 1 ... 1 ],
M is the 6 x 6 matrix
[[ 2, 3, 3, 3, 4, 5 ],
[ 3, 4, 5, 5, 6, 6 ],
[ 1, 0, 2, 0, 0, 0 ],
[ 3, 5, 5, 4, 6, 6 ],
[ 2, 1, 4, 1, 2, 0 ],
[ 2, 5, 2, 5, 6, 8 ]],
and w is the 6 x 1 column vector
[[ 1 ],
[ 1 ],
[ 0 ],
[ 1 ],
[ 0 ],
[ 1 ]] (End)
G.f.: 2*x*(x-2)*(x^3-6*x^2+4*x-1) / (4*x^5-6*x^4-91*x^3+75*x^2-23*x+1). - Colin Barker, May 14 2013

a(4) corrected and a(5)-a(7) computed by Brian Kell, May 20 2008
a(8) - a(11) from Brian Kell, Oct 20 2008
a(12)-a(18) added from Frank Simon's thesis by N. J. A. Sloane, Jan 04 2013

A110476 Table of number of partitions of an m X n rectangle, read by descending antidiagonals.

Original entry on oeis.org

1, 2, 2, 4, 12, 4, 8, 74, 74, 8, 16, 456, 1434, 456, 16, 32, 2810, 27780, 27780, 2810, 32, 64, 17316, 538150, 1691690, 538150, 17316, 64, 128, 106706, 10424872, 103015508, 103015508, 10424872, 106706, 128, 256, 657552, 201947094, 6273056950

Offset: 1

Hugo van der Sanden, Sep 08 2005

We count the partitions of the rectangle into regions of orthogonally connected unit squares. a(2, 2) = 12 comprising one partition of the 2 X 2 region; 4 partitions into a 3-square 'L' shape and an isolated corner; 2 partitions into two 1 X 2 bricks; 4 partitions into a 1 X 2 brick and two isolated squares; and 1 partition into four isolated squares.

			Array A(m,n) (with rows m >= 1 and columns n >= 1) begins
    1,      2,        4,         8,        16,       32,     64, 128, ...
    2,     12,       74,       456,      2810,    17316, 106706, ...
    4,     74,     1434,     27780,    538150, 10424872, ...
    8,    456,    27780,   1691690, 103015508, ...
   16,   2810,   538150, 103015508, ...
   32,  17316, 10424872, ...
   64, 106706, ...
  128, ...
  ...

Walter Trump, Table of n, a(n) for n = 1..220 (first 40 terms from Hugo van der Sanden).
Brian Kell, Values for m+n < 16 [except (7,7), (7,8) and (8,7)]
A. Knopfmacher and M. E. Mays, Graph compositions I: Basic enumeration, Integers, 1 (2001), 1-11. [From _Brian Kell_, Oct 21 2008]
Yulka Lipkova, Miso Forisek, Tom Zathurecky, and Davidko Pal, Delicious cake. [From _Brian Kell_, Oct 21 2008]
J. N. Ridley and M. E. Mays, Compositions of unions of graphs, Fib. Quart., 42 (2004), 222-230. [From _Brian Kell_, Oct 21 2008]
Frank Simon, Algebraic Methods for Computing the Reliability of Networks, Dissertation, Doctor Rerum Naturalium (Dr. rer. nat.), Fakultät Mathematik und Naturwissenschaften der Technischen Universität Dresden, 2012. - From _N. J. A. Sloane_, Jan 04 2013
F. Simon, P. Tittmann and M. Trinks, Counting Connected Set Partitions of Graphs, Electron. J. Combin., 18(1) (2010), #P14, 12pp.

Cf. A000041, A000079, A078469, A221157.

Cf. A108808, A145835. - Brian Kell, Oct 21 2008

a(m,n) = a(n,m).
a(1,n) = 2^(n-1) = a(n,1).
a(2,n) = A078469(n) = a(n,2).
From Petros Hadjicostas, Feb 27 2021: (Start)
The following two equations seem to follow from the work of Brian Kell and Frank Simon:
a(3,n) = A108808(n) = a(n,3).
a(4,n) = A221157(n) = a(n,4). (End)

Corrected by Chuck Carroll (chuck(AT)chuckcarroll.org), Jun 06 2006

Name edited by Michel Marcus, Jul 02 2020

A152113 A001333 with terms repeated.

Original entry on oeis.org

1, 1, 3, 3, 7, 7, 17, 17, 41, 41, 99, 99, 239, 239, 577, 577, 1393, 1393, 3363, 3363, 8119, 8119, 19601, 19601, 47321, 47321, 114243, 114243, 275807, 275807, 665857, 665857, 1607521, 1607521, 3880899, 3880899, 9369319, 9369319, 22619537, 22619537, 54608393

Offset: 1

N. J. A. Sloane, Sep 21 2009

Suggested by an email message from Hugo van der Sanden, Mar 23 2009, who says: Consider the partitions of a 2 X n rectangle into connected pieces consisting of unit squares cut along lattice lines. Then a(n) is the number of distinct pieces with rotational symmetry that extend to opposite corners.

a(n+2) is the number of palindromic words of length n on a 3-letter alphabet {a,b,c} which do not contain the "ab" subword. See A001906 for the words of length n on a 3-letter alphabet without "ab" subword but not necessarily palindromic. Example length 1: "a" or "b" or "c". Example length 2: "aa", "bb", "cc". Example length 3: There are 9 palindromic words but "aba" and "bab" are not admitted and only 7 remain. - R. J. Mathar, Jul 10 2019

			The pieces illustrating a(3) = 3 are:
 AAA BB. .CC
 AAA .BB CC.

Index entries for linear recurrences with constant coefficients, signature (0,2,0,1).

Cf. A001333, A078469, A152124.

From Colin Barker, Jul 14 2013: (Start)
a(n) = 2*a(n-2) + a(n-4).
G.f.: -x*(x+1)*(x^2+1) / (x^4+2*x^2-1). (End)
a(n+1) = A135153(n) + A135153(n+2). - R. J. Mathar, Jul 10 2019

A152124 Number of partitions of a 2 x n rectangle into connected pieces consisting of unit squares cut along lattice lines (like a 2-d analog of a partition into integers) in which each piece has rotational symmetry.

Original entry on oeis.org

1, 2, 8, 36, 162, 746, 3420, 15738, 72352, 332850, 1530928, 7042422, 32394478, 149015678, 685471704, 3153185542, 14504703924, 66721946584, 306922286796, 1411848979422, 6494534685710, 29874996141112, 137425609255358, 632160693109496, 2907952479953454

Offset: 0

Hugo van der Sanden, Mar 23 2009

nonn

			Example: the partitions comprising a(2)=8 are:
AA AA AB AA AB BC BA AB
AA BB AB BC AC AA CA CD
I.e., exactly those of A078469(2)=12 except for the 4 rotations of the one partition that includes an asymmetric piece:
AA
AB

Hugo van der Sanden, Table of n, a(n) for n = 0..100

Cf. A078057, A152113.

Let u(n) represent the number of decompositions of a 1 x n rectangle.
Then: u(n) = 2^(n-1) for n > 0, u(n) = 1 for n = 0.
Let t(n) represent the number of decompositions of a 2 x n rectangle such that a single piece includes the whole of the leftmost and rightmost columns.
Then: t(n) = t(n-2) + sum_1^{(n-3)/2}{ 2 u(i)^2 t(n-2i-2) }
Let s(m, n) represent the number of decompositions of a 2 x n rectangle with a 1 x m spike attached to the side.
Then for m > 0: s(m, n) = sum_1^m{ s(m-i, n) } + sum_1^n{ s(i, n-i) } + sum_m^{(n+m-1)/2}{ u(i-m) sum_1^{n+m-2i}{ t(j) s(i, n+m-2i-j) } } and for m = 0: s(m, n) = sum_1^n{ s(i, n-i) } + sum_1^n{ t(i) s(0, n-i) } + sum_1^{(n-1)/2){ u(i) sum_1^{n-2i}{ t(j) s(i, n-2i-j) } } (Note that these sums can be taken to infinity if the functions are defined as zero when any argument is negative.)
We get t(n) = [ 0 1 1 1 1 3 3 13 13 59 59 269 269 1227 1227 5597 5597 25531 ... ] = A052984((n - 3) / 2) with recurrence a(n) = 5a(n-1)-2a(n-2), a(0) = 1, a(1) = 3.
This gives a much faster way to calculate values for the sequence (as s(0, n)).

Entries changed by N. J. A. Sloane to match the b-file, Oct 04 2010

A264841 Triangle read by rows: T(n,k) is the number of ways to partition an n X k square grid into any number of parts along the gridlines.

Original entry on oeis.org

1, 2, 12, 4, 74, 1442, 8, 456, 28028, 1716098, 16, 2810, 544844, 105093828, 20276816980, 32, 17316, 10591310, 6435880414, 3912156203494, 2378025136264102, 64, 106706, 205886234, 394129505248, 754801786191820, 1445496758320387318, 2768227968406304217000, 128, 657552, 4002256640, 24136256828880

Offset: 1

Linus Hamilton, Nov 26 2015

A set of edges forms a valid partition if and only if it includes the entire boundary of the grid, and there are no vertices of degree 1.

			The triangle T(n,k) begins:
n\k 1  2    3      4         5
1:  1
2:  2  12
3:  4  74   1442
4:  8  456  28028  1716098
5:  16 2810 544844 105093828 20276816980

Danny Rorabaugh, A264841 Example: T(2,2)
R. J. Mathar, Counting 2-way monotonic terrace forms over rectangular landscapes, see Section 6.3, Combinatorics and Graph Theory, viXra:1511.0225, 2015.

A078469 is the second column of this triangle.

T(n,1) = 2^(n-1).

T(n,2) = A078469(n).

cp's OEIS Frontend

A108808 Number of compositions of grid graph G_{3,n} = P_3 X P_n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A110476 Table of number of partitions of an m X n rectangle, read by descending antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A152113 A001333 with terms repeated.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A152124 Number of partitions of a 2 x n rectangle into connected pieces consisting of unit squares cut along lattice lines (like a 2-d analog of a partition into integers) in which each piece has rotational symmetry.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A264841 Triangle read by rows: T(n,k) is the number of ways to partition an n X k square grid into any number of parts along the gridlines.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula