A336479 For any number n with k binary digits, a(n) is the number of tilings T of a size k staircase polyomino (as described in A335547) such that the sizes of the polyominoes at the base of T correspond to the lengths of runs of consecutive equal digits in the binary representation of n.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 5, 3, 2, 3, 1, 1, 1, 2, 8, 5, 11, 18, 8, 5, 3, 5, 11, 7, 3, 5, 1, 1, 1, 2, 13, 8, 26, 42, 18, 11, 26, 42, 94, 58, 29, 47, 13, 8, 5, 8, 29, 18, 36, 58, 26, 16, 7, 11, 26, 16, 5, 8, 1, 1, 1, 2, 21, 13, 60, 97, 42, 26, 87, 141, 317

Offset

0,6

Comments

a(0) = 1 corresponds to the empty polyomino.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Rémy Sigrist, PARI program for A336479

Index entries for sequences related to binary expansion of n

Formula

A335547(n) = Sum_{k = 2^(n-1)..2^n-1} a(k).

a(A000975(n+1)) = A335547(n).

a(2^k-1) = 1 for any k >= 0.

a(2^k) = 1 for any k >= 0.

a(3*2^k) = A000045(k+1) for any k >= 0.

a(7*2^k) = A123392(k) for any k >= 0.

Example

For n = 13, the binary representation of 13 is "1101", so we count the tilings of a size 4 staircase polyomino whose base has the following shape:
      .....
      .   .
      .   .....
      .       .
      +---+   .....
      |   |       .
      |   +---+---+---+
      | 1   1 | 0 | 1 |
      +-------+---+---+
there are 3 such tilings:
      +---+              +---+              +---+
      |   |              |   |              |   |
      +---+---+          +   +---+          +---+---+
      |   |   |          |       |          |   |   |
      +---+---+---+      +---+---+---+      +---+   +---+
      |   |   |   |      |   |   |   |      |   |       |
      |   +---+---+---+  |   +---+---+---+  |   +---+---+---+
      |       |   |   |  |       |   |   |  |       |   |   |
      +-------+---+---+, +-------+---+---+, +-------+---+---+
so a(13) = 3.

Prog

(PARI) See Links section.

Crossrefs

Cf. A000045, A000975, A101211, A123392, A335547.

Sequence in context: A367955 A273894 A308035 * A221131 A126886 A179272

Adjacent sequences: A336476 A336477 A336478 * A336480 A336481 A336482

Keyword

nonn,base

Author

Rémy Sigrist, Sep 13 2020

Status

approved