A143964 Sequence representing valid nontrivial 1-dimensional Hashi (a.k.a. Bridges or Hashiwokakero) puzzle orientations.

0, 11, 22, 110, 121, 132, 220, 231, 242, 1100, 1210, 1221, 1232, 1320, 1331, 1342, 2200, 2310, 2321, 2332, 2420, 2431, 2442, 11000, 12100, 12210, 12221, 12232, 12320, 12331, 12342, 13200, 13310, 13321, 13332, 13420, 13431, 13442, 22000, 23100, 23210, 23221

Offset

1,2

Comments

From Nathaniel Johnston, Sep 30 2011: (Start)

A k-digit number d_1 d_2 ... d_k is in this sequence if there is a multigraph with k vertices (representing the k digits) with the properties that: (1) there are at most two edges connecting d_i and d_{i+1}, and (2) there are no edges connecting d_i and d_j if i and j are not consecutive integers. In the title, "nontrivial" means that this multigraph must be connected (which eliminates terms like 1111 and 1122).

For k > 1, there are 2^k-2 = A000918(k) terms in this sequence with k digits.

(End)

Links

Nathaniel Johnston, Table of n, a(n) for n = 1..10000

Wikipedia, Hashiwokakero

Maple

lim:=5: L[0]:={0}: for n from 0 to lim do L[n+1]:={0, op(map(`+`, L[n], 11*10^n)), op(map(`+`, L[n], 22*10^n))}: od: `union`(seq(L[k], k=0..lim)); # Nathaniel Johnston, Sep 30 2011

Crossrefs

Cf. A000918.

Sequence in context: A111696 A047902 A081930 * A034708 A091784 A213972

Adjacent sequences: A143961 A143962 A143963 * A143965 A143966 A143967

Keyword

easy,nonn

Author

Edgar Almeida Ribeiro (edgar.a.ribeiro(AT)gmail.com), Sep 06 2008

Status

approved