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

%I #26 Jun 16 2016 23:27:45

%S 8,26,16,60,75,32,115,225,216,64,196,530,840,622,128,308,1071,2425,

%T 3136,1791,256,456,1946,5796,11100,11704,5157,512,645,3270,12152,

%U 31395,50775,43681,14849,1024,880,5175,23136,75992,169884,232275,163020,42756,2048

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

%C All the conjectured formulas are true, and follow from the Burstein-Mansour paper. - _N. J. A. Sloane_, May 21 2013

%H R. H. Hardin, <a href="/A200785/b200785.txt">Table of n, a(n) for n = 1..10010</a>

%H A. Burstein and T. Mansour, <a href="http://arXiv.org/abs/math.CO/0112281">Words restricted by 3-letter generalized multipermutation patterns</a>, Annals. Combin., 7 (2003), 1-14. See Th. 3.13.

%F 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

%F Empirical formulas for columns:

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

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

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

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

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

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

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

%F Empirical recurrence for general column k:

%F 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))}

%F Formulae for rows:

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

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

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

%F 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

%F 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

%F 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

%F 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

%e Table starts

%e ....8.....26......60.......115.......196........308.........456.........645

%e ...16.....75.....225.......530......1071.......1946........3270........5175

%e ...32....216.....840......2425......5796......12152.......23136.......40905

%e ...64....622....3136.....11100.....31395......75992......164004......324087

%e ..128...1791...11704.....50775....169884.....474566.....1160616.....2562633

%e ..256...5157...43681....232275....919413....2964416.....8216484....20273247

%e ..512..14849..163020...1062500...4975322...18514405....58154912...160338680

%e .1024..42756..608400...4860250..26924106..115637431...411637168..1268210421

%e .2048.123111.2270580..22232375.145698840..722234149..2913595712.10030582998

%e .4096.354484.8473921.101698250.788446400.4510869636.20622837480.79335475611

%e Some arrays for n=4, k=3:

%e ..0....1....0....0....1....0....3....3....0....1....3....0....2....2....2....2

%e ..3....0....2....2....0....2....0....0....3....1....0....0....0....3....3....3

%e ..2....3....2....2....2....2....3....3....1....0....1....0....2....1....3....3

%e ..1....0....2....1....0....0....2....2....2....2....1....2....2....0....0....2

%e ..0....3....0....0....1....2....1....2....0....0....3....2....0....3....1....3

%e ..3....3....0....3....0....2....3....2....0....3....0....0....2....2....1....3

%Y Column 1 is A000079

%Y Column 2 is A076264

%Y Column 3 is A072335

%Y Row 1 is A002413

%Y Cf. A200781.

%K nonn,tabl

%O 1,1

%A _R. H. Hardin_ Nov 22 2011