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

Author

Dennis P. Walsh, May 28 2020

Keywords

• nonn
• tabl
• easy

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

Examples

			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>.
		

Crossrefs

Cf. A016116, A127975.

Programs

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 *)

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).

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.