A325687 -id:A325687 - cp's OEIS frontend

A325592 Triangle read by rows where T(n,k) is the number of length-k knapsack partitions of n.

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 3, 2, 0, 0, 1, 0, 1, 3, 4, 2, 0, 0, 1, 0, 1, 4, 3, 3, 0, 0, 0, 1, 0, 1, 4, 7, 2, 2, 0, 0, 0, 1, 0, 1, 5, 6, 4, 2, 0, 0, 0, 0, 1, 0, 1, 5, 10, 6, 4, 2, 0, 0, 0, 0, 1, 0, 1, 6, 9, 5, 1, 2, 0, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, May 15 2019

A knapsack partition of n is an integer partition of n whose distinct submultisets all have different sums.

			Triangle begins:
  1
  0  1
  0  1  1
  0  1  1  1
  0  1  2  0  1
  0  1  2  2  0  1
  0  1  3  2  0  0  1
  0  1  3  4  2  0  0  1
  0  1  4  3  3  0  0  0  1
  0  1  4  7  2  2  0  0  0  1
  0  1  5  6  4  2  0  0  0  0  1
  0  1  5 10  6  4  2  0  0  0  0  1
  0  1  6  9  5  1  2  0  0  0  0  0  1
  0  1  6 14 10  5  2  2  0  0  0  0  0  1
  0  1  7 13 11  3  3  2  0  0  0  0  0  0  1
  0  1  7 19 16  7  3  2  2  0  0  0  0  0  0  1
Row n = 12 counts the following partitions (A = 10, B = 11, C = 12):
   (C)  (66)   (444)   (3333)  (81111)  (222222)  (111111111111)
        (75)   (543)   (5511)           (711111)
        (84)   (552)   (7221)
        (93)   (732)   (7311)
        (A2)   (741)   (9111)
        (B1)   (822)
               (831)
               (921)
               (A11)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..10010

Row sums are A000041.
Column k = 2 is A004526.
Column k = 3 is A325690.
Cf. A002219, A006827, A108917, A143823, A169942, A275972, A276024, A292886, A321143, A325676, A325687.

Table[Length[Select[IntegerPartitions[n,{k}],UnsameQ@@Total/@Union[Subsets[#]]&]],{n,0,15},{k,0,n}]

A325679 Number of compositions of n such that every restriction to a circular subinterval has a different sum.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 5, 13, 13, 27, 21, 41, 41, 77, 63, 143, 129, 241, 203, 385, 347, 617, 491, 947, 835, 1445, 1185, 2511, 1991, 3585, 2915, 5411, 4569, 8063, 6321, 11131, 10133, 16465, 13207, 23817, 20133, 33929, 26663, 48357, 41363, 69605, 54363, 95727, 81183, 132257, 106581

Offset: 0

Gus Wiseman, May 13 2019

nonn

A composition of n is a finite sequence of positive integers summing to n.
A circular subinterval is a sequence of consecutive indices where the first and last indices are also considered consecutive.
For n > 0, a(n) is the number of subsets of Z_n which contain 0 and such that every ordered pair of distinct elements has a different difference (modulo n). The elements of a subset correspond with the partial sums of a composition. For example, when n = 8 the subset {0,2,7} corresponds with the composition (251). - Andrew Howroyd, Mar 24 2025

			The a(1) = 1 through a(8) = 13 compositions:
  (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)
            (12)  (13)  (14)  (15)  (16)   (17)
            (21)  (31)  (23)  (24)  (25)   (26)
                        (32)  (42)  (34)   (35)
                        (41)  (51)  (43)   (53)
                                    (52)   (62)
                                    (61)   (71)
                                    (124)  (125)
                                    (142)  (152)
                                    (214)  (215)
                                    (241)  (251)
                                    (412)  (512)
                                    (421)  (521)

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

Cf. A000079, A008965, A108917, A143823, A169942, A276024.

Cf. A325545, A325676, A325677, A325678, A325680, A325681, A325687, A382399.

suball[q_]:=Join[Take[q,#]&/@Select[Tuples[Range[Length[q]],2],OrderedQ],Drop[q,#]&/@Select[Tuples[Range[2,Length[q]-1],2],OrderedQ]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@Total/@suball[#]&]],{n,0,15}]

a(n)={
   my(recurse(k,b,w)=
      if(k >= n, 1,
         b+=1<Andrew Howroyd, Mar 24 2025

a(21) onwards from Andrew Howroyd, Mar 24 2025

A325678 Maximum length of a composition of n such that every restriction to a subinterval has a different sum.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

Offset: 0

Gus Wiseman, May 13 2019

nonn

A composition of n is a finite sequence of positive integers summing to n.

Also the maximum number of nonzero marks on a Golomb ruler of length n.

Run-lengths are A270813.
Cf. A000079, A007318, A103295, A108917, A143823, A169942.
Cf. A325466, A325676, A325677, A325679, A325681, A325683, A325687.

Table[Max[Length/@Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@ReplaceList[#,{_,s__,_}:>Plus[s]]&]],{n,0,15}]

a(n) + 1 = A143824(n + 1).

A325688 Number of length-3 compositions of n such that every distinct consecutive subsequence has a different sum.

Original entry on oeis.org

0, 0, 0, 1, 0, 4, 5, 12, 12, 25, 24, 40, 41, 60, 60, 85, 84, 112, 113, 144, 144, 181, 180, 220, 221, 264, 264, 313, 312, 364, 365, 420, 420, 481, 480, 544, 545, 612, 612, 685, 684, 760, 761, 840, 840, 925, 924, 1012, 1013, 1104, 1104, 1201, 1200, 1300, 1301, 1404

Offset: 0

Gus Wiseman, May 15 2019

nonn

A composition of n is a finite sequence of positive integers summing to n.

Confirmed recurrence relation from Colin Barker for n <= 5000. - Fausto A. C. Cariboni, Feb 13 2022

			The a(3) = 1 through a(8) = 12 compositions:
  (111)  (113)  (114)  (115)  (116)
         (122)  (132)  (124)  (125)
         (221)  (222)  (133)  (143)
         (311)  (231)  (142)  (152)
                (411)  (214)  (215)
                       (223)  (233)
                       (241)  (251)
                       (322)  (332)
                       (331)  (341)
                       (412)  (512)
                       (421)  (521)
                       (511)  (611)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..5000

Column k = 3 of A325687.
Cf. A000217 (all length-3).
Cf. A000079, A001399, A005044, A008642, A069905, A108917, A124278, A266223.
Cf. A325686, A325689, A325690, A325691.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{3}],UnsameQ@@Total/@Union[ReplaceList[#,{_,s__,_}:>{s}]]&]],{n,0,30}]

Conjectures from Colin Barker, May 16 2019: (Start)
G.f.: x^3*(1 + 2*x^2 + 4*x^3 + 5*x^4) / ((1 - x)^3*(1 + x)^2*(1 + x + x^2)).
a(n) = 2*a(n-2) + a(n-3) - a(n-4) - 2*a(n-5) + a(n-7) for n>7.
(End)

A354580 Number of rucksack compositions of n: every distinct partial run has a different sum.

Original entry on oeis.org

1, 1, 2, 4, 6, 12, 22, 39, 68, 125, 227, 402, 710, 1280, 2281, 4040, 7196, 12780, 22623, 40136, 71121, 125863, 222616, 393305, 695059, 1227990, 2167059, 3823029, 6743268, 11889431, 20955548, 36920415, 65030404, 114519168, 201612634, 354849227

Offset: 0

Gus Wiseman, Jun 13 2022

nonn

We define a partial run of a sequence to be any contiguous constant subsequence. The term rucksack is short for run-knapsack.

			The a(0) = 1 through a(5) = 12 compositions:
  ()  (1)  (2)    (3)      (4)        (5)
           (1,1)  (1,2)    (1,3)      (1,4)
                  (2,1)    (2,2)      (2,3)
                  (1,1,1)  (3,1)      (3,2)
                           (1,2,1)    (4,1)
                           (1,1,1,1)  (1,1,3)
                                      (1,2,2)
                                      (1,3,1)
                                      (2,1,2)
                                      (2,2,1)
                                      (3,1,1)
                                      (1,1,1,1,1)

Max Alekseyev, Table of n, a(n) for n = 0..65

The knapsack version is A325676, ranked by A333223.
The non-partial version for partitions is A353837, ranked by A353838 (complement A353839).
The non-partial version is A353850, ranked by A353852.
The version for partitions is A353864, ranked by A353866.
The complete version for partitions is A353865, ranked by A353867.
These compositions are ranked by A354581.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A108917 counts knapsack partitions, ranked by A299702, strict A275972.
A238279 and A333755 count compositions by number of runs.
A275870 counts collapsible partitions, ranked by A300273.
A353836 counts partitions by number of distinct run-sums.
A353847 is the composition run-sum transformation.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353853-A353859 pertain to composition run-sum trajectory.
A353860 counts collapsible compositions, ranked by A354908.
Cf. A143823, A169942, A242882, A325545, A325680, A325682, A325685, A325687, A329739, A351017, A353849.

Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n],UnsameQ@@Total/@Union@@Subsets/@Split[#]&]],{n,0,15}]

Terms a(16) onward from Max Alekseyev, Sep 10 2023

A325682 Number of necklace compositions of n such that every distinct circular subsequence has a different sum.

Original entry on oeis.org

1, 2, 3, 4, 4, 6, 7, 9, 13, 12, 17, 21, 28, 26, 49, 46, 74, 68, 113, 107, 176, 144, 255, 235, 375

Offset: 1

Gus Wiseman, May 13 2019

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

A circular subsequence is a sequence of consecutive terms where the first and last parts are also considered consecutive.

			The a(1) = 1 through a(8) = 13 necklace compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (12)   (13)    (14)     (15)      (16)       (17)
             (111)  (22)    (23)     (24)      (25)       (26)
                    (1111)  (11111)  (33)      (34)       (35)
                                     (222)     (124)      (44)
                                     (111111)  (142)      (125)
                                               (1111111)  (152)
                                                          (2222)
                                                          (11111111)

Cf. A000079, A000740, A008965, A059966, A108917, A143823, A169942, A276024.

Cf. A325676, A325680, A325685, A325687.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
subalt[q_]:=Union[ReplaceList[q,{_,s__,_}:>{s}],DeleteCases[ReplaceList[q,{t___,,u___}:>{u,t}],{}]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&UnsameQ@@Total/@subalt[#]&]],{n,20}]

a(21)-a(25) from Robert Price, Jun 19 2021

A325681 Number of necklace compositions of n such that every restriction to a circular subinterval has a different sum.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 6, 6, 11, 9, 16, 16, 27, 23, 46, 42, 73, 63, 112, 102, 173, 141, 254, 228, 373, 313, 614, 500, 855, 709, 1252, 1074, 1827, 1457, 2470, 2260, 3559, 2905, 5044, 4294, 6997, 5623, 9752, 8422, 13741, 10913, 18562, 15912, 25213, 20569, 35146, 29286, 46307, 38241, 61396

Offset: 1

Gus Wiseman, May 13 2019

nonn

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

A circular subinterval is a sequence of consecutive indices where the first and last indices are also considered consecutive.

			The a(1) = 1 through a(10) = 9 necklace compositions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)    (9)    (A)
            (12)  (13)  (14)  (15)  (16)   (17)   (18)   (19)
                        (23)  (24)  (25)   (26)   (27)   (28)
                                    (34)   (35)   (36)   (37)
                                    (124)  (125)  (45)   (46)
                                    (142)  (152)  (126)  (127)
                                                  (135)  (136)
                                                  (153)  (163)
                                                  (162)  (172)
                                                  (234)
                                                  (243)

Andrew Howroyd, Table of n, a(n) for n = 1..80

Cf. A000079, A000740, A008965, A108917, A143823, A169942, A276024.

Cf. A325676, A325677, A325678, A325679, A325682, A325683, A325687.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
suball[q_]:=Join[Take[q,#]&/@Select[Tuples[Range[Length[q]],2],OrderedQ],Drop[q,#]&/@Select[Tuples[Range[2,Length[q]-1],2],OrderedQ]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&UnsameQ@@Total/@suball[#]&]],{n,15}]

a(n)={
   my(recurse(k,r,b,w)=
      if(k >= n, 1/r,
         b+=1<Andrew Howroyd, Mar 25 2025

a(21) onwards from Andrew Howroyd, Mar 24 2025

A308251 Number of subsets of {1,...,n + 1} containing n + 1 and such that all positive differences of distinct elements are distinct.

Original entry on oeis.org

1, 2, 3, 6, 9, 14, 21, 34, 49, 76, 101, 146, 205, 294, 397, 560, 747, 1028, 1341, 1810, 2343, 3178, 4051, 5370, 6921, 9014, 11361, 14838, 18719, 24082, 29953, 38220, 47663, 60550, 74619, 93848, 115961, 145320, 177549, 221676, 270335, 335124

Offset: 0

Gus Wiseman, May 17 2019

nonn

Also the number of subsets of {1...n} containing no positive differences of the elements and such that all such differences are distinct.

			The a(0) = 1 through a(5) = 14 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}
                     {1,3,4}  {1,2,5}  {5,6}
                              {1,4,5}  {1,2,6}
                              {2,3,5}  {1,3,6}
                              {2,4,5}  {1,4,6}
                                       {1,5,6}
                                       {2,3,6}
                                       {2,5,6}
                                       {3,4,6}
                                       {3,5,6}

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..99 (terms 0..41 from Gus Wiseman, terms 42..80 from Vaclav Kotesovec)

Cf. A000079, A108917, A143823, A143824, A169942, A325676, A325677, A325683, A325687.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&UnsameQ@@Abs[Subtract@@@Subsets[#,{2}]]&]],{n,15}]

First differences of A143823. Partial sums of A169942.

A334268 Number of compositions of n where every distinct subsequence (not necessarily contiguous) has a different sum.

Original entry on oeis.org

1, 1, 2, 4, 5, 10, 10, 24, 24, 43, 42, 88, 72, 136, 122, 242, 213, 392, 320, 630, 490, 916, 742, 1432, 1160, 1955, 1604, 2826, 2310, 3850, 2888, 5416, 4426, 7332, 5814, 10046, 7983, 12946, 10236, 17780, 14100, 22674, 17582, 30232, 23674, 37522, 29426, 49832

Offset: 0

Gus Wiseman, Jun 02 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

The contiguous case is A325676.

			The a(1) = 1 through a(6) = 19 compositions:
  (1)  (2)    (3)      (4)        (5)          (6)
       (1,1)  (1,2)    (1,3)      (1,4)        (1,5)
              (2,1)    (2,2)      (2,3)        (2,4)
              (1,1,1)  (3,1)      (3,2)        (3,3)
                       (1,1,1,1)  (4,1)        (4,2)
                                  (1,1,3)      (5,1)
                                  (1,2,2)      (1,1,4)
                                  (2,2,1)      (2,2,2)
                                  (3,1,1)      (4,1,1)
                                  (1,1,1,1,1)  (1,1,1,1,1,1)

These compositions are ranked by A334967.
Compositions where every restriction to a subinterval has a different sum are counted by A169942 and A325677 and ranked by A333222. The case of partitions is counted by A325768 and ranked by A325779.
Positive subset-sums of partitions are counted by A276024 and A299701.
Knapsack partitions are counted by A108917 and A325592 and ranked by A299702, while the strict case is counted by A275972 and ranked by A059519 and A301899.
Knapsack compositions are counted by A325676 and A325687 and ranked by A333223. The case of partitions is counted by A325769 and ranked by A325778, for which the number of distinct consecutive subsequences is given by A325770.
Cf. A003022, A029931, A103295, A143823, A325680, A333224.

b:= proc(n, s) option remember; `if`(n=0, 1, add((h->
      `if`(nops(h)=nops(map(l-> add(i, i=l), h)),
       b(n-j, h), 0))({s[], map(l-> [l[], j], s)[]}), j=1..n))
    end:
a:= n-> b(n, {[]}):
seq(a(n), n=0..23);  # Alois P. Heinz, Jun 03 2020

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@Total/@Union[Subsets[#]]&]],{n,0,15}]

a(18)-a(47) from Alois P. Heinz, Jun 03 2020

cp's OEIS Frontend

A325592 Triangle read by rows where T(n,k) is the number of length-k knapsack partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325679 Number of compositions of n such that every restriction to a circular subinterval has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A325678 Maximum length of a composition of n such that every restriction to a subinterval has a different sum.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A325688 Number of length-3 compositions of n such that every distinct consecutive subsequence has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A354580 Number of rucksack compositions of n: every distinct partial run has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A325682 Number of necklace compositions of n such that every distinct circular subsequence has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A325681 Number of necklace compositions of n such that every restriction to a circular subinterval has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A308251 Number of subsets of {1,...,n + 1} containing n + 1 and such that all positive differences of distinct elements are distinct.

Views

Author

Keywords