login
A360955
Number of finite sets of positive integers whose right half (inclusive) sums to n.
5
1, 1, 2, 3, 4, 6, 7, 11, 12, 19, 20, 31, 33, 49, 51, 77, 79, 112, 124, 165, 177, 247, 260, 340, 388, 480, 533, 693, 747, 925, 1078, 1271, 1429, 1772, 1966, 2331, 2705, 3123, 3573, 4245, 4737, 5504, 6424, 7254, 8256, 9634, 10889, 12372, 14251, 16031, 18379
OFFSET
0,3
LINKS
FORMULA
a(n) = Sum_{w>=1} Sum_{h=w..floor((n-binomial(w,2))/w)} binomial(h,w) * A072233(n - w*h - binomial(w,2), w-1) for n > 0. - Andrew Howroyd, Mar 13 2023
EXAMPLE
The a(1) = 1 through a(8) = 12 sets:
{1} {2} {3} {4} {5} {6} {7} {8}
{1,2} {1,3} {1,4} {1,5} {1,6} {1,7} {1,8}
{2,3} {2,4} {2,5} {2,6} {2,7} {2,8}
{3,4} {3,5} {3,6} {3,7} {3,8}
{4,5} {4,6} {4,7} {4,8}
{1,2,3} {5,6} {5,7} {5,8}
{1,2,4} {6,7} {6,8}
{1,2,5} {7,8}
{1,3,4} {1,2,6}
{2,3,4} {1,3,5}
{1,2,3,4} {2,3,5}
{1,2,3,5}
For example, the set y = {2,3,5} has right half (inclusive) {3,5}, with sum 8, so y is counted under a(8).
MATHEMATICA
Table[Length[Select[Join@@IntegerPartitions/@Range[0, 3*k], UnsameQ@@#&&Total[Take[#, Ceiling[Length[#]/2]]]==k&]], {k, 0, 15}]
PROG
(PARI) \\ P(n, k) is A072233(n, k).
P(n, k)=polcoef(1/prod(k=1, k, 1 - x^k + O(x*x^n)), n)
a(n)=if(n==0, 1, sum(w=1, sqrt(n), my(t=binomial(w, 2)); sum(h=w, (n-t)\w, binomial(h, w) * P(n-w*h-t, w-1)))) \\ Andrew Howroyd, Mar 13 2023
CROSSREFS
The version for multisets is A360671, exclusive A360673.
The exclusive version is A360954.
First for prime indices, second for partitions, third for prime factors:
- A360676 gives left sum (exclusive), counted by A360672, product A361200.
- A360677 gives right sum (exclusive), counted by A360675, product A361201.
- A360678 gives left sum (inclusive), counted by A360675, product A347043.
- A360679 gives right sum (inclusive), counted by A360672, product A347044.
Sequence in context: A108917 A237667 A325769 * A226538 A339510 A191930
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 09 2023
EXTENSIONS
Terms a(16) and beyond from Andrew Howroyd, Mar 13 2023
STATUS
approved