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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A200785 T(n,k) is the number of arrays of n+2 elements from {0,1,...,k} with no two consecutive ascents. 11
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 (list; table; graph; refs; listen; history; text; internal format)
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 A063560 A265104

Adjacent sequences:  A200782 A200783 A200784 * A200786 A200787 A200788

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin Nov 22 2011

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 22 22:17 EDT 2017. Contains 283901 sequences.