OFFSET
0,5
REFERENCES
The question of enumerating these partitions appears as Problem 11005, American Mathematical Monthly, 110, April 2003, page 340.
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).)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..4786 (terms n = 2..500 from T. D. Noe)
Marty Getz and Dixon Jones, Problem 11005, American Mathematical Monthly, 110, April 2003, page 340.
Marty Getz, Dixon Jones and Ken Dutch, Partitioning by Arithmetic Progressions: 11005, American Math. Monthly, Vol. 112, 2005, pp. 89-90.
FORMULA
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
EXAMPLE
a(5) = 4: the four ways to partition [5] as described above are: 12|345, 123|45, 12345, 135|24.
MAPLE
F:= combinat[fibonacci]:
a:= proc(n) option remember; `if`(n=0, 1, add((k->
F(k)^r*F(k-1)^(d-r))(iquo(n, d, 'r')), d=1..iquo(n, 2)))
end:
seq(a(n), n=0..40); # Alois P. Heinz, Feb 11 2024
PROG
(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
CROSSREFS
A053732 relates to partitions of {1, 2, ..., n} into arithmetic progressions without restrictions on the common difference of the progressions.
KEYWORD
nonn,easy,nice
AUTHOR
Marty Getz (ffmpg1(AT)uaf.edu) and Dixon Jones (fndjj(AT)uaf.edu), Jul 08 2002
EXTENSIONS
More terms from Michel Marcus, Oct 13 2013
a(0)-a(1) prepended by Alois P. Heinz, Feb 11 2024
STATUS
approved