login
Number of binary words of length n with all distinct run-lengths.
30

%I #14 Feb 12 2022 13:41:22

%S 1,2,2,6,6,10,22,26,38,54,114,130,202,266,386,702,870,1234,1702,2354,

%T 3110,5502,6594,9514,12586,17522,22610,31206,48630,60922,83734,111482,

%U 149750,196086,261618,336850,514810,631946,862130,1116654,1502982,1916530,2555734,3242546

%N Number of binary words of length n with all distinct run-lengths.

%F a(n>0) = 2 * A032020(n).

%e The a(0) = 1 through a(6) = 22 words:

%e {} 0 00 000 0000 00000 000000

%e 1 11 001 0001 00001 000001

%e 011 0111 00011 000011

%e 100 1000 00111 000100

%e 110 1110 01111 000110

%e 111 1111 10000 001000

%e 11000 001110

%e 11100 001111

%e 11110 011000

%e 11111 011100

%e 011111

%e 100000

%e 100011

%e 100111

%e 110000

%e 110001

%e 110111

%e 111001

%e 111011

%e 111100

%e 111110

%e 111111

%t Table[Length[Select[Tuples[{0,1},n],UnsameQ@@Length/@Split[#]&]],{n,0,10}]

%o (Python)

%o from itertools import groupby, product

%o def adrl(s):

%o runlens = [len(list(g)) for k, g in groupby(s)]

%o return len(runlens) == len(set(runlens))

%o def a(n):

%o if n == 0: return 1

%o return 2*sum(adrl("1"+"".join(w)) for w in product("01", repeat=n-1))

%o print([a(n) for n in range(20)]) # _Michael S. Branicky_, Feb 08 2022

%Y Using binary expansions instead of words gives A032020, ranked by A044813.

%Y The version for partitions is A098859.

%Y The complement is counted by twice A261982.

%Y The version for compositions is A329739, for runs A351013.

%Y For runs instead of run-lengths we have A351016, twice A351018.

%Y The version for patterns is A351292, for runs A351200.

%Y A000120 counts binary weight.

%Y A001037 counts binary Lyndon words, necklaces A000031, aperiodic A027375.

%Y A005811 counts runs in binary expansion.

%Y A011782 counts integer compositions.

%Y A242882 counts compositions with distinct multiplicities.

%Y A297770 counts distinct runs in binary expansion.

%Y A325545 counts compositions with distinct differences.

%Y A329767 counts binary words by runs-resistance.

%Y A351014 counts distinct runs in standard compositions.

%Y A351204 counts partitions where every permutation has all distinct runs.

%Y A351290 ranks compositions with all distinct runs.

%Y Cf. A003242, A098504, A106356, A116608, A175413, A233564, A238130 or A238279, A328592, A334028, A350952.

%K nonn

%O 0,2

%A _Gus Wiseman_, Feb 07 2022

%E a(25)-a(32) from _Michael S. Branicky_, Feb 08 2022

%E More terms from _David A. Corneth_, Feb 08 2022 using data from A032020