A082111 -id:A082111 - cp's OEIS frontend

A193516 T(n,k) = number of ways to place any number of 4X1 tiles of k distinguishable colors into an nX1 grid.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 5, 4, 1, 1, 1, 5, 7, 7, 5, 1, 1, 1, 6, 9, 10, 9, 7, 1, 1, 1, 7, 11, 13, 13, 15, 10, 1, 1, 1, 8, 13, 16, 17, 25, 25, 14, 1, 1, 1, 9, 15, 19, 21, 37, 46, 39, 19, 1, 1, 1, 10, 17, 22, 25, 51, 73, 76, 57, 26, 1, 1, 1, 11, 19, 25, 29, 67, 106, 125

Offset: 1

R. H. Hardin, with proof and formula from Robert Israel in the Sequence Fans Mailing List, Jul 29 2011

Table starts:
..1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..1...1...1...1....1....1....1....1....1....1....1.....1.....1.....1.....1
..2...3...4...5....6....7....8....9...10...11...12....13....14....15....16
..3...5...7...9...11...13...15...17...19...21...23....25....27....29....31
..4...7..10..13...16...19...22...25...28...31...34....37....40....43....46
..5...9..13..17...21...25...29...33...37...41...45....49....53....57....61
..7..15..25..37...51...67...85..105..127..151..177...205...235...267...301
.10..25..46..73..106..145..190..241..298..361..430...505...586...673...766
.14..39..76.125..186..259..344..441..550..671..804...949..1106..1275..1456
.19..57.115.193..291..409..547..705..883.1081.1299..1537..1795..2073..2371
.26..87.190.341..546..811.1142.1545.2026.2591.3246..3997..4850..5811..6886
.36.137.328.633.1076.1681.2472.3473.4708.6201.7976.10057.12468.15233.18376

			Some solutions for n=9 k=3; colors=1, 2, 3; empty=0
..0....3....0....0....3....3....0....0....0....0....2....2....0....0....1....2
..1....3....0....2....3....3....3....0....0....0....2....2....1....0....1....2
..1....3....0....2....3....3....3....2....0....0....2....2....1....0....1....2
..1....3....3....2....3....3....3....2....1....0....2....2....1....0....1....2
..1....0....3....2....0....3....3....2....1....0....2....0....1....0....0....0
..2....3....3....2....0....3....3....2....1....3....2....2....0....0....0....3
..2....3....3....2....0....3....3....0....1....3....2....2....0....0....0....3
..2....3....0....2....0....3....3....0....0....3....2....2....0....0....0....3
..2....3....0....2....0....0....3....0....0....3....0....2....0....0....0....3

R. H. Hardin, Table of n, a(n) for n = 1..9999

Column 1 is A003269(n+1),
Column 2 is A052942,
Column 3 is A143454(n-3),
Row 8 is A082111,
Row 9 is A100536(n+1),
Row 10 is A051866(n+1).

T:= proc(n, k) option remember;
      `if`(n<0, 0,
      `if`(n<4 or k=0, 1, k*T(n-4, k) +T(n-1, k)))
    end:
seq(seq(T(n, d+1-n), n=1..d), d=1..13); # Alois P. Heinz, Jul 29 2011

T[n_, k_] := T[n, k] = If[n < 0, 0, If[n < 4 || k == 0, 1, k*T[n-4, k]+T[n-1, k]]]; Table[Table[T[n, d+1-n], {n, 1, d}], {d, 1, 13}] // Flatten (* Jean-François Alcover, Mar 04 2014, after Alois P. Heinz *)

With z X 1 tiles of k colors on an n X 1 grid (with n >= z), either there is a tile (of any of the k colors) on the first spot, followed by any configuration on the remaining (n-z) X 1 grid, or the first spot is vacant, followed by any configuration on the remaining (n-1) X 1. So T(n,k) = T(n-1,k) + k*T(n-z,k), with T(n,k) = 1 for n=0,1,...,z-1. The solution is T(n,k) = sum_r r^(-n-1)/(1 + z k r^(z-1)) where the sum is over the roots of the polynomial k x^z + x - 1.
T(n,k) = sum {s=0..[n/4]} (binomial(n-3*s,s)*k^s).
For z X 1 tiles, T(n,k,z) = sum{s=0..[n/z]} (binomial(n-(z-1)*s,s)*k^s). - R. H. Hardin, Jul 31 2011

A214870 Natural numbers placed in table T(n,k) layer by layer. The order of placement: at the beginning filled odd places of layer clockwise, next - even places counterclockwise. T(n,k) read by antidiagonals.

Original entry on oeis.org

1, 2, 3, 5, 4, 7, 10, 9, 8, 13, 17, 16, 6, 14, 21, 26, 25, 11, 12, 22, 31, 37, 36, 18, 15, 20, 32, 43, 50, 49, 27, 24, 23, 30, 44, 57, 65, 64, 38, 35, 19, 33, 42, 58, 73, 82, 81, 51, 48, 28, 29, 45, 56, 74, 91, 101, 100, 66, 63, 39, 34, 41, 59, 72, 92, 111

Offset: 1

Boris Putievskiy, Mar 11 2013

Permutation of the natural numbers.
a(n) is a pairing function: a function that reversibly maps Z^{+} x Z^{+} onto Z^{+}, where Z^{+} is the set of integer positive numbers.
Layer is pair of sides of square from T(1,n) to T(n,n) and from T(n,n) to T(n,1).
Enumeration table T(n,k) layer by layer. The order of the list:
  T(1,1)=1;
  T(1,2), T(2,1), T(2,2);
  . . .
  T(1,n), T(3,n), ... T(n,3), T(n,1); T(n,2), T(n,4), ... T(4,n), T(2,n);
  . . .

			The start of the sequence as table:
   1   2   5  10  17  26 ...
   3   4   9  16  25  36 ...
   7   8   6  11  18  27 ...
  13  14  12  15  24  35 ...
  21  22  20  23  19  28 ...
  31  32  30  33  29  34 ...
  ...
The start of the sequence as triangle array read by rows:
   1;
   2,  3;
   5,  4,  7;
  10,  9,  8, 13;
  17, 16,  6, 14, 21;
  26, 25, 11, 12, 22, 31;
  ...

Boris Putievskiy, Rows n = 1..140 of triangle, flattened
Boris Putievskiy, Transformations [of] Integer Sequences And Pairing Functions arXiv:1212.2732 [math.CO], 2012.
Eric Weisstein's World of Mathematics, Pairing functions
Index entries for sequences that are permutations of the natural numbers

Cf. A060734, A060736, A185725, A213921, A213922; table T(n,k) contains: in rows A002522, A000290, A059100, A005563, A117950, A008865, A087475, A028872, A117951, A028347, A114949, A028875, A117619, A028878, A189833, A028881, A189834, A028884, A114948, A028560, A189836; in columns A002061, A014206, A002378, A027688, A028387, A027689, A028552, A027690, A014209, A027691, A027692, A082111, A027693, A028557, A027694, A108195, A187710, A048058, A048840.

t=int((math.sqrt(8*n-7) - 1)/ 2)
i=n-t*(t+1)/2
j=(t*t+3*t+4)/2-n
if i > j:
   result=i*i-i+(j%2)*(2-(j+1)/2)+((j+1)%2)*(j/2+1)
else:
   result=j*j-2*(i%2)*j + (i%2)*((i+1)/2+1) + ((i+1)%2)*(-i/2+1)

As table
T(n,k) = k*k-2*(n mod 2)*k+(n mod 2)*((n+1)/2+1)+((n+1) mod 2)*(-n/2+1), if n<=k;
T(n,k) = n*n-n+(k mod 2)*(2-(k+1)/2)+((k+1) mod 2)*(k/2+1), if n>k.
As linear sequence
a(n) = j*j-2*(i mod 2)*j+(i mod 2)*((i+1)/2+1)+((i+1) mod 2)*(-i/2+1), if i<=j;
a(n) = i*i-i+(j mod 2)*(2-(j+1)/2)+((j+1) mod 2)*(j/2+1), if i>j; where i=n-t*(t+1)/2, j=(t*t+3*t+4)/2-n, t=floor((-1+sqrt(8*n-7))/2).

cp's OEIS Frontend

A193516 T(n,k) = number of ways to place any number of 4X1 tiles of k distinguishable colors into an nX1 grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula