A103295 Number of complete rulers with length n.

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,4

Comments

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

Links

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.

Formula

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

Example

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

Mathematica

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

Crossrefs

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

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

Sequence in context: A339152 A003611 A192115 * A352134 A304257 A217492

Adjacent sequences: A103292 A103293 A103294 * A103296 A103297 A103298

Keyword

nonn

Author

Peter Luschny, Feb 28 2005

Extensions

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

Status

approved