A319411 Triangle read by rows: T(n,k) = number of binary vectors of length n with runs-resistance k (1 <= k <= n).
2, 2, 2, 2, 2, 4, 2, 4, 6, 4, 2, 2, 12, 12, 4, 2, 6, 30, 18, 8, 0, 2, 2, 44, 44, 32, 4, 0, 2, 6, 82, 76, 74, 16, 0, 0, 2, 4, 144, 138, 172, 52, 0, 0, 0, 2, 6, 258, 248, 350, 156, 4, 0, 0, 0, 2, 2, 426, 452, 734, 404, 28, 0, 0, 0, 0, 2, 10, 790, 752, 1500, 938, 104, 0, 0, 0, 0, 0
Offset: 1
Examples
Triangle begins: 2, 2, 2, 2, 2, 4, 2, 4, 6, 4, 2, 2, 12, 12, 4, 2, 6, 30, 18, 8, 0, 2, 2, 44, 44, 32, 4, 0, 2, 6, 82, 76, 74, 16, 0, 0, 2, 4, 144, 138, 172, 52, 0, 0, 0, 2, 6, 258, 248, 350, 156, 4, 0, 0, 0, 2, 2, 426, 452, 734, 404, 28, 0, 0, 0, 0, 2, 10, 790, 752, 1500, 938, 104, 0, 0, 0, 0, 0, ... Lenormand gives the first 20 rows. The calculation of row 4 is as follows. We may assume the first bit is a 0, and then double the answers. vector / runs / steps to reach a single number: 0000 / 4 / 1 0001 / 31 -> 11 -> 2 / 3 0010 / 211 -> 12 -> 11 -> 2 / 4 0011 / 22 -> 2 / 2 0100 / 112 -> 21 -> 11 -> 2 / 4 0101 / 1111 -> 4 / 2 0110 / 121 -> 111 -> 3 / 3 0111 / 13 -> 11 -> 2 / 3 and we get 1 (once), 2 (twice), 3 (three times) and 4 (twice). So row 4 is: 2,4,6,4.
Links
- Hiroaki Yamanouchi, Table of n, a(n) for n = 1..1830
- Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.
Crossrefs
Row sums are A000079.
Column k = 3 is 2 * A329745 (because runs-resistance 2 for compositions corresponds to runs-resistance 3 for binary words).
The version for compositions is A329744.
The version for partitions is A329746.
The number of nonzero entries in row n > 0 is A319412(n).
The runs-resistance of the binary expansion of n is A318928.
Programs
-
Mathematica
runsresist[q_]:=If[Length[q]==1,1,Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1]; Table[Length[Select[Tuples[{0,1},n],runsresist[#]==k&]],{n,10},{k,n}] (* Gus Wiseman, Nov 25 2019 *)
Comments