A269435 T(n,k)=Number of length-n 0..k arrays with no repeated value greater than the previous repeated value.

2, 3, 4, 4, 9, 8, 5, 16, 27, 15, 6, 25, 64, 78, 28, 7, 36, 125, 250, 222, 51, 8, 49, 216, 615, 964, 622, 92, 9, 64, 343, 1281, 2995, 3674, 1722, 164, 10, 81, 512, 2380, 7536, 14455, 13868, 4719, 290, 11, 100, 729, 4068, 16408, 44021, 69235, 51917, 12821, 509, 12, 121

Offset: 1

Author

R. H. Hardin, Feb 26 2016

Keywords

• nonn
• tabl

Comments

Table starts

...2.....3......4.......5........6.........7.........8..........9.........10

...4.....9.....16......25.......36........49........64.........81........100

...8....27.....64.....125......216.......343.......512........729.......1000

..15....78....250.....615.....1281......2380......4068.......6525.......9955

..28...222....964....2995.....7536.....16408.....32152......58149......98740

..51...622...3674...14455....44021....112476....252932.....516189.....976135

..92..1722..13868...69235...255576....767172...1981512....4566213....9621220

.164..4719..51917..329430..1475871...5209554..15465934...40265487...94574110

.290.12821.192980.1558430..8482276..35236110.120310016..354051015..927338710

.509.34575.712868.7334806.48543777.237479970.933059856.3105016479.9072298237

From Robert Israel, May 30 2019: (Start)

For each of the A000110 partitions pi of the set {1,...,n}, let A_pi(n,k) be the number of length-n 0..k arrays v, such that v(i)=v(j) if and only if i and j are in the same part, and with no repeated value greater than the previous repeated value. There are restrictions on the values in the parts: if two parts a and b each have cardinality >= 2 and a_2 < b_2 (where the parts are indexed in increasing order), then v(b_i) < v(a_i). Thus if there are m partitions with cardinality >= 2, the values on those m parts are decreasing (listing these parts in order of their second entries). So for a partition with j parts of which m have cardinality >= 2, we have A_pi(n,k) = (k+1)*k*...*(k+2-j)/m!, which is a polynomial in k of degree j. The partition of largest cardinality is the partition into singletons, which has m=0. The result is that for each n, T(n,k) is a monic polynomial of degree n. To verify the "empirical" formula for a row, only n terms in that row need to be computed. (End)

Examples

			Some solutions for n=6 k=4
..1. .2. .3. .3. .2. .2. .2. .4. .3. .2. .3. .4. .3. .2. .1. .2
..4. .3. .3. .4. .0. .0. .4. .3. .1. .0. .2. .3. .4. .0. .3. .4
..3. .0. .1. .3. .3. .0. .3. .4. .3. .4. .3. .3. .3. .3. .4. .0
..3. .4. .3. .2. .1. .0. .3. .2. .1. .3. .4. .3. .2. .0. .0. .0
..3. .1. .4. .2. .2. .2. .2. .4. .3. .0. .3. .3. .3. .4. .4. .2
..2. .4. .3. .1. .3. .3. .0. .4. .2. .1. .2. .0. .0. .3. .4. .3
		

Links

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

Crossrefs

Column 1 is A029907(n+1).

Column 2 is A268013.

Column 3 is A267975.

Diagonal is A268104.

Row 1 is A000027(n+1).

Row 2 is A000290(n+1).

Row 3 is A000578(n+1).

Formula

Empirical for column k:

k=1: a(n) = 2*a(n-1) +a(n-2) -2*a(n-3) -a(n-4)

k=2: a(n) = 6*a(n-1) -9*a(n-2) -4*a(n-3) +9*a(n-4) +6*a(n-5) +a(n-6)

k=3: [order 8]

k=4: [order 10]

k=5: [order 12]

k=6: [order 14]

k=7: [order 16]

Empirical for row n:

n=1: a(n) = n + 1

n=2: a(n) = n^2 + 2*n + 1

n=3: a(n) = n^3 + 3*n^2 + 3*n + 1

n=4: a(n) = n^4 + 4*n^3 + (11/2)*n^2 + (7/2)*n + 1

n=5: a(n) = n^5 + 5*n^4 + (17/2)*n^3 + 8*n^2 + (9/2)*n + 1

n=6: a(n) = n^6 + 6*n^5 + 12*n^4 + (44/3)*n^3 + (23/2)*n^2 + (29/6)*n + 1

n=7: a(n) = n^7 + 7*n^6 + 16*n^5 + (71/3)*n^4 + (139/6)*n^3 + (43/3)*n^2 + (35/6)*n + 1