1

I wish to make an integer length n of boards laid down end to end. Each board is an integer length and among boards of one length there are unique types. For example, boards of length one come in two types: "1a", "1b" while boards of length two come in one type: "2" I can make a length 2 combination in these 5 unique ways: (1a,1a)(1a,1b)(1b,1a)(1b,1b), and (2). If I have s(n) boards types of length n, and wish to make a total length n, there are r(n) different ways. The solution is:

r(1) = s(1)

r(2) = s(2) + s(1) r(1)

r(3) = s(3) + s(2) r(1) + s(1) r(2)

r(4) = s(4) + s(3) r(1) + s(2) r(2) + s(1) r(3)

etc.

Where might I find a detailed explanation of why this works? I am thinking this is very basic stuff, since if s(n)=1 for all n, then we are just partitioning the integers.

E.g.

There are 8 ways to make 4: (1,1,1,1)(2,1,1)(1,2,1)(1,1,2)(2,2)(1,3)(3,1),(4) and r(4)=2^(n-1)=8. This is consistent as a particular case of the series above.

I tried wikipedia for partitions, but maybe there is a less opaque intro out there. Thanks.

So, I am also interested is simplifying methods when the s(n) start repeating, e.g. as above. Another example, if s(n)= ..., 2,2,4,2,2,4,2,2,4,... starting from n=4, what math method can I use to turn the rule above into a recursion relation, when all the s(n) are known, so that the coefficients are determined:

r(n) = A r(n-1) + B r(n-2) + C r(n-3) + D r(n-4) + E r(n-5) + F r(n-6)

Steven Lord
  • 11
  • Since you count different orderings of the same sum as different, you're counting compositions. – Karl Oct 25 '23 at 20:36
  • Great, thanks - compositions it is and the wiki page explains the case s(n)=1, all n. I guess I understand it vaguely. In the s(n)=1 case, the solution is r(n)=1+r(n-1)+r(n-1)+ ... r(1). When s(n) takes on values (=0 or >1), its insertion into each term accounts for the multiplicity of possibilities. - I am still looking for a way of turning the open sums into a closed form. I am trying to understand this paper: http://www.numdam.org/item/MSH_1995__130__27_0.pdf – Steven Lord Oct 25 '23 at 20:53
  • Yeah, to obtain the recurrence, count the compositions according to the length of the first board: If the first board has length $k$, then there are $s(k)$ boards to choose from and $r(n-k)$ ways to make the rest of the arrangement. So $r(n)=\sum_{k=1}^ns(k)r(n-k)$ (where we define $r(0)=1$). – Karl Oct 25 '23 at 21:01
  • Again, thanks. The formula you gave does exactly represent the equations I presented. The 2nd problem I am addressing is this: when the s(n)'s become cyclic (mod 3). In that case the authors collapsed the recursion down to only 6 prior terms no matter how large n. – Steven Lord Oct 25 '23 at 21:07
  • 1
    The brute force way I can think of is to postulate that (A, B,...F) exist, make 6 linear equations and solve with matrix inversion. Yet the authors solved it with some finesse that is beyond me, but I was hoping the method discussed somewhere... Even knowing what it is called would help. – Steven Lord Oct 25 '23 at 21:24
  • The authors collapse the recursion using generating functions which I suspect is a useful tool in this area. Any references? – Steven Lord Oct 25 '23 at 22:25

0 Answers0