A243815 Number of length n words on alphabet {0,1} such that the length of every maximal block of 0's (runs) is the same.

1, 2, 4, 8, 14, 24, 39, 62, 97, 151, 233, 360, 557, 864, 1344, 2099, 3290, 5176, 8169, 12931, 20524, 32654, 52060, 83149, 133012, 213069, 341718, 548614, 881572, 1417722, 2281517, 3673830, 5918958, 9540577, 15384490, 24817031, 40045768, 64637963, 104358789

Offset: 0

Author

Geoffrey Critzer, Jun 11 2014

Keywords

• nonn

Comments

Number of terms of A164710 with exactly n+1 binary digits. - Robert Israel, Nov 09 2015

From Gus Wiseman, Jun 23 2025: (Start)

This is the number of subsets of {1..n} with all equal lengths of runs of consecutive elements increasing by 1. For example, the runs of S = {1,2,5,6,8,9} are ((1,2),(5,6),(8,9)), with lengths (2,2,2), so S is counted under a(9). The a(0) = 1 through a(4) = 14 subsets are:

{} {} {} {} {}

{1} {1} {1} {1}

{2} {2} {2}

{1,2} {3} {3}

{1,2} {4}

{1,3} {1,2}

{2,3} {1,3}

{1,2,3} {1,4}

{2,3}

{2,4}

{3,4}

{1,2,3}

{2,3,4}

{1,2,3,4}

(End)

Examples

			0110 is a "good" word because the length of both its runs of 0's is 1.
Words of the form 11...1 are good words because the condition is vacuously satisfied.
a(5) = 24 because there are 32 length 5 binary words but we do not count: 00010, 00101, 00110, 01000, 01001, 01100, 10010, 10100.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A164710.

These subsets are ranked by A164707, complement A164708.

For distinct instead of equal lengths we have A384175, complement A384176.

For anti-runs instead of runs we have A384889, for partitions A384888.

For permutations instead of subsets we have A384892, distinct instead of equal A384891.

For partitions instead of subsets we have A384904, strict A384886.

The complement is counted by A385214.

A034839 counts subsets by number of maximal runs, for strict partitions A116674.

A049988 counts partitions with equal run-lengths, distinct A325325.

A329738 counts compositions with equal run-lengths, distinct A329739.

A384887 counts partitions with equal lengths of gapless runs, distinct A384884.

Cf. A010027, A044813, A069010, A268193, A383013, A384177, A384893.

Programs

Maple

a:= n-> 1 + add(add((d-> binomial(d+j, d))(n-(i*j-1))
          , j=1..iquo(n+1, i)), i=2..n+1):
seq(a(n), n=0..50);  # Alois P. Heinz, Jun 11 2014

Mathematica

nn=30;Prepend[Map[Total,Transpose[Table[Drop[CoefficientList[Series[ (1+x^k)/(1-x-x^(k+1))-1/(1-x),{x,0,nn}],x],1],{k,1,nn}]]],0]+1
Table[Length[Select[Subsets[Range[n]],SameQ@@Length/@Split[#,#2==#1+1&]&]],{n,0,10}] (* Gus Wiseman, Jun 23 2025 *)