|
|
A226107
|
|
Number of strict partitions of n with Cookie Monster number 2.
|
|
2
|
|
|
0, 0, 1, 1, 2, 3, 3, 4, 4, 6, 5, 7, 6, 9, 7, 10, 8, 12, 9, 13, 10, 15, 11, 16, 12, 18, 13, 19, 14, 21, 15, 22, 16, 24, 17, 25, 18, 27, 19, 28, 20, 30, 21, 31, 22, 33, 23, 34, 24, 36, 25, 37, 26, 39, 27, 40, 28, 42, 29, 43, 30, 45, 31, 46, 32, 48, 33, 49, 34, 51
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
Given a set of integers representing the number of cookies in jars, The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty the jars when in one move he may choose any subset of jars and take the same number of cookies from each of those jars.
Partitions have Cookie Monster number 2 if either they have two distinct values, or they have three distinct values, where the largest value is the sum of the other two. These are the partitions of n into distinct numbers with Cookie Monster number 2.
Three distinct values are only possible when n is even, in which case the largest value will be n/2. The number of strict partitions of n into two parts is just floor((n-1)/2). - Andrew Howroyd, Apr 29 2020
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x^3*(1 + x + x^2 + 2*x^3) / ((1 - x)^2*(1 + x)^2*(1 + x^2)).
a(n) = a(n-2) + a(n-4) - a(n-6) for n>6.
(End)
a(2*n+1) = n; a(2*n) = n - 1 + floor((n-1)/2). - Andrew Howroyd, Apr 29 2020
|
|
EXAMPLE
|
If there are 7 cookies, the total number of partitions is 15. 5 partitions of 7 are strict: (7), (1,6), (2,5), (3,4), (1,2,4). One of these partitions, (7), corresponds to Cookie Monster number 1 (it has one value). One of these partitions, (1,2,4), has Cookie Monster number 3 (it has three values and the largest is not the sum of the other two). The remaining 3 partitions, (1,6), (2,5) and (3,4) have Cookie Monster number 2, so a(7)= 3.
|
|
MATHEMATICA
|
Table[Length[
Select[Union[Map[Union, IntegerPartitions[n]]],
Total[#] ==
n && (Length[#] ==
2 || (Length[#] == 3 && #[[3]] == #[[1]] + #[[2]])) &]], {n, 50}]
LinearRecurrence[{0, 1, 0, 1, 0, -1}, {0, 0, 1, 1, 2, 3}, 70] (* Harvey P. Dale, Jun 07 2022 *)
|
|
PROG
|
(PARI) a(n) = {(n-1)\2 + if(n%2==0, (n/2-1)\2)} \\ Andrew Howroyd, Apr 29 2020
(PARI) concat([0, 0], Vec(x^3*(1 + x + x^2 + 2*x^3) / ((1 - x)^2*(1 + x)^2*(1 + x^2)) + O(x^40))) \\ Colin Barker, Apr 29 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|