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,1

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)

Links

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

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

Example

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

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

Sequence in context: A269494 A269776 A269619 * A269656 A223949 A224133

Adjacent sequences: A269432 A269433 A269434 * A269436 A269437 A269438

Keyword

nonn,tabl

Author

R. H. Hardin, Feb 26 2016

Status

approved