A072255 - OEIS

%I #30 Dec 17 2024 09:20:51

%S 1,0,1,1,3,4,7,11,19,29,47,76,125,200,322,519,845,1366,2211,3573,5778,

%T 9342,15122,24481,39639,64094,103684,167734,271397,439178,710698,

%U 1149964,1860751,3010500,4870792,7880666,12751729,20632965,33385273,54019297,87406719

%N Number of ways to partition {1,2,...,n} into arithmetic progressions, where in each partition all the progressions have the same common difference and have lengths >= 2.

%D The question of enumerating these partitions appears as Problem 11005, American Mathematical Monthly, 110, April 2003, page 340.

%D Problem 11005, American Math. Monthly, Vol. 112, 2005, pp. 89-90. (The published solution is incomplete; the solver's expression q_2(n,d) must be summed over all d = 1,2,...,floor(n/2).)

%H Alois P. Heinz, <a href="/A072255/b072255.txt">Table of n, a(n) for n = 0..4786</a> (terms n = 2..500 from T. D. Noe)

%H Marty Getz and Dixon Jones, <a href="http://www.jstor.org/stable/3647885">Problem 11005</a>, American Mathematical Monthly, 110, April 2003, page 340.

%H Marty Getz, Dixon Jones and Ken Dutch, <a href="http://www.jstor.org/stable/30037399">Partitioning by Arithmetic Progressions: 11005</a>, American Math. Monthly, Vol. 112, 2005, pp. 89-90.

%F a(n) = Sum_{d=1..floor(n/2)} F(k)^r * F(k-1)^(d-r), where d is the common difference of the arithmetic progressions, k = floor(n/d), r = n mod d and F(k) is the k-th Fibonacci number (A000045). - Marty Getz (ffmpg1(AT)uaf.edu) and Dixon Jones (fndjj(AT)uaf.edu), May 21 2005

%e a(5) = 4: the four ways to partition [5] as described above are: 12|345, 123|45, 12345, 135|24.

%p F:= combinat[fibonacci]:

%p a:= proc(n) option remember; `if`(n=0, 1, add((k->

%p       F(k)^r*F(k-1)^(d-r))(iquo(n, d, 'r')), d=1..iquo(n, 2)))

%p     end:

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Feb 11 2024

%t a[n_] := If[n == 0, 1, Module[{k, r}, Sum[{k, r} = QuotientRemainder[n, d]; Fibonacci[k]^r*Fibonacci[k-1]^(d-r), {d, 1, Quotient[n, 2]}]]];

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Dec 17 2024 *)

%o (PARI) a(n) = sum(d = 1, n\2, fibonacci(n\d)^(n % d) * fibonacci(n\d -1)^(d - n%d)); \\ _Michel Marcus_, Oct 13 2013

%Y A053732 relates to partitions of {1, 2, ..., n} into arithmetic progressions without restrictions on the common difference of the progressions.

%Y Cf. A000045, A000110.

%K nonn,easy,nice

%O 0,5

%A Marty Getz (ffmpg1(AT)uaf.edu) and Dixon Jones (fndjj(AT)uaf.edu), Jul 08 2002

%E More terms from _Michel Marcus_, Oct 13 2013

%E a(0)-a(1) prepended by _Alois P. Heinz_, Feb 11 2024