|
| |
|
|
A072255
|
|
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.
|
|
2
|
|
|
|
1, 0, 1, 1, 3, 4, 7, 11, 19, 29, 47, 76, 125, 200, 322, 519, 845, 1366, 2211, 3573, 5778, 9342, 15122, 24481, 39639, 64094, 103684, 167734, 271397, 439178, 710698, 1149964, 1860751, 3010500, 4870792, 7880666, 12751729, 20632965, 33385273, 54019297, 87406719
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
Marty Getz and Dixon Jones, Problem 11005, American Mathematical Monthly, 110, April 2003, page 340.
|
|
|
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:
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
