login
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
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
L. M. Braswell and T. Khovanova, Cookie Monster Devours Naccis arXiv:1305.4305 [math.HO], 2013.
FORMULA
From Colin Barker, Apr 10 2020: (Start)
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
Terms a(51) and beyond from Andrew Howroyd, Apr 29 2020
STATUS
approved