A095944 -id:A095944 - cp's OEIS frontend

A365541 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.

1, 2, 2, 2, 4, 4, 7, 4, 4, 8, 8, 14, 14, 14, 8, 8, 16, 16, 28, 28, 37, 28, 28, 16, 16, 32, 32, 56, 56, 74, 74, 74, 56, 56, 32, 32, 64, 64, 112, 112, 148, 148, 175, 148, 148, 112, 112, 64, 64, 128, 128, 224, 224, 296, 296, 350, 350, 350, 296, 296, 224, 224, 128, 128

Offset: 2

Gus Wiseman, Sep 15 2023

Rows are palindromic.

			Triangle begins:
    1
    2    2    2
    4    4    7    4    4
    8    8   14   14   14    8    8
   16   16   28   28   37   28   28   16   16
   32   32   56   56   74   74   74   56   56   32   32
Row n = 4 counts the following subsets:
  {1,2}      {1,3}      {1,4}      {2,4}      {3,4}
  {1,2,3}    {1,2,3}    {2,3}      {1,2,4}    {1,3,4}
  {1,2,4}    {1,3,4}    {1,2,3}    {2,3,4}    {2,3,4}
  {1,2,3,4}  {1,2,3,4}  {1,2,4}    {1,2,3,4}  {1,2,3,4}
                        {1,3,4}
                        {2,3,4}
                        {1,2,3,4}

Row lengths are A005408.
The case counting only length-2 subsets is A008967.
Column k = n + 1 appears to be A167762.
The version for all subsets (instead of just pairs) is A365381.
Column k = n is A365544.
A000009 counts subsets summing to n.
A007865/A085489/A151897 count certain types of sum-free subsets.
A046663 counts partitions with no submultiset summing to k, strict A365663.
A093971/A088809/A364534 count certain types of sum-full subsets.
A365543 counts partitions with a submultiset summing to k, strict A365661.
Cf. A068911, A095944, A238628, A288728, A326083, A364272, A365376, A365377.

Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#,{2}],k]&]], {n,2,11}, {k,3,2n-1}]

A367216 Number of subsets of {1..n} whose cardinality is equal to the sum of some subset.

Original entry on oeis.org

1, 2, 3, 5, 10, 20, 40, 82, 169, 348, 716, 1471, 3016, 6171, 12605, 25710, 52370, 106539, 216470, 439310, 890550, 1803415, 3648557, 7375141, 14896184, 30065129, 60639954, 122231740, 246239551, 495790161, 997747182, 2006969629, 4035274292, 8110185100, 16293958314, 32724456982

Offset: 0

Gus Wiseman, Nov 12 2023

nonn

			The a(0) = 1 through a(4) = 10 subsets:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {1,2}  {1,2}    {1,2}
                  {2,3}    {2,3}
                  {1,2,3}  {2,4}
                           {1,2,3}
                           {1,2,4}
                           {1,3,4}
                           {2,3,4}
                           {1,2,3,4}

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216*   A367217    A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A002865 counts partitions whose length is a part, complement A229816.
A007865/A085489/A151897 count certain types of sum-free subsets.
A088809/A093971/A364534 count certain types of sum-full subsets.
A237668 counts sum-full partitions, ranks A364532.
A240855 counts strict partitions whose length is a part, complement A240861.
A364272 counts sum-full strict partitions, sum-free A364349.
A365046 counts combination-full subsets, differences of A364914.
Triangles:
A365381 counts sets with a subset summing to k, without A366320.
A365541 counts sets containing two distinct elements summing to k.
Cf. A068911, A095944, A103580, A288728, A326080, A326083, A365376, A365544.

Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#], Length[#]]&]], {n,0,10}]

a(n) = 2^n - A367217(n). - Chai Wah Wu, Nov 14 2023

a(16)-a(28) from Chai Wah Wu, Nov 14 2023

a(29)-a(35) from Max Alekseyev, Feb 25 2025

A365544 Number of subsets of {1..n} containing two distinct elements summing to n.

Original entry on oeis.org

0, 0, 0, 2, 4, 14, 28, 74, 148, 350, 700, 1562, 3124, 6734, 13468, 28394, 56788, 117950, 235900, 484922, 969844, 1979054, 3958108, 8034314, 16068628, 32491550, 64983100, 131029082, 262058164, 527304974, 1054609948, 2118785834, 4237571668, 8503841150, 17007682300

Offset: 0

Gus Wiseman, Sep 20 2023

			The a(1) = 0 through a(5) = 14 subsets:
  .  .  {1,2}    {1,3}      {1,4}
        {1,2,3}  {1,2,3}    {2,3}
                 {1,3,4}    {1,2,3}
                 {1,2,3,4}  {1,2,4}
                            {1,3,4}
                            {1,4,5}
                            {2,3,4}
                            {2,3,5}
                            {1,2,3,4}
                            {1,2,3,5}
                            {1,2,4,5}
                            {1,3,4,5}
                            {2,3,4,5}
                            {1,2,3,4,5}

Index entries for linear recurrences with constant coefficients, signature (2,3,-6).

For strict partitions we have A140106 shifted left.
The version for partitions is A004526.
The complement is counted by A068911.
For all subsets of elements we have A365376.
Main diagonal k = n of A365541.
A000009 counts subsets summing to n.
A007865/A085489/A151897 count certain types of sum-free subsets.
A093971/A088809/A364534 count certain types of sum-full subsets.
A365381 counts subsets with a subset summing to k.
Cf. A008967, A095944, A167762, A238628, A288728, A326083, A364272, A365377.

Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#,{2}],n]&]],{n,0,10}]

def A365544(n): return (1<>1)<<1 if n&1 else 3**(n-1>>1)<<2) if n else 0 # Chai Wah Wu, Aug 30 2024

a(n) = 2^n - A068911(n).
From Alois P. Heinz, Aug 30 2024: (Start)
G.f.: 2*x^3/((2*x-1)*(3*x^2-1)).
a(n) = 2 * A167762(n-1) for n>=1. (End)

A360634 Number T(n,k) of sets of nonempty words over binary alphabet with a total of n letters of which k are the first letter; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 2, 6, 6, 2, 2, 11, 16, 11, 2, 3, 18, 37, 37, 18, 3, 4, 28, 73, 100, 73, 28, 4, 5, 42, 133, 228, 228, 133, 42, 5, 6, 61, 227, 470, 593, 470, 227, 61, 6, 8, 86, 370, 899, 1370, 1370, 899, 370, 86, 8, 10, 119, 580, 1617, 2894, 3497, 2894, 1617, 580, 119, 10

Offset: 0

Alois P. Heinz, Feb 14 2023

			T(4,0) = 2: {bbbb}, {b,bbb}.
T(4,1) = 11: {abbb}, {babb}, {bbab}, {bbba}, {a,bbb}, {ab,bb}, {abb,b}, {b,bab}, {b,bba}, {ba,bb}, {a,b,bb}.
T(4,2) = 16: {aabb}, {abab}, {abba}, {baab}, {baba}, {bbaa}, {a,abb}, {a,bab}, {a,bba}, {aa,bb}, {aab,b}, {ab,ba}, {aba,b}, {b,baa}, {a,ab,b}, {a,b,ba}.
Triangle T(n,k) begins:
   1;
   1,   1;
   1,   3,   1;
   2,   6,   6,    2;
   2,  11,  16,   11,    2;
   3,  18,  37,   37,   18,    3;
   4,  28,  73,  100,   73,   28,    4;
   5,  42, 133,  228,  228,  133,   42,    5;
   6,  61, 227,  470,  593,  470,  227,   61,   6;
   8,  86, 370,  899, 1370, 1370,  899,  370,  86,   8;
  10, 119, 580, 1617, 2894, 3497, 2894, 1617, 580, 119, 10;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Columns k=0-2 give: A000009, A095944, A360650.
Row sums give A102866.
T(2n,n) gives A360638.
Cf. A055375 (the same for multisets), A200751, A208741.

g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(
      g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i), k), k=0..j))))
    end:
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
     `if`(i<1, 0, add(b(n-i*j, i-1)*g(i$2, j), j=0..n/i))))
    end:
T:= (n, k)-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2)):
seq(T(n), n=0..15);

g[n_, i_, j_] := g[n, i, j] = Expand[If[j == 0, 1, If[i < 0, 0, Sum[g[n, i - 1, j - k]*x^(i*k)*Binomial[Binomial[n, i], k], {k, 0, j}]]]];
b[n_, i_] := b[n, i] = Expand[If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1]*g[i, i, j], {j, 0, n/i}]]]];
T[n_] := CoefficientList[b[n, n], x];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Dec 05 2023, after Alois P. Heinz *)

T(n,k) = T(n,n-k).

Sum_{k=0..2n} (-1)^k*T(2n,k) = A200751(n). - Alois P. Heinz, Sep 09 2023

A365659 Number of strict integer partitions of n that either have (1) length 2, or (2) greatest part n/2.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 3, 3, 4, 4, 6, 5, 8, 6, 10, 7, 12, 8, 15, 9, 18, 10, 21, 11, 25, 12, 29, 13, 34, 14, 40, 15, 46, 16, 53, 17, 62, 18, 71, 19, 82, 20, 95, 21, 109, 22, 125, 23, 144, 24, 165, 25, 189, 26, 217, 27, 248, 28, 283, 29, 324

Offset: 0

Gus Wiseman, Sep 16 2023

nonn

Also the number of strict integer partitions of n containing two possibly equal elements summing to n.

			The a(3) = 1 through a(11) = 5 partitions:
  (2,1)  (3,1)  (3,2)  (4,2)    (4,3)  (5,3)    (5,4)  (6,4)    (6,5)
                (4,1)  (5,1)    (5,2)  (6,2)    (6,3)  (7,3)    (7,4)
                       (3,2,1)  (6,1)  (7,1)    (7,2)  (8,2)    (8,3)
                                       (4,3,1)  (8,1)  (9,1)    (9,2)
                                                       (5,3,2)  (10,1)
                                                       (5,4,1)

Without repeated parts we have A140106.
The non-strict version is A238628.
For subsets instead of strict partitions we have A365544.
A000009 counts subsets summing to n.
A365046 counts combination-full subsets, differences of A364914.
A365543 counts partitions of n with a submultiset summing to k.
Cf. A008967, A046663, A068911, A095944, A364272, A365376, A365377.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&(Length[#]==2||Max@@#==n/2)&]], {n,0,30}]

from sympy.utilities.iterables import partitions
def A365659(n): return n>>1 if n&1 or n==0 else (m:=n>>1)+sum(1 for p in partitions(m) if max(p.values(),default=1)==1)-2 # Chai Wah Wu, Sep 18 2023

a(n) = (n-1)/2 if n is odd. a(n) = n/2 + A000009(n/2) - 2 if n is even and n > 0. - Chai Wah Wu, Sep 18 2023

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

Original entry on oeis.org

0, 1, 2, 3, 6, 9, 15, 23, 40, 55, 94, 132, 210, 298, 476, 644, 1038, 1406, 2149, 2965, 4584, 6077, 9426, 12648, 19067, 25739, 38958, 51514, 78459, 104265, 155436, 208329, 312791, 411886, 620780, 823785, 1224414, 1631815, 2437015, 3217077, 4822991

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

The complement is counted by A365069. The binary version is A364755, complement A364756. For re-usable parts we have A288728, complement A365070.

			The subset {1,3,4,6} has 4 = 1 + 3 so is not counted under a(6).
The subset {2,3,4,5,6} has 6 = 2 + 4 and 4 = 1 + 3 so is not counted under a(6).
The a(0) = 0 through a(6) = 15 subsets:
  .  {1}  {2}    {3}    {4}      {5}      {6}
          {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
                 {2,3}  {2,4}    {2,5}    {2,6}
                        {3,4}    {3,5}    {3,6}
                        {1,2,4}  {4,5}    {4,6}
                        {2,3,4}  {1,2,5}  {5,6}
                                 {1,3,5}  {1,2,6}
                                 {2,4,5}  {1,3,6}
                                 {3,4,5}  {1,4,6}
                                          {2,3,6}
                                          {2,5,6}
                                          {3,4,6}
                                          {3,5,6}
                                          {4,5,6}
                                          {3,4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 0..85
Steven R. Finch, Monoids of natural numbers, March 17, 2009.

First differences of A151897.
The version with re-usable parts is A288728 first differences of A007865.
The binary version is A364755, first differences of A085489.
The binary complement is A364756, first differences of A088809.
The complement is counted by A365069, first differences of A364534.
The complement w/ re-usable parts is A365070, first differences of A093971.
A108917 counts knapsack partitions, strict A275972.
A124506 counts combination-free subsets, differences of A326083.
A364350 counts combination-free strict partitions, complement A364839.
A365046 counts combination-full subsets, differences of A364914.
Partitions: A236912, A237113, A237668, A364532, A364272, A364349, A364913.
Cf. A050291, A095944, A103580, A324741, A326080, A326117, A341507, A364533.

Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Intersection[#, Total/@Subsets[#,{2,Length[#]}]]=={}&]], {n,0,10}]

a(n) + A365069(n) = 2^(n-1).

First differences of A151897.

a(14) onwards added (using A151897) by Andrew Howroyd, Jan 13 2024

A095941 Number of subsets of {1,2,...,n} such that every number in the set is no larger than the sum of the other numbers in the set.

Original entry on oeis.org

0, 0, 1, 4, 13, 35, 85, 194, 425, 904, 1885, 3878, 7904, 16008, 32282, 64913, 130280, 261145, 523036, 1047017, 2095222, 4191927, 8385695, 16773663, 33550117, 67103645, 134211440, 268427907, 536861880, 1073731053, 2147470842, 4294952115, 8589916646, 17179848025

Offset: 1

Michael Rieck and W. Edwin Clark, Jul 13 2004

These are the lengths of the sides of a (possibly degenerate) polygon.

Might be called "coalition sets": no member of the set can outnumber all of the others, so a coalition is needed in order to get a majority. - Jaap Spies, Jul 14 2004

Alois P. Heinz, Table of n, a(n) for n = 1..3321 (first 500 terms from T. D. Noe)

See A095944 for formula. Cf. A002623.

b:= proc(n, s) option remember; `if`(s<1, 2^n,
     `if`(n*(n+1)/2 add(b(j-1, j), j=1..n):
seq(a(n), n=1..37);  # Alois P. Heinz, Feb 13 2021

max = 30; -Accumulate[ Accumulate[q = PartitionsQ[ Range[max]]] + 1] + Accumulate[q] + 2^Range[max] - 1 (* Jean-François Alcover, Aug 01 2013, after A095944 *)

Extended by Alexander D. Healy using data from A095944, Nov 18 2005

A270144 a(n) = Sum_{k=0..n} (-1)^(k+1) * k * A000009(n-k).

Original entry on oeis.org

0, 1, -1, 2, -1, 2, 0, 2, 1, 2, 3, 2, 5, 3, 7, 5, 10, 7, 14, 11, 18, 17, 24, 24, 32, 34, 42, 47, 56, 63, 74, 85, 96, 113, 126, 147, 165, 191, 213, 247, 275, 316, 353, 404, 449, 514, 571, 648, 723, 816, 909, 1024, 1140, 1278, 1424, 1592, 1770, 1976, 2195, 2442

Offset: 0

Vaclav Kotesovec, Mar 12 2016

sign

Convolution of A000009 and A181983.

Vaclav Kotesovec, Table of n, a(n) for n = 0..5000

Cf. A000009, A025147, A095944, A270143.

Table[Sum[(-1)^(n-k+1)*PartitionsQ[k]*(n-k), {k, 0, n}], {n, 0, 100}]
nmax = 100; CoefficientList[Series[x/(1 + x)^2 * Product[(1 + x^k), {k, 1, nmax}], {x, 0, nmax}], x]

a(n) = Sum_{k=0..n} (-1)^(n-k+1) * (n-k) * A000009(k).
a(n) ~ A000009(n)/4.
a(n) ~ exp(Pi*sqrt(n/3)) / (16*3^(1/4)*n^(3/4)).
G.f.: x/(1+x)^2 * Product_{k>=1} (1+x^k).

A341507 Number of nonempty subsets S of {1,2,...,n} in which all elements are strictly less than the sum of the other elements of S.

Original entry on oeis.org

0, 0, 0, 0, 2, 9, 28, 74, 178, 402, 872, 1842, 3821, 7830, 15913, 32161, 64761, 130091, 260911, 522749, 1046667, 2094797, 4191414, 8385079, 16772926, 33549239, 67102603, 134210207, 268426453, 536860171, 1073729049, 2147468499, 4294949383, 8589913467, 17179844335

Offset: 0

Henry Bottomley, Feb 13 2021

nonn

In other words, every element of S is strictly less than half the sum.

			For n = 5 the a(5)=9 subsets are {2,3,4}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, and {1,2,3,4,5}.

math.stackexchange, Permutation and Combinatorics Problem

Cf. A000009, A002623, A095941, A095944, A317910.

b:= proc(n, s) option remember; `if`(s<1, 2^n,
     `if`(n*(n+1)/2 add(b(j-1, j+1), j=1..n):
seq(a(n), n=0..37);  # Alois P. Heinz, Feb 13 2021

gf := (1 - x - x^2)/((1 - 2 x) (1 - x)^2) - QPochhammer[-1, x]/(2 (1 - x)^2);
CoefficientList[Series[gf, {x, 0, 34}], x] (* Peter Luschny, Feb 13 2021 *)

a(n) = A095941(n) - A317910(n).

G.f.: (1-x-x^2)/((1-x)^2*(1-2*x)) - (1/(1-x)^2)*Product_{k>=1} (1 + x^k).

A365660 Number of integer partitions of 2n with exactly n distinct sums of nonempty submultisets.

Original entry on oeis.org

1, 1, 1, 3, 2, 6, 6, 16, 12, 20, 26, 59, 45, 79, 94, 186, 142, 231, 244, 442, 470, 616, 746, 1340, 1053, 1548, 1852, 2780, 2826, 3874, 4320, 6617, 6286, 7924, 9178, 13180, 13634, 17494, 20356, 28220, 29176, 37188, 41932, 56037

Offset: 0

Gus Wiseman, Sep 16 2023

Are n = 1, 2, 4 the only n such that none of these partitions has 1?

Are n = 2, 4, 5, 8, 9 the only n such that none of these partitions is strict?

			The partition (433) has sums 3, 4, 6, 7, 10 so is counted under a(5).
The a(1) = 1 through a(7) = 16 partitions:
(2)  (2,2)  (4,2)    (4,2,2)    (4,3,3)      (6,4,2)        (6,5,3)
            (5,1)    (2,2,2,2)  (4,4,2)      (6,5,1)        (8,4,2)
            (2,2,2)             (6,2,2)      (4,4,2,2)      (8,5,1)
                                (8,1,1)      (6,2,2,2)      (9,3,2)
                                (4,2,2,2)    (4,2,2,2,2)    (9,4,1)
                                (2,2,2,2,2)  (2,2,2,2,2,2)  (10,3,1)
                                                            (11,2,1)
                                                            (4,4,4,2)
                                                            (5,3,3,3)
                                                            (6,4,2,2)
                                                            (8,2,2,2)
                                                            (11,1,1,1)
                                                            (4,4,2,2,2)
                                                            (6,2,2,2,2)
                                                            (4,2,2,2,2,2)
                                                            (2,2,2,2,2,2,2)

For n instead of 2n we have A126796.
Central column n = 2k of A365658.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A002219 counts partitions of 2n with a submultiset summing to n.
A046663 counts partitions of n w/o a submultiset of sum k, strict A365663.
A122768 counts distinct nonempty submultisets of partitions.
A299701 counts sums of submultisets of prime indices, of partitions A304792.
A364272 counts sum-full strict partitions, sum-free A364349.
A365543 counts partitions of n w/ a submultiset of sum k, strict A365661.
Cf. A000041, A008967, A095944, A364911, A365376, A365377.

msubs[y_]:=primeMS/@Divisors[Times@@Prime/@y];
Table[Length[Select[IntegerPartitions[2n], Length[Union[Total/@Rest[msubs[#]]]]==n&]],{n,0,10}]

from collections import Counter
from sympy.utilities.iterables import partitions, multiset_combinations
def A365660(n):
    c = 0
    for p in partitions(n<<1):
        q, s = list(Counter(p).elements()), set()
        for l in range(1,len(q)+1):
            for k in multiset_combinations(q,l):
                s.add(sum(k))
                if len(s) > n:
                    break
            else:
                continue
            break
        if len(s)==n:
            c += 1
    return c # Chai Wah Wu, Sep 20 2023

a(21)-a(38) from Chai Wah Wu, Sep 20 2023

a(39)-a(43) from Chai Wah Wu, Sep 21 2023

cp's OEIS Frontend

A365541 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367216 Number of subsets of {1..n} whose cardinality is equal to the sum of some subset.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A365544 Number of subsets of {1..n} containing two distinct elements summing to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A360634 Number T(n,k) of sets of nonempty words over binary alphabet with a total of n letters of which k are the first letter; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A365659 Number of strict integer partitions of n that either have (1) length 2, or (2) greatest part n/2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A095941 Number of subsets of {1,2,...,n} such that every number in the set is no larger than the sum of the other numbers in the set.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A270144 a(n) = Sum_{k=0..n} (-1)^(k+1) * k * A000009(n-k).

Views

Author

Keywords