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
Examples
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
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
Comments