A360955 Number of finite sets of positive integers whose right half (inclusive) sums to n.

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

Andrew Howroyd, Table of n, a(n) for n = 0..1000

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.

Cf. A000009, A072233, A359893, A359901, A360674, A360956.

Sequence in context: A108917 A237667 A325769 * A226538 A339510 A191930

Adjacent sequences: A360952 A360953 A360954 * A360956 A360957 A360958

Keyword

nonn

Author

Gus Wiseman, Mar 09 2023

Extensions

Terms a(16) and beyond from Andrew Howroyd, Mar 13 2023

Status

approved