A335259 Triangle read by rows: T(n,k) = k^ceiling(n/k) for 1 <= k <= n.

1, 1, 2, 1, 4, 3, 1, 4, 9, 4, 1, 8, 9, 16, 5, 1, 8, 9, 16, 25, 6, 1, 16, 27, 16, 25, 36, 7, 1, 16, 27, 16, 25, 36, 49, 8, 1, 32, 27, 64, 25, 36, 49, 64, 9, 1, 32, 81, 64, 25, 36, 49, 64, 81, 10, 1, 64, 81, 64, 125, 36, 49, 64, 81, 100, 11, 1, 64, 81, 64, 125, 36, 49, 64, 81, 100, 121, 12

Offset

1,3

Comments

T(n,k) is the number of functions f:[n]->[k] such that f(x)=f(y) whenever i*k-k+1<=x<=y<=i*k where 1<=i<=ceiling(n/k). An example of such a function is f:[8]->[3] defined by f(1)=f(2)=f(3)=2, f(4)=f(5)=f(6)=3, and f(7)=f(8)=2. To count all functions of this type when n=8 and k=3, we note that there are 3 possible values for f(1), f(4), and f(7). Hence T(8,3)=3^3 or, equivalently, 3^ceiling(8/3). A proof of the general result follows the same approach. We also note the following: (i) T(n,1)=1 for all n; (ii) T(n,n)=n for all n; T(n,k)=k^2 when ceiling(n/2)<=k<n.

Links

Table of n, a(n) for n=1..78.

Formula

G.f. for fixed k: k*x^k*(1+k*x+k*x^2+...+k*x^(k-1))/(1-k*x^k).

For n>1, T(n,2) = A016116(n).

For n>2, T(n,3) = A127975(n).

Example

Triangle T(n,k):
  1;
  1,  2;
  1,  4,  3;
  1,  4,  9,  4;
  1,  8,  9, 16,  5;
  1,  8,  9, 16, 25,  6;
  1, 16, 27, 16, 25, 36,  7;
  1, 16, 27, 16, 25, 36, 49,  8;
  1, 32, 27, 64, 25, 36, 49, 64,  9;
  1, 32, 81, 64, 25, 36, 49, 64, 81, 10;
...
T(8,3) counts the 27 functions from [8] to [3] where f(1)=f(2)=f(3), f(4)=f(5)=f(6), and f(7)=f(8). Letting f be defined by its vector of images <f(1), ...,f(8)>, the 27 functions are <1,1,1,1,1,1,1,1>, <1,1,1,1,1,1,2,2>, <1,1,1,1,1,1,3,3>, <1,1,1,2,2,2,1,1>, <1,1,1,2,2,2,2,2>, <1,1,1,2,2,2,3,3>, <1,1,1,3,3,3,1,1>, <1,1,1,3,3,3,2,2>, <1,1,1,3,3,3,3,3>, <2,2,2,1,1,1,1,1>, <2,2,2,1,1,1,2,2>, <2,2,2,1,1,1,3,3>, <2,2,2,2,2,2,1,1>, <2,2,2,2,2,2,2,2>, <2,2,2,2,2,2,3,3>, <2,2,2,3,3,3,1,1>, <2,2,2,3,3,3,2,2>, <2,2,2,3,3,3,3,3>, <3,3,3,1,1,1,1,1>, <3,3,3,1,1,1,2,2>, <3,3,3,1,1,1,3,3>, <3,3,3,2,2,2,1,1>, <3,3,3,2,2,2,2,2>, <3,3,3,2,2,2,3,3>, <3,3,3,3,3,3,1,1>, <3,3,3,3,3,3,2,2>, and <3,3,3,3,3,3,3,3>.

Maple

seq(seq(k^ceil(n/k), k=1..n), n=1..20);

Mathematica

Table[k^Ceiling[n/k], {n, 12}, {k, n}] // Flatten (* Michael De Vlieger, Jun 28 2020 *)

Crossrefs

Cf. A016116, A127975.

Sequence in context: A112157 A265624 A332332 * A378037 A093682 A344767

Adjacent sequences: A335256 A335257 A335258 * A335260 A335261 A335262

Keyword

nonn,tabl,easy

Author

Dennis P. Walsh, May 28 2020

Status

approved