A200781 -id:A200781 - cp's OEIS frontend

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

R. H. Hardin Nov 22 2011

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

			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

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.

Column 1 is A000079
Column 2 is A076264
Column 3 is A072335
Row 1 is A002413
Cf. A200781.

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

A225682 Triangle read by rows: T(n,k) (0 <= k <= n) = chi(k)*binomial(n,k), where chi(k) = 1,-1,0 according as k == 0,1,2 mod 3.

Original entry on oeis.org

1, 1, -1, 1, -2, 0, 1, -3, 0, 1, 1, -4, 0, 4, -1, 1, -5, 0, 10, -5, 0, 1, -6, 0, 20, -15, 0, 1, 1, -7, 0, 35, -35, 0, 7, -1, 1, -8, 0, 56, -70, 0, 28, -8, 0, 1, -9, 0, 84, -126, 0, 84, -36, 0, 1, 1, -10, 0, 120, -210, 0, 210, -120, 0, 10, -1, 1, -11, 0, 165, -330, 0, 462, -330, 0, 55, -11, 0, 1, -12, 0, 220, -495, 0, 924, -792, 0, 220, -66, 0, 1

Offset: 0

Murray R. Bremner and N. J. A. Sloane, May 17 2013

Corresponding to row n of this triangle, define a generating function G_n(x) = 1/(Sum_{k=0..n} T(n,k)*x^k).
Then G_n(x) is the g.f. for the number of words of length n over an alphabet of size n which do not contain any strictly decreasing factor (consecutive subword) of length 3.
For example, G_2, G_3, G_4, G_5, G_6 are g.f.'s for A000079, A076264, A072335, A200781, A200782.

			Triangle begins:
[1],
[1, -1],
[1, -2, 0],
[1, -3, 0, 1],
[1, -4, 0, 4, -1],
[1, -5, 0, 10, -5, 0],
[1, -6, 0, 20, -15, 0, 1],
[1, -7, 0, 35, -35, 0, 7, -1],
[1, -8, 0, 56, -70, 0, 28, -8, 0],
...

Cf. A000079, A076264, A072335, A200781, A200782.

f:=proc(n) local k,s;
s:=k->if k mod 3 = 0 then 1 elif k mod 3 = 1 then -1 else 0; fi;
[seq(s(k)*binomial(n,k),k=0..n)];
end;
[seq(f(n),n=0..12)];

chi[k_] := Switch[Mod[k, 3], 0, 1, 1, -1, 2, 0]; t[n_, k_] := chi[k]*Binomial[n, k]; Table[t[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 14 2014 *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula