A325682 -id:A325682 - cp's OEIS frontend

A325676 Number of compositions of n such that every distinct consecutive subsequence has a different sum.

1, 1, 2, 4, 5, 10, 12, 24, 26, 47, 50, 96, 104, 172, 188, 322, 335, 552, 590, 938, 1002, 1612, 1648, 2586, 2862, 4131, 4418, 6718, 7122, 10332, 11166, 15930, 17446, 24834, 26166, 37146, 41087, 55732, 59592, 84068, 89740, 122106, 133070, 177876, 194024, 262840, 278626

Offset: 0

Gus Wiseman, May 13 2019

nonn

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

Compare to the definition of knapsack partitions (A108917).

			The distinct consecutive subsequences of (1,4,4,3) together with their sums are:
   1: {1}
   3: {3}
   4: {4}
   5: {1,4}
   7: {4,3}
   8: {4,4}
   9: {1,4,4}
  11: {4,4,3}
  12: {1,4,4,3}
Because the sums are all different, (1,4,4,3) is counted under a(12).
The a(1) = 1 through a(6) = 12 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (13)    (14)     (15)
             (21)   (22)    (23)     (24)
             (111)  (31)    (32)     (33)
                    (1111)  (41)     (42)
                            (113)    (51)
                            (122)    (114)
                            (221)    (132)
                            (311)    (222)
                            (11111)  (231)
                                     (411)
                                     (111111)

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

Cf. A000079, A103295, A108917, A169942, A235998, A321143.

Cf. A325466, A325545, A325680, A325682, A325685, A325687, A325688.

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

a(21)-a(22) from Jinyuan Wang, Jun 20 2020
a(23)-a(25) from Robert Price, Jun 19 2021
a(26)-a(46) from Fausto A. C. Cariboni, Feb 10 2022

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

Original entry on oeis.org

1, 1, 2, 4, 5, 6, 8, 14, 16, 29, 24, 42, 46, 78, 66, 146, 133, 242, 208, 386, 352, 620, 494, 948, 842, 1447

Offset: 0

Gus Wiseman, May 13 2019

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

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) = 16 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (12)   (13)    (14)     (15)      (16)       (17)
             (21)   (22)    (23)     (24)      (25)       (26)
             (111)  (31)    (32)     (33)      (34)       (35)
                    (1111)  (41)     (42)      (43)       (44)
                            (11111)  (51)      (52)       (53)
                                     (222)     (61)       (62)
                                     (111111)  (124)      (71)
                                               (142)      (125)
                                               (214)      (152)
                                               (241)      (215)
                                               (412)      (251)
                                               (421)      (512)
                                               (1111111)  (521)
                                                          (2222)
                                                          (11111111)

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

Cf. A325545, A325676, A325682, A325685, A325687, A325688.

subalt[q_]:=Union[ReplaceList[q,{_,s__,_}:>{s}],DeleteCases[ReplaceList[q,{t___,,u___}:>{u,t}],{}]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@Total/@subalt[#]&]],{n,0,15}]

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

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

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

A325786 Number of complete necklace compositions of n.

Original entry on oeis.org

1, 1, 2, 2, 4, 7, 12, 19, 41, 71, 141, 255, 509, 924, 1882, 3395, 6838, 12715, 25233, 47049

Offset: 1

Gus Wiseman, May 22 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. A necklace composition of n is complete if every positive integer from 1 to n is the sum of some circular subsequence.

			The a(1) = 1 through a(8) = 19 necklace compositions:
  (1)  (11)  (12)   (112)   (113)    (123)     (124)      (1124)
             (111)  (1111)  (122)    (132)     (142)      (1133)
                            (1112)   (1113)    (1114)     (1142)
                            (11111)  (1122)    (1123)     (1214)
                                     (1212)    (1132)     (1223)
                                     (11112)   (1213)     (1322)
                                     (111111)  (1222)     (11114)
                                               (11113)    (11123)
                                               (11122)    (11132)
                                               (11212)    (11213)
                                               (111112)   (11222)
                                               (1111111)  (11312)
                                                          (12122)
                                                          (111113)
                                                          (111122)
                                                          (111212)
                                                          (112112)
                                                          (1111112)
                                                          (11111111)

Cf. A000740, A002033, A008965, A103295, A108917, A126796, A276024, A325549, A325682, A325781, A325788, A325789, A325791.

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[#]&&Union[Total/@subalt[#]]==Range[n]&]],{n,15}]

A325787 Number of perfect strict necklace compositions of n.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, May 22 2019

nonn

A strict necklace composition of n is a finite sequence of distinct positive integers summing to n that is lexicographically minimal among all of its cyclic rotations. In other words, it is a strict composition of n starting with its least part. A circular subsequence is a sequence of consecutive terms where the last and first parts are also considered consecutive. A necklace composition of n is perfect if every positive integer from 1 to n is the sum of exactly one distinct circular subsequence. For example, the composition (1,2,6,4) is perfect because it has the following circular subsequences and sums:
(1)
(2)
(1,2)
(4)
(4,1)
(6)
(4,1,2)
(2,6)
(1,2,6)
(6,4)
(6,4,1)
(2,6,4)
(1,2,6,4)
a(n) > 0 iff n = A002061(k) = A004136(k) for some k. - Bert Dobbelaere, Nov 11 2020

			The a(1) = 1 through a(31) = 10 perfect strict necklace compositions (empty columns not shown):
  (1)  (1,2)  (1,2,4)  (1,2,6,4)  (1,3,10,2,5)  (1,10,8,7,2,3)
              (1,4,2)  (1,3,2,7)  (1,5,2,10,3)  (1,13,6,4,5,2)
                       (1,4,6,2)                (1,14,4,2,3,7)
                       (1,7,2,3)                (1,14,5,2,6,3)
                                                (1,2,5,4,6,13)
                                                (1,2,7,4,12,5)
                                                (1,3,2,7,8,10)
                                                (1,3,6,2,5,14)
                                                (1,5,12,4,7,2)
                                                (1,7,3,2,4,14)
From _Bert Dobbelaere_, Nov 11 2020: (Start)
Compositions matching nonzero terms from a(57) to a(273), up to symmetry.
a(57) = 12:
  (1,2,10,19,4,7,9,5)
  (1,3,5,11,2,12,17,6)
  (1,3,8,2,16,7,15,5)
  (1,4,2,10,18,3,11,8)
  (1,4,22,7,3,6,2,12)
  (1,6,12,4,21,3,2,8)
a(73) = 8:
  (1,2,4,8,16,5,18,9,10)
  (1,4,7,6,3,28,2,8,14)
  (1,6,4,24,13,3,2,12,8)
  (1,11,8,6,4,3,2,22,16)
a(91) = 12:
  (1,2,6,18,22,7,5,16,4,10)
  (1,3,9,11,6,8,2,5,28,18)
  (1,4,2,20,8,9,23,10,3,11)
  (1,4,3,10,2,9,14,16,6,26)
  (1,5,4,13,3,8,7,12,2,36)
  (1,6,9,11,29,4,8,2,3,18)
a(133) = 36:
  (1,2,9,8,14,4,43,7,6,10,5,24)
  (1,2,12,31,25,4,9,10,7,11,16,5)
  (1,2,14,4,37,7,8,27,5,6,13,9)
  (1,2,14,12,32,19,6,5,4,18,13,7)
  (1,3,8,9,5,19,23,16,13,2,28,6)
  (1,3,12,34,21,2,8,9,5,6,7,25)
  (1,3,23,24,6,22,10,11,18,2,5,8)
  (1,4,7,3,16,2,6,17,20,9,13,35)
  (1,4,16,3,15,10,12,14,17,33,2,6)
  (1,4,19,20,27,3,6,25,7,8,2,11)
  (1,4,20,3,40,10,9,2,15,16,6,7)
  (1,5,12,21,29,11,3,16,4,22,2,7)
  (1,7,13,12,3,11,5,18,4,2,48,9)
  (1,8,10,5,7,21,4,2,11,3,26,35)
  (1,14,3,2,4,7,21,8,25,10,12,26)
  (1,14,10,20,7,6,3,2,17,4,8,41)
  (1,15,5,3,25,2,7,4,6,12,14,39)
  (1,22,14,20,5,13,8,3,4,2,10,31)
a(183) = 40:
  (1,2,13,7,5,14,34,6,4,33,18,17,21,8)
  (1,2,21,17,11,5,9,4,26,6,47,15,12,7)
  (1,2,28,14,5,6,9,12,48,18,4,13,16,7)
  (1,3,5,6,25,32,23,10,18,2,17,7,22,12)
  (1,3,12,7,20,14,44,6,5,24,2,28,8,9)
  (1,3,24,6,12,14,11,55,7,2,8,5,16,19)
  (1,4,6,31,3,13,2,7,14,12,17,46,8,19)
  (1,4,8,52,3,25,18,2,9,24,6,10,7,14)
  (1,4,20,2,12,3,6,7,33,11,8,10,35,31)
  (1,5,2,24,15,29,14,21,13,4,33,3,9,10)
  (1,5,23,27,42,3,4,11,2,19,12,10,16,8)
  (1,6,8,22,4,5,33,21,3,20,32,16,2,10)
  (1,8,3,10,23,5,56,4,2,14,15,17,7,18)
  (1,8,21,45,6,7,11,17,3,2,10,4,23,25)
  (1,9,5,40,3,4,21,35,16,18,2,6,11,12)
  (1,9,14,26,4,2,11,5,3,12,27,34,7,28)
  (1,9,21,25,3,4,8,5,6,16,2,36,14,33)
  (1,10,22,34,27,12,3,4,2,14,24,5,8,17)
  (1,10,48,9,19,4,8,6,7,17,3,2,34,15)
  (1,12,48,6,2,38,3,22,7,10,11,5,4,14)
a(273) = 12:
  (1,2,4,8,16,32,27,26,11,9,45,13,10,29,5,17,18)
  (1,3,12,10,31,7,27,2,6,5,19,20,62,14,9,28,17)
  (1,7,3,15,33,5,24,68,2,14,6,17,4,9,19,12,34)
  (1,7,12,44,25,41,9,17,4,6,22,33,13,2,3,11,23)
  (1,7,31,2,11,3,9,36,17,4,22,6,18,72,5,10,19)
  (1,21,11,50,39,13,6,4,14,16,25,26,3,2,7,8,27)
(End)

Bert Dobbelaere, Table of n, a(n) for n = 1..306

Cf. A002033, A002061, A004136, A008965, A032153, A103300, A126796, A325680, A325682, A325780, A325782, A325786, A325788, A325789.

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/@Select[IntegerPartitions[n],UnsameQ@@#&],neckQ[#]&&Sort[Total/@subalt[#]]==Range[n]&]],{n,30}]

More terms from Bert Dobbelaere, Nov 11 2020

cp's OEIS Frontend

A325676 Number of compositions of n such that every distinct consecutive subsequence has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

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

A325786 Number of complete necklace compositions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325787 Number of perfect strict necklace compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions