login
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.
3
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.
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
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Sep 13 2020
STATUS
approved