login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A212855 T(n,k) = number of n X k arrays with rows being permutations of 0..k-1 and no column j greater than column j-1 in all rows. 12
1, 1, 1, 1, 3, 1, 1, 19, 7, 1, 1, 211, 163, 15, 1, 1, 3651, 8983, 1135, 31, 1, 1, 90921, 966751, 271375, 7291, 63, 1, 1, 3081513, 179781181, 158408751, 7225951, 45199, 127, 1, 1, 136407699, 53090086057, 191740223841, 21855093751, 182199871, 275563, 255 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

In other words, there are no "column rises", where a "column rise" means a pair of adjacent columns where each entry in the left column is strictly less than the adjacent entry in the right column.

Table starts

.1..1.....1.........1.............1..................1.......................1

.1..3....19.......211..........3651..............90921.................3081513

.1..7...163......8983........966751..........179781181.............53090086057

.1.15..1135....271375.....158408751.......191740223841.........429966316953825

.1.31..7291...7225951...21855093751....164481310134301.....2675558106868421881

.1.63.45199.182199871.2801736968751.128645361626874561.14895038886845467640193

This is R(n,k,0) in [Abramson-Promislow].

REFERENCES

Abramson, Morton; Promislow, David. Enumeration of arrays by column rises. J. Combinatorial Theory Ser. A 24 (1978), no. 2, 247--250. MR0469773 (57 #9554).

LINKS

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

FORMULA

Empirical for column k:

k=1: a(n) = a(n-1).

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

k=3: a(n) = 10*a(n-1) - 27*a(n-2) + 18*a(n-3).

k=4: a(n) = 47*a(n-1) - 718*a(n-2) + 4416*a(n-3) - 10656*a(n-4) + 6912*a(n-5).

k=5: a(n) = 246*a(n-1) - 20545*a(n-2) + 751800*a(n-3) - 12911500*a(n-4) + 100380000*a(n-5) - 304200000*a(n-6) + 216000000*a(n-7).

From Benoit Jubin, May 29 2012: (Start)

T(n,1) = T(1,n) = 1.

T(n,2) = 2^n - 1 since the only n X 2 matrix with rows permutations of {0,1} which has a column rise is the one where all rows are [0,1].

(k!)^n*(1 - (k-1)/2^n) <= T(n,k) <= (k!)^n (the first inequality is (11) in the Abramson-Promislow reference, the second is trivial). (End)

EXAMPLE

Some solutions for n=3, k=4:

..2..1..3..0....1..3..0..2....3..0..2..1....1..3..0..2....1..3..2..0

..2..0..1..3....1..3..0..2....3..1..2..0....1..0..3..2....1..3..0..2

..2..3..0..1....3..0..2..1....2..3..1..0....2..0..3..1....3..1..0..2

CROSSREFS

Diagonal is A212806.

Row 2 is A000275.

Column 3 is A212850.

Sequence in context: A176293 A176339 A121412 * A016561 A111382 A173884

Adjacent sequences:  A212852 A212853 A212854 * A212856 A212857 A212858

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin May 28 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 28 19:06 EDT 2017. Contains 284246 sequences.