A325685 -id:A325685 - 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

A103295 Number of complete rulers with length n.

Original entry on oeis.org

1, 1, 1, 3, 4, 9, 17, 33, 63, 128, 248, 495, 988, 1969, 3911, 7857, 15635, 31304, 62732, 125501, 250793, 503203, 1006339, 2014992, 4035985, 8080448, 16169267, 32397761, 64826967, 129774838, 259822143, 520063531, 1040616486, 2083345793, 4168640894, 8342197304, 16694070805, 33404706520, 66832674546, 133736345590

Offset: 0

Peter Luschny, Feb 28 2005

nonn

For definitions, references and links related to complete rulers see A103294.
Also the number of compositions of n whose consecutive subsequence-sums cover an initial interval of the positive integers. For example, (2,3,1) is such a composition because (1), (2), (3), (3,1), (2,3), and (2,3,1) are subsequences with sums covering {1..6}. - Gus Wiseman, May 17 2019
a(n) ~ c*2^n, where 0.2427 < c < 0.2459. - Fei Peng, Oct 17 2019

			a(4) = 4 counts the complete rulers with length 4, {[0,2,3,4],[0,1,3,4],[0,1,2,4],[0,1,2,3,4]}.

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..49
Scott Harvey-Arnold, Steven J. Miller, and Fei Peng, Distribution of missing differences in diffsets, arXiv:2001.08931 [math.CO], 2020.
Peter Luschny, Perfect rulers
Hugo Pfoertner, Count complete rulers of given length. FORTRAN program.
Index entries for sequences related to perfect rulers.
Gus Wiseman, Illustration of A103295.

Cf. A103300 (Perfect rulers with length n). Main diagonal of A349976.

Cf. A000079, A126796, A143823, A169942, A325676, A325677, A325683, A325684, A325685.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],SubsetQ[ReplaceList[#,{_,s__,_}:>Plus[s]],Range[n]]&]],{n,0,15}] (* Gus Wiseman, May 17 2019 *)

a(n) = Sum_{i=0..n} A103294(n, i) = Sum_{i=A103298(n)..n} A103294(n, i).

a(30)-a(36) from Hugo Pfoertner, Mar 17 2005
a(37)-a(38) from Hugo Pfoertner, Dec 10 2021
a(39) from Hugo Pfoertner, Dec 16 2021

A325687 Triangle read by rows where T(n,k) is the number of length-k compositions of n such that every distinct consecutive subsequence has a different sum.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 0, 1, 1, 4, 4, 0, 1, 1, 5, 5, 0, 0, 1, 1, 6, 12, 4, 0, 0, 1, 1, 7, 12, 5, 0, 0, 0, 1, 1, 8, 25, 8, 4, 0, 0, 0, 1, 1, 9, 24, 12, 3, 0, 0, 0, 0, 1, 1, 10, 40, 32, 8, 4, 0, 0, 0, 0, 1, 1, 11, 41, 41, 6, 3, 0, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, May 13 2019

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

			The distinct consecutive subsequences of (1,1,3,3) are (1), (1,1), (3), (1,3), (1,1,3), (3,3), (1,3,3), (1,1,3,3), all of which have different sums, so (1,1,3,3) is counted under a(8).
Triangle begins:
  1
  1  1
  1  2  1
  1  3  0  1
  1  4  4  0  1
  1  5  5  0  0  1
  1  6 12  4  0  0  1
  1  7 12  5  0  0  0  1
  1  8 25  8  4  0  0  0  1
  1  9 24 12  3  0  0  0  0  1
  1 10 40 32  8  4  0  0  0  0  1
  1 11 41 41  6  3  0  0  0  0  0  1
  1 12 60 76 14  4  4  0  0  0  0  0  1
  1 13 60 88 16  6  3  0  0  0  0  0  0  1
Row n = 8 counts the following compositions:
  (8)  (17)  (116)  (1115)  (11111111)
       (26)  (125)  (1133)
       (35)  (143)  (2222)
       (44)  (152)  (3311)
       (53)  (215)  (5111)
       (62)  (233)
       (71)  (251)
             (332)
             (341)
             (512)
             (521)
             (611)

Row sums are A325676.
Column k = 2 is A000027.
Column k = 3 is A325688.
Cf. A000079, A007318, A048004, A108917, A143823, A169942, A266223, A325592, A325680, A325685.

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

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

A325684 Number of minimal complete rulers of length n.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 5, 12, 12, 24, 40, 46, 92, 133, 192, 308, 546, 710, 1108, 1754, 2726, 3878, 5928, 9260, 14238, 20502, 30812, 48378, 72232, 105744, 160308, 241592, 362348, 540362, 797750, 1183984, 1786714

Offset: 0

Gus Wiseman, May 13 2019

A complete ruler of length n is a subset of {0..n} containing 0 and n and such that the differences of distinct terms (up to sign) cover an initial interval of positive integers.

Also the number of maximal (most coarse) compositions of n whose consecutive subsequence-sums cover an initial interval of positive integers.

			The a(1) = 1 through a(7) = 12 rulers:
  {0,1}  {0,1,2}  {0,1,3}  {0,1,2,4}  {0,1,2,5}  {0,1,4,6}    {0,1,2,3,7}
                  {0,2,3}  {0,1,3,4}  {0,1,3,5}  {0,2,5,6}    {0,1,2,4,7}
                           {0,2,3,4}  {0,2,4,5}  {0,1,2,3,6}  {0,1,2,5,7}
                                      {0,3,4,5}  {0,1,3,5,6}  {0,1,3,5,7}
                                                 {0,3,4,5,6}  {0,1,3,6,7}
                                                              {0,1,4,5,7}
                                                              {0,1,4,6,7}
                                                              {0,2,3,6,7}
                                                              {0,2,4,6,7}
                                                              {0,2,5,6,7}
                                                              {0,3,5,6,7}
                                                              {0,4,5,6,7}
The a(1) = 1 through a(9) = 24 compositions:
  (1)  (11)  (12)  (112)  (113)  (132)   (1114)  (1133)   (1143)
             (21)  (121)  (122)  (231)   (1123)  (1241)   (1332)
                   (211)  (221)  (1113)  (1132)  (1322)   (2331)
                          (311)  (1221)  (1222)  (1412)   (3411)
                                 (3111)  (1231)  (1421)   (11115)
                                         (1312)  (2141)   (11124)
                                         (1321)  (2231)   (11142)
                                         (2131)  (3311)   (11241)
                                         (2221)  (11114)  (11322)
                                         (2311)  (11132)  (12141)
                                         (3211)  (23111)  (12222)
                                         (4111)  (41111)  (12231)
                                                          (12312)
                                                          (13221)
                                                          (14112)
                                                          (14121)
                                                          (14211)
                                                          (21141)
                                                          (21321)
                                                          (22221)
                                                          (22311)
                                                          (24111)
                                                          (42111)
                                                          (51111)

Cf. A000079, A103295, A126796, A143823, A169942, A325677, A325683, A325685.

fasmin[y_]:=Complement[y,Union@@Table[Union[s,#]&/@Rest[Subsets[Complement[Union@@y,s]]],{s,y}]];
Table[Length[fasmin[Accumulate/@Select[Join@@Permutations/@IntegerPartitions[n],SubsetQ[ReplaceList[#,{_,s__,_}:>Plus[s]],Range[n]]&]]],{n,0,15}]

a(16)-a(36) from Fausto A. C. Cariboni, Feb 27 2022

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

A325763 Heinz numbers of integer partitions whose consecutive subsequence-sums cover an initial interval of positive integers.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 48, 54, 56, 60, 64, 72, 80, 96, 100, 108, 112, 120, 128, 144, 160, 162, 168, 176, 180, 192, 200, 216, 224, 240, 256, 280, 288, 300, 320, 324, 336, 352, 360, 384, 392, 400, 416, 432, 448, 480, 486, 500, 504, 512

Offset: 1

Gus Wiseman, May 19 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

The enumeration of these partitions by sum appears to be A002865.

			The sequence of terms together with their prime indices begins:
     1: {}
     2: {1}
     4: {1,1}
     6: {1,2}
     8: {1,1,1}
    12: {1,1,2}
    16: {1,1,1,1}
    18: {1,2,2}
    20: {1,1,3}
    24: {1,1,1,2}
    32: {1,1,1,1,1}
    36: {1,1,2,2}
    40: {1,1,1,3}
    48: {1,1,1,1,2}
    54: {1,2,2,2}
    56: {1,1,1,4}
    60: {1,1,2,3}
    64: {1,1,1,1,1,1}
    72: {1,1,1,2,2}
    80: {1,1,1,1,3}

Cf. A002033, A103295, A103300, A169942, A325676, A325685, A325764, A325765.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Range[Total[primeMS[#]]]==Union[ReplaceList[primeMS[#],{_,s__,_}:>Plus[s]]]&]

A325789 Number of perfect necklace compositions of n.

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1

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 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.

			The a(1) = 1 , a(2) = 1, a(3) = 2, a(7) = 3, a(13) = 5, and a(31) = 11 perfect necklace compositions (A = 10, B = 11, C = 12, D = 13, E = 14):
  1  11  12   124      1264           12546D
         111  142      1327           1274C5
              1111111  1462           13278A
                       1723           13625E
                       1111111111111  15C472
                                      17324E
                                      1A8723
                                      1D6452
                                      1E4237
                                      1E5263
                                      1111111111111111111111111111111

Cf. A002033, A008965, A103300, A108917, A126796, A325676, A325679, A325685, A325780, A325782, A325786, A325787, 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/@IntegerPartitions[n],neckQ[#]&&Sort[Total/@subalt[#]]==Range[n]&]],{n,10}]

For n > 1, a(n) = A325787(n) + 1.

A325989 Number of perfect factorizations of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, May 30 2019

nonn

A perfect factorization of n is an orderless factorization of n into factors > 1 such that every divisor of n is the product of exactly one submultiset of the factors. This is the intersection of covering (or complete) factorizations (A325988) and knapsack factorizations (A292886).

			The a(216) = 4 perfect factorizations:
  (2*2*2*3*3*3)
  (2*2*2*3*9)
  (2*3*3*3*4)
  (2*3*4*9)

Positions of terms > 1 are A325990.

Cf. A002033, A103300, A292886, A325685, A325780, A325787, A325789, A325988.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],Sort[Times@@@Union[Subsets[#]]]==Divisors[n]&]],{n,100}]

a(2^n) = A002033(n).

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

A103295 Number of complete rulers with length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A325687 Triangle read by rows where T(n,k) is the number of length-k compositions of n such that every distinct consecutive subsequence has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A325684 Number of minimal complete rulers of length n.

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

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

A325763 Heinz numbers of integer partitions whose consecutive subsequence-sums cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples