A200785 T(n,k) is the number of arrays of n+2 elements from {0,1,...,k} with no two consecutive ascents.

8, 26, 16, 60, 75, 32, 115, 225, 216, 64, 196, 530, 840, 622, 128, 308, 1071, 2425, 3136, 1791, 256, 456, 1946, 5796, 11100, 11704, 5157, 512, 645, 3270, 12152, 31395, 50775, 43681, 14849, 1024, 880, 5175, 23136, 75992, 169884, 232275, 163020, 42756, 2048

Offset

1,1

Comments

All the conjectured formulas are true, and follow from the Burstein-Mansour paper. - N. J. A. Sloane, May 21 2013

Links

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

A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14. See Th. 3.13.

Formula

T(n-2,k) = \sum_{L=0}^n (-1)^L / L! * \sum_{M=0}^{min(L,[(n-L)/2])} binomial(n-L-M,M) * M! * (k+1)^(n-L-2*M) B_{L,M}(x_1,x_2,...), where B_{L,M}() are Bell polynomials, x_i = binomial(k+1,i+2) * i! * f(i), i=1,2,..., and f(i) has period of length 6: [0,1,1,0,-1,-1] (i.e., f(0)=0, f(1)=1, etc.). This formula implies that for a fixed n, T(n,k) is a polynomial in k, which is easy to compute. - Max Alekseyev, Dec 12 2011

Empirical formulas for columns:

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

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

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

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

k=5: a(n) = 6*a(n-1) -20*a(n-3) +15*a(n-4) -a(n-6)

k=6: a(n) = 7*a(n-1) -35*a(n-3) +35*a(n-4) -7*a(n-6) +a(n-7)

k=7: a(n) = 8*a(n-1) -56*a(n-3) +70*a(n-4) -28*a(n-6) +8*a(n-7)

Empirical recurrence for general column k:

0 = sum{i=0..floor(k/3) (binomial(k+1,3*i+1)*T(n-(3*i+1),k))} - sum{i=0..floor((k+1)/3) (binomial(k+1,3*i)*T(n-3*i,k))}

Formulae for rows:

T(1,k) = (5/6)*k^3 + 3*k^2 + (19/6)*k + 1

T(2,k) = (17/24)*k^4 + (43/12)*k^3 + (151/24)*k^2 + (53/12)*k + 1

T(3,k) = (7/12)*k^5 + (47/12)*k^4 + (39/4)*k^3 + (133/12)*k^2 + (17/3)*k + 1

T(4,k) = (349/720)*k^6 + (321/80)*k^5 + (1883/144)*k^4 + (1013/48)*k^3 + (3139/180)*k^2 + (413/60)*k + 1

T(5,k) = (2017/5040)*k^7 + (1427/360)*k^6 + (5759/360)*k^5 + (607/18)*k^4 + (28459/720)*k^3 + (9113/360)*k^2 + (848/105)*k + 1

T(6,k) = (6679/20160)*k^8 + (4799/1260)*k^7 + (26449/1440)*k^6 + (2162/45)*k^5 + (212153/2880)*k^4 + (6019/90)*k^3 + (174571/5040)*k^2 + (3893/420)*k + 1

T(7,k) = (99377/362880)*k^9 + (48247/13440)*k^8 + (243673/12096)*k^7 + (60529/960)*k^6 + (2076437/17280)*k^5 + (274529/1920)*k^4 + (952027/9072)*k^3 + (152461/3360)*k^2 + (26399/2520)*k + 1

Example

Table starts
....8.....26......60.......115.......196........308.........456.........645
...16.....75.....225.......530......1071.......1946........3270........5175
...32....216.....840......2425......5796......12152.......23136.......40905
...64....622....3136.....11100.....31395......75992......164004......324087
..128...1791...11704.....50775....169884.....474566.....1160616.....2562633
..256...5157...43681....232275....919413....2964416.....8216484....20273247
..512..14849..163020...1062500...4975322...18514405....58154912...160338680
.1024..42756..608400...4860250..26924106..115637431...411637168..1268210421
.2048.123111.2270580..22232375.145698840..722234149..2913595712.10030582998
.4096.354484.8473921.101698250.788446400.4510869636.20622837480.79335475611
Some arrays for n=4, k=3:
..0....1....0....0....1....0....3....3....0....1....3....0....2....2....2....2
..3....0....2....2....0....2....0....0....3....1....0....0....0....3....3....3
..2....3....2....2....2....2....3....3....1....0....1....0....2....1....3....3
..1....0....2....1....0....0....2....2....2....2....1....2....2....0....0....2
..0....3....0....0....1....2....1....2....0....0....3....2....0....3....1....3
..3....3....0....3....0....2....3....2....0....3....0....0....2....2....1....3

Crossrefs

Column 1 is A000079

Column 2 is A076264

Column 3 is A072335

Row 1 is A002413

Cf. A200781.

Sequence in context: A060718 A060743 A029617 * A120743 A345205 A063560

Adjacent sequences: A200782 A200783 A200784 * A200786 A200787 A200788

Keyword

nonn,tabl

Author

R. H. Hardin Nov 22 2011

Status

approved