[seqfan] Re: 2-d partitions, rotationally symmetric pieces

Tue Mar 31 02:01:15 CEST 2009

For (4a) below: thanks to Richard Mathar for confirming that the values I
supplied did not yield a useful recurrence relation.

To understand this issue more deeply, I evaluated a series of constrained
versions of the function in (4), such that only pieces with a width no
greater than m were considered. I found as expected that these series
satisfied a recurrence relation, and less expectedly that the order in
each case was m(m+1)/2. The first few recurrences were:

m = 1: order 1: [ 2 ]
m = 2: order 3: [ 3, 2, -2 ]
m = 3: order 6: [ 3, 4, 5, -6, -4, -2 ]
m = 4: order 10: [ 3, 5, 5, 5, -16, -15, -2, 2, 4, 2 ]
m = 5: order 15: [ 3, 5, 7, 5, 18, -37, -46, -28, -12, ... ]
m = 6: order 21: [ 3, 5, 8, 5, 14, 20, -81, -103, -90, ... ]
m = 7: order 28: [ 3, 5, 8, 7, 14, 16, 70, -183, -260, ... ]
m = 8: order 36: [ 3, 5, 8, 8, 14, 12, 57, 76, -390, -546, ... ]
m = 9: order 45: [ 3, 5, 8, 8, 16, 12, 53, 58, 262, -888, ... ]

.. which shows an interesting convergence, but not I suspect a particularly
useful one. (Read that as: for m=2, f(n) = 3f(n-1) + 2f(n-2) - 2f(n-3).)

So I went back to finding an expression for the original sequence in (4),
and developed this:

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.)

t(n) = [ 0 1 1 1 1 3 3 13 13 59 59 269 269 1227 1227 5597 5597 25531 ... ]
     = A052984((n - 3) / 2)
.. which I'm delighted to discover are the "Kekule numbers for certain
benzenoids", satisfy the recurrence:
  a(n) = 5a(n-1)-2a(n-2), a(0) = 1, a(1) = 3
.. and have several interesting comments for formulae.

This gives me a much faster way to calculate values for the original sequence
(as s(0, n)), and renewed hope of finding a simpler formula for it. I give
the first 100 values below, calculated in 3 minutes.

Hugo

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
13376642577294978 61532837218960114 283052345606879420 1302046743996675526
5989442412395652706 27551561091456500874 126737760600181764884
582996364838160676928 2681795542278203773274 12336315909241464751110
56747312691650631822870 261038832129100667094944 1200784119057734204692164
5523632207594957173852822 25408824351144344317660836
116881126520263413548448436 537655640727457721776193040
2473227257575562200009730048 11376897412140112702097106448
52333967422484611908157430890 240737351051008267299224201154
1107396879032660660807017736126 5094048938967675072292968041434
23432732278661558484283635512692 107791061417384562040635993131518
495841150033828884076678985348834 2280879720767068276280591613554232
10492094696560629350349624149190482 48263856317935963725949441441614582
222014754350430927068740216282628480 1021272540357797332287661666065331910
4697875169334863349017013779924231134 21610324604361686346356417696609129588
99407947779080716823220925418856817824 457278650948812345563975629776489415418
2103491413767715768207600244762839355950
9676104752788471482942705414952084872178
44510285411259912223324365633461247522066
204748249218869020540202723683530983034662
941846253531032005856092134467606013816572
4332512579104831487436057096492330378159808
19929649003464599684167587796199381842936818
91676804659933312908696663866180226636489610
421715229966894848181351084973641395846877670
1939898929131812661841202086471144036221310490
8923575882099799569553858704360665994698898926
41048636775747447154477882760065241738519073660
188824592675593629367950795118775446883681738568
868597098458810313882854516005487974041322129854
3995564924889052637654640431184769709054758447228
18379682705975230940271657660301646352022856287678
84546927086087894335277688989137566163695950132272
388917643141706146471731225534454691213016036339574
1789029339799490538804650303836749473770656363687706
8229572597448915327542027481118313034343958724011552
37856207067164485210155671799622036866898506110409416
174139348859535978646889299578264474932215035427229528
801044667983282683116861072529392006926863994540968832
3684822323655479787326138081313256136194054889476939722
16950260203458631979473862223934090055291217413851227374
77971553504900075118039194863306919382461620017440805478
358670786347396893453015576449836170141346580256112843462
1649893162266869921302009331123614035890120238609232822770
7589543253903004555094573555564338642313185405783561711038
34912058623070787616051684015863337635143690313354579965732
160596204083022205962767154023175210438760148051475875841408
738745917115075766444737619449802080080031085116432972593254
3398246759133014450812214515795204725632467043707586918408386
15632006578195640701873679515056880029525402622087955069415646
71907559097649106027925563620703052043071461238795023384079522
330776284510669517648864620707132734639757573780066873050485164
1521577867023725121777065327835408945298765683896001459343321030
6999290196518879753893009813282956468658363041981764946719530126
32196882142425001122371646507888969509572992357451308320810231324
148106335155067851329214788300399127996038253237794698270711176726
681292257307159021976120658824791127099066057726012008916294974704

hv at crypt.org wrote:
:All the points below involve connected pieces consisting of unit squares
:cut along lattice lines, as 2-d analogues of the integers used for partitions.
:
:1. A078469 "Number of different compositions of the ladder graph L_n."
:
:This is identically the number of partitions of the 2 x n rectangle.
:I feel the entry for a(0) = 0 should be 1 instead, though it does throw
:out the start of the recurrence.
:
:2. The number of ways to decompose the 1 x n rectangle into pieces each
:of which has rotational symmetry is trivially 2^(n - 1).
:
:3. The number of distinct pieces with rotational symmetry that extend
:to opposite corners of a 2 x n rectangle satisfies the recurrence relation
:a(2n) = a(2n + 1) = 2a(2n-2) + a(2n-4): [n=1]: 1, 1, 3, 3, 7, 7, 17, 17, ...
:
:Example: the pieces comprising a(3) are:
:
:AAA BB. .CC
:AAA .BB CC.
:
:4. The number of ways to decompose the 2 x n rectangle into pieces each
:of which has rotational symmetry is the following sequence:
:
:[n=0]: 1, 2, 8, 36, 162, 746, 3420, 15738, 72352, 332850, 
:[n=10]: 1530928, 7042422, 32394478, 149015678, 685471704, 3153185542,
:  14504703924, 66721946584, 306922286796, 1411848979422
:[n=20]: 6494534685710, 137425609255358, 632160693109496, 2907952479953454,
:  13376642577294978, 61532837218960114, 283052345606879420,
:  1302046743996675526 [n=28]
:
: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
:
:[4a: is there a general technique, when you think it likely a sequence
:exhibits a recurrence relation, to discover what the relation is given
:sufficient values? Clearly an order-n recurrence will yield a matrix of
:simultaneous equations given 2n-1 consecutive values, but I'm guessing
:that prior art might help shortcircuit the effort.]
:
:5. Representing the partitions in (4) by the set of centres of rotation
:of the pieces, the representation is unique for all partitions up to a(8).
:An ambiguous pair on the 2 x 9 rectangle are:
:
:AAAAAABAA AAAAABBBA
:AACAAAAAA ACCCAAAAA
:
:I'm not sure that re-counting the sequence in (4) with this extra
:constraint is additionally interesting enough to be worth the effort:
:I'd rather go on to tackle 3 x n and larger.
:
:This train of though was inspired by a new puzzle-type on janko.at,
:"Galaxien": http://www.janko.at/Raetsel/Galaxien/index.htm
:
:Hugo