Displaying 1-10 of 54 results found.
Number of compositions of n such that every distinct consecutive subsequence has a different sum.
+10
57
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
COMMENTS
A composition of n is a finite sequence of positive integers summing to n.
Compare to the definition of knapsack partitions ( A108917).
EXAMPLE
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)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@Total/@Union[ReplaceList[#, {___, s__, ___}:>{s}]]&]], {n, 0, 15}]
Number of distinct runs in the n-th composition in standard order.
+10
52
0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2, 1, 1, 2, 2, 2, 1, 3, 3, 2, 2, 3, 1, 2, 3, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 2, 3, 2, 2, 2, 3, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 3, 2, 3, 2, 2, 3
COMMENTS
The n-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of n, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.
EXAMPLE
The number 3310 has binary expansion 110011101110 and standard composition (1,3,1,1,2,1,1,2), with runs (1), (3), (1,1), (2), (1,1), (2), of which 4 are distinct, so a(3310) = 4.
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Length[Union[Split[stc[n]]]], {n, 0, 100}]
CROSSREFS
Counting not necessarily distinct runs gives A124767. Using binary expansions instead of standard compositions gives A297770. Positions of first appearances are A351015. A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A085207 represents concatenation of standard compositions, reverse A085208.
A351204 counts partitions where every permutation has all distinct runs.
Counting words with all distinct runs:
- A351202 = permutations of prime factors. Selected statistics of standard compositions:
- Number of distinct parts is A334028. Selected classes of standard compositions:
- Constant compositions are A272919. Cf. A098859, A106356, A116608, A238279, A242882, A318928, A325545, A328592, A329745, A350952, A351201.
Number of compositions of n whose run-lengths are all different.
+10
51
1, 1, 2, 2, 5, 8, 10, 20, 28, 41, 62, 102, 124, 208, 278, 426, 571, 872, 1158, 1718, 2306, 3304, 4402, 6286, 8446, 11725, 15644, 21642, 28636, 38956, 52296, 70106, 93224, 124758, 165266, 218916, 290583, 381706, 503174, 659160, 865020, 1124458, 1473912, 1907298
COMMENTS
A composition of n is a finite sequence of positive integers with sum n.
EXAMPLE
The a(1) = 1 through a(7) = 20 compositions:
(1) (2) (3) (4) (5) (6) (7)
(11) (111) (22) (113) (33) (115)
(112) (122) (114) (133)
(211) (221) (222) (223)
(1111) (311) (411) (322)
(1112) (1113) (331)
(2111) (3111) (511)
(11111) (11112) (1114)
(21111) (1222)
(111111) (2221)
(4111)
(11113)
(11122)
(22111)
(31111)
(111112)
(111211)
(112111)
(211111)
(1111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@Length/@Split[#]&]], {n, 0, 10}]
CROSSREFS
Compositions with relatively prime run-lengths are A000740. Compositions with distinct multiplicities are A242882. Compositions with distinct differences are A325545. Compositions with equal run-lengths are A329738. Compositions with normal run-lengths are A329766.
Length of shortest (or optimal) Golomb ruler with n marks.
(Formerly M2540)
+10
49
1, 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, 372, 425, 480, 492, 553, 585
COMMENTS
a(n) is the least integer such that there is an n-element set of integers between 0 and a(n), the sums of pairs (of not necessarily distinct elements) of which are distinct.
An n-mark Golomb ruler has a unique integer distance between any pair of marks and thus measures n(n-1)/2 distinct integer distances.
An optimal n-mark Golomb ruler has the smallest possible length (distance between the two end marks) for an n-mark ruler.
A perfect n-mark Golomb ruler has length exactly n(n-1)/2 and measures each distance from 1 to n(n-1)/2. (End)
Also the smallest m such that there exists a length-n composition of m for which every restriction to a subinterval has a different sum. Representatives of compositions for the first few terms are:
0: ()
1: (1)
3: (2,1)
6: (2,3,1)
11: (3,1,5,2)
17: (4,2,3,7,1)
Representatives of corresponding Golomb rulers are:
{0}
{0,1}
{0,2,3}
{0,2,5,6}
{0,3,4,9,11}
{0,4,6,9,16,17}
(End)
REFERENCES
CRC Handbook of Combinatorial Designs, 1996, p. 315.
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff.
S. W. Golomb, How to number a graph, pp. 23-37 of R. C. Read, editor, Graph Theory and Computing. Academic Press, NY, 1972.
Richard K. Guy, Unsolved Problems in Number Theory (2nd edition), Springer-Verlag (1994), Section C10.
A. Kotzig and P. J. Laufer, Sum triangles of natural numbers having minimum top, Ars. Combin. 21 (1986), 5-13.
Miller, J. C. P., Difference bases. Three problems in additive number theory. Computers in number theory (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969), pp. 299--322. Academic Press, London,1971. MR0316269 (47 #4817)
Rhys Price Jones, Gracelessness, Proc. 10th S.-E. Conf. Combin., Graph Theory and Computing, 1979, pp. 547-552.
Ana Salagean, David Gardner and Raphael Phan, Index Tables of Finite Fields and Modular Golomb Rulers, in Sequences and Their Applications - SETA 2012, Lecture Notes in Computer Science. Volume 7280, 2012, pp. 136-147.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
A. K. Dewdney, Computer Recreations, Scientific Amer. 253 (No. 6, Jun), 1985, pp. 16ff; 254 (No. 3, March), 1986, pp. 20ff. [Annotated scanned copy]
FORMULA
a(n) >= n(n-1)/2, with strict inequality for n >= 5 (Golomb). - David W. Wilson, Aug 18 2007
EXAMPLE
a(5)=11 because 0-1-4-9-11 (0-2-7-10-11) resp. 0-3-4-9-11 (0-2-7-8-11) are shortest: there is no b0-b1-b2-b3-b4 with different distances |bi-bj| and max. |bi-bj| < 11.
MATHEMATICA
Min@@Total/@#&/@GatherBy[Select[Join@@Permutations/@Join@@Table[IntegerPartitions [i], {i, 0, 15}], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&], Length] (* Gus Wiseman, May 17 2019 *)
CROSSREFS
0-1-4-9-11 corresponds to 1-3-5-2 in A039953: 0+1+3+5+2=11 A row or column of array in A234943.
EXTENSIONS
a(25), a(26) proved by OGR-25 and OGR-26 projects, added by Max Alekseyev, Sep 29 2010
Number of Golomb rulers of length n.
+10
49
1, 1, 3, 3, 5, 7, 13, 15, 27, 25, 45, 59, 89, 103, 163, 187, 281, 313, 469, 533, 835, 873, 1319, 1551, 2093, 2347, 3477, 3881, 5363, 5871, 8267, 9443, 12887, 14069, 19229, 22113, 29359, 32229, 44127, 48659, 64789, 71167, 94625, 105699, 139119, 151145, 199657
COMMENTS
Wanted: a recurrence. Are any of A169940- A169954 related to any other entries in the OEIS? Leading entry in row n of triangle in A169940. Also the number of Sidon sets A with min(A) = 0 and max(A) = n. Odd for all n since {0,n} is the only symmetric Golomb ruler, and reversal preserves the Golomb property. Bounded from above by A032020 since the ruler {0 < r_1 < ... < r_t < n} gives rise to a composition of n: (r_1 - 0, r_2 - r_1, ... , n - r_t) with distinct parts. - Tomas Boothby, May 15 2012 Also the number of compositions of n such that every restriction to a subinterval has a different sum. This is a stronger condition than all distinct consecutive subsequences having a different sum (cf. A325676). - Gus Wiseman, May 16 2019
EXAMPLE
For n=2, there is one Golomb Ruler: {0,2}. For n=3, there are three: {0,3}, {0,1,3}, {0,2,3}. - Tomas Boothby, May 15 2012 The a(1) = 1 through a(8) = 15 compositions such that every restriction to a subinterval has a different sum:
(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)
(132) (52) (62)
(231) (61) (71)
(124) (125)
(142) (143)
(214) (152)
(241) (215)
(412) (251)
(421) (341)
(512)
(521)
(End)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@ReplaceList[#, {___, s__, ___}:>Plus[s]]&]], {n, 15}] (* Gus Wiseman, May 16 2019 *)
PROG
(Sage)
R = QQ['x']
return sum(1 for c in cartesian_product([[0, 1]]*n) if max(R([1] + list(c) + [1])^2) == 2)
CROSSREFS
Cf. A000079, A103295, A103300, A108917, A143824, A325466, A325545, A325676, A325678, A325679, A325683, A325686.
Number of arithmetic progressions (where the difference between adjacent terms is either positive, 0, or negative) of positive integers that sum to n.
+10
43
1, 2, 4, 5, 6, 10, 8, 10, 15, 14, 12, 22, 14, 18, 28, 21, 18, 34, 20, 28, 38, 28, 24, 46, 31, 32, 48, 38, 30, 62, 32, 40, 58, 42, 46, 73, 38, 46, 68, 58, 42, 84, 44, 56, 90, 56, 48, 94, 55, 70, 90, 66, 54, 106, 70, 74, 100, 70, 60, 130, 62, 74, 118, 81, 82, 130, 68, 84, 120
FORMULA
G.f.: x/(1-x) + Sum_{k>=2} x^k * (1 + x^(k(k-1)/2)) / (1 - x^(k(k-1)/2)) / (1 -x^k).
EXAMPLE
The a(1) = 1 through a(8) = 10 compositions with equal differences:
(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)
(123) (61) (62)
(222) (1111111) (71)
(321) (2222)
(111111) (11111111)
(End)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ@@Differences[#]&]], {n, 0, 15}] (* returns a(0) = 1, Gus Wiseman, May 15 2019*)
CROSSREFS
Cf. A000005, A000079, A049980, A049981, A049982, A049983, A049986, A049987, A049988, A049989, A049990, A070211, A127938, A175327, A325328, A325407, A325545, A325546, A325547, A325548, A325557, A325558.
Those positive integers n that when written in binary, the lengths of the runs of 1 are distinct and the lengths of the runs of 0's are distinct.
+10
42
1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 15, 16, 19, 23, 24, 25, 28, 29, 30, 31, 32, 35, 38, 39, 44, 47, 48, 49, 50, 52, 55, 56, 57, 59, 60, 61, 62, 63, 64, 67, 70, 71, 78, 79, 88, 92, 95, 96, 97, 98, 103, 104, 111, 112, 113, 114, 115, 116, 120, 121, 123, 124, 125
COMMENTS
A044813 contains those positive integers that when written in binary, have all run-lengths (of both 0's and 1's) distinct.
A175414 contains those positive integers in A175413 that are not in A044813. ( A175414 contains those positive integers that when written in binary, at least one run of 0's is the same length as one run of 1's, even though all run of 0 are of distinct length and all runs of 1's are of distinct length.)
Also numbers whose binary expansion has all distinct runs (not necessarily run-lengths). - Gus Wiseman, Feb 21 2022
MAPLE
q:= proc(n) uses ListTools; (l-> is(nops(l)=add(
nops(i), i={Split(`=`, l, 1)}) +add(
nops(i), i={Split(`=`, l, 0)})))(Bits[Split](n))
end:
MATHEMATICA
f[n_] := And@@Unequal@@@Transpose[Partition[Length/@Split[IntegerDigits[n, 2]], 2, 2, {1, 1}, 0]]; Select[Range[125], f] (* Ray Chandler, Oct 21 2011 *) Select[Range[0, 100], UnsameQ@@Split[IntegerDigits[#, 2]]&] (* Gus Wiseman, Feb 21 2022 *)
PROG
(Python)
from itertools import groupby, product
def ok(n):
runs = [(k, len(list(g))) for k, g in groupby(bin(n)[2:])]
return len(runs) == len(set(runs))
CROSSREFS
A242882 counts compositions with distinct multiplicities.
A318928 gives runs-resistance of binary expansion.
A325545 counts compositions with distinct differences.
A334028 counts distinct parts in standard compositions.
A351014 counts distinct runs in standard compositions.
Counting words with all distinct runs:
- A351202 = permutations of prime factors.
Sum of divisors of n minus the number of divisors of n.
+10
41
0, 1, 2, 4, 4, 8, 6, 11, 10, 14, 10, 22, 12, 20, 20, 26, 16, 33, 18, 36, 28, 32, 22, 52, 28, 38, 36, 50, 28, 64, 30, 57, 44, 50, 44, 82, 36, 56, 52, 82, 40, 88, 42, 78, 72, 68, 46, 114, 54, 87, 68, 92, 52, 112, 68, 112, 76, 86, 58, 156, 60, 92, 98, 120, 80, 136, 66, 120, 92
COMMENTS
Number of permutations p of {1,2,...,n} such that p(k)-k takes exactly two distinct values. Example: a(4)=4 because we have 4123, 3412, 2143 and 2341. - Max Alekseyev and Emeric Deutsch, Dec 22 2006 Number of solutions to the Diophantine equation xy + yz = n, with x,y,z >= 1.
In other words, number of ways to write n = (a + b) * k for positive integers a, b, k. - Gus Wiseman, Mar 25 2021 Also the number of compositions of n into an even number of parts with alternating parts equal. These are finite even-length sequences q of positive integers summing to n such that q(i) = q(i+2) for all possible i. For example, the a(2) = 1 through a(8) = 11 compositions are:
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)
(2,1) (2,2) (2,3) (2,4) (2,5) (2,6)
(3,1) (3,2) (3,3) (3,4) (3,5)
(1,1,1,1) (4,1) (4,2) (4,3) (4,4)
(5,1) (5,2) (5,3)
(1,2,1,2) (6,1) (6,2)
(2,1,2,1) (7,1)
(1,1,1,1,1,1) (1,3,1,3)
(2,2,2,2)
(3,1,3,1)
(1,1,1,1,1,1,1,1)
The version with alternating parts weakly decreasing is A114921, or A342528 if odd-length compositions are included. Allowing odd lengths as well as even gives A342527. (End)
FORMULA
G.f.: Sum_{n>=1} (n-1)*x^n/(1-x^n). - Joerg Arndt, Jan 30 2011 L.g.f.: -log(Product_{k>=1} (1 - x^k)^(1-1/k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Mar 18 2018 G.f.: Sum_{n >= 1} q^(n^2)*( (n - 1) + q^n - (n - 1)*q^(2*n) )/(1 - q^n)^2 - differentiate equation 1 in Arndt with respect to t, then set x = q and t = q. - Peter Bala, Jan 22 2021 a(n) = n * A010054(n) - Sum_{k>=1} a(n - k*(k+1)/2), assuming a(n) = 0 for n <= 0 (Kobayashi, 2022). - Amiram Eldar, Jun 23 2023
MAPLE
with(numtheory): seq(sigma(n)-tau(n), n=1..70); # Emeric Deutsch, Dec 22 2006
MATHEMATICA
Table[DivisorSigma[1, n]-DivisorSigma[0, n], {n, 100}] (* Wesley Ivan Hurt, Dec 26 2013 *)
PROG
(GAP) List([1..100], n->Sigma(n)-Tau(n)); # Muniru A Asiru, Mar 19 2018 (Python)
from math import prod
from sympy import factorint
f = factorint(n).items()
return prod((p**(e+1)-1)//(p-1) for p, e in f)-prod(e+1 for p, e in f) # Chai Wah Wu, Jul 16 2022
CROSSREFS
A175342/ A325545 count compositions with constant/distinct differences.
Number of integer compositions of n with all distinct runs.
+10
36
1, 1, 2, 4, 7, 14, 26, 48, 88, 161, 294, 512, 970, 1634, 2954, 5156, 9119, 15618, 27354, 46674, 80130, 138078, 232286, 394966, 665552, 1123231, 1869714, 3146410, 5186556, 8620936, 14324366, 23529274, 38564554, 63246744, 103578914, 167860584, 274465845
EXAMPLE
The a(1) = 1 through a(5) = 14 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,1,2) (4,1)
(2,1,1) (1,1,3)
(1,1,1,1) (1,2,2)
(2,2,1)
(3,1,1)
(1,1,1,2)
(1,1,2,1)
(1,2,1,1)
(2,1,1,1)
(1,1,1,1,1)
For example, the composition c = (3,1,1,1,1,2,1,1,3,4,1,1) has runs (3), (1,1,1,1), (2), (1,1), (3), (4), (1,1), and since (3) and (1,1) both appear twice, c is not counted under a(20).
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], UnsameQ@@Split[#]&]], {n, 0, 10}]
PROG
(PARI) \\ here LahI is A111596 as row polynomials. LahI(n, y) = {sum(k=1, n, y^k*(-1)^(n-k)*(n!/k!)*binomial(n-1, k-1))}
S(n) = {my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); 1 + sum(i=1, (sqrtint(8*n+1)-1)\2, polcoef(p, i, y)*LahI(i, y))}
seq(n)={my(q=S(n)); [subst(serlaplace(p), y, 1) | p<-Vec(prod(k=1, n, subst(q + O(x*x^(n\k)), x, x^k)))]} \\ Andrew Howroyd, Feb 12 2022
CROSSREFS
The version for run-lengths instead of runs is A329739, normal A329740. A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A116608 counts compositions by number of distinct parts.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329744 counts compositions by runs-resistance.
A351014 counts distinct runs in standard compositions.
Counting words with all distinct runs:
- A351202 = permutations of prime factors. Cf. A003242, A025047, A044813, A098504, A098859, A106356, A329738, A328592, A334028, A351015, A351201, A351204.
Number of binary words of length n with all distinct run-lengths.
+10
30
1, 2, 2, 6, 6, 10, 22, 26, 38, 54, 114, 130, 202, 266, 386, 702, 870, 1234, 1702, 2354, 3110, 5502, 6594, 9514, 12586, 17522, 22610, 31206, 48630, 60922, 83734, 111482, 149750, 196086, 261618, 336850, 514810, 631946, 862130, 1116654, 1502982, 1916530, 2555734, 3242546
EXAMPLE
The a(0) = 1 through a(6) = 22 words:
{} 0 00 000 0000 00000 000000
1 11 001 0001 00001 000001
011 0111 00011 000011
100 1000 00111 000100
110 1110 01111 000110
111 1111 10000 001000
11000 001110
11100 001111
11110 011000
11111 011100
011111
100000
100011
100111
110000
110001
110111
111001
111011
111100
111110
111111
MATHEMATICA
Table[Length[Select[Tuples[{0, 1}, n], UnsameQ@@Length/@Split[#]&]], {n, 0, 10}]
PROG
(Python)
from itertools import groupby, product
def adrl(s):
runlens = [len(list(g)) for k, g in groupby(s)]
return len(runlens) == len(set(runlens))
def a(n):
if n == 0: return 1
return 2*sum(adrl("1"+"".join(w)) for w in product("01", repeat=n-1))
CROSSREFS
Using binary expansions instead of words gives A032020, ranked by A044813. The version for partitions is A098859. The complement is counted by twice A261982. A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329767 counts binary words by runs-resistance.
A351014 counts distinct runs in standard compositions.
A351204 counts partitions where every permutation has all distinct runs.
A351290 ranks compositions with all distinct runs.
Search completed in 0.038 seconds
| 
