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

Author

Peter Luschny, Feb 28 2005

Keywords

• nonn

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

Examples

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

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.

Crossrefs

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

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

Programs

Mathematica

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

Formula

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

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