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

Author

Rémy Sigrist, Sep 13 2020

Keywords

• nonn
• base

Comments

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

Examples

			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.
		

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

Crossrefs

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

Programs

PARI

See Links section.

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.