OFFSET
0,7
COMMENTS
T(n,k) = number of strings s(0),...,s(n) such that s(0)=0, s(n)=n-k and for 1<=i<=n, s(i)=s(i-1)+d, with d in {0,1,2} if i=0, in {0,2} if s(i)=2i, in {0,1,2} if s(i)=2i-1, in {0,1} if 0<=s(i)<=2i-2.
Can be seen as concatenation of triangles A104763 and A105809, with identifying column of Fibonacci numbers, see example. - Reinhard Zumkeller, Aug 15 2013
LINKS
FORMULA
T(n, k) = Sum_{j=0..floor((2*n-k+1)/2)} binomial(n-j, 2*n-k-2*j). - Len Smiley, Oct 21 2001
EXAMPLE
. 0: 1
. 1: 1 1 1
. 2: 1 1 2 2 1
. 3: 1 1 2 3 4 3 1
. 4: 1 1 2 3 5 7 7 4 1
. 5: 1 1 2 3 5 8 12 14 11 5 1
. 6: 1 1 2 3 5 8 13 20 26 25 16 6 1
. 7: 1 1 2 3 5 8 13 21 33 46 51 41 22 7 1
. 8: 1 1 2 3 5 8 13 21 34 54 79 97 92 63 29 8 1
. 9: 1 1 2 3 5 8 13 21 34 55 88 133 176 189 155 92 37 9 1
. 10: 1 1 2 3 5 8 13 21 34 55 89 143 221 309 365 344 247 129 46 10 1
.
. 1: 1
. 2: 1 1
. 3: 1 1 2
. 4: 1 1 2 3
. 5: 1 1 2 3 5 columns = A000045, > 0
. 6: 1 1 2 3 5 8 +---------+
. 7: 1 1 2 3 5 8 13 | A104763 |
. 8: 1 1 2 3 5 8 13 21 +---------+
. 9: 1 1 2 3 5 8 13 21 34
. 10: 1 1 2 3 5 8 13 21 34 55
. 11: 1 1 2 3 5 8 13 21 34 55 89
.
. 0: 1
. 1: 1 1 +---------+
. 2: 2 2 1 | A105809 |
. 3: 3 4 3 1 +---------+
. 4: 5 7 7 4 1
. 5: 8 12 14 11 5 1
. 6: 13 20 26 25 16 6 1
. 7: 21 33 46 51 41 22 7 1
. 8: 34 54 79 97 92 63 29 8 1
. 9: 55 88 133 176 189 155 92 37 9 1
. 10: 89 143 221 309 365 344 247 129 46 10 1
MAPLE
A027926 := proc(n, k)
add(binomial(n-j, 2*n-k-2*j), j=0..(2*n-k+1)/2) ;
end proc: # R. J. Mathar, Apr 11 2016
MATHEMATICA
z = 15; t[n_, 0] := 1; t[n_, k_] := 1 /; k == 2 n; t[n_, 1] := 1;
t[n_, k_] := t[n, k] = t[n - 1, k - 2] + t[n - 1, k - 1];
u = Table[t[n, k], {n, 0, z}, {k, 0, 2 n}];
TableForm[u] (* A027926 array *)
v = Flatten[u] (* A027926 sequence *)
(* Clark Kimberling, Aug 31 2014 *)
Table[Sum[Binomial[n-j, 2*n-k-2*j], {j, 0, Floor[(2*n-k+1)/2]}], {n, 0, 10}, {k, 0, 2*n}]//Flatten (* G. C. Greubel, Sep 05 2019 *)
PROG
(PARI) {T(n, k) = if( k<0 || k>2*n, 0, if( k<=1 || k==2*n, 1, T(n-1, k-2) + T(n-1, k-1)))}; /* _Michael Somos, Feb 26 1999 */
(PARI) {T(n, k) = if( k<0 || k>2*n, 0, sum( j=max(0, k-n), k\2, binomial(k-j, j)))}; /* Michael Somos */
(Haskell)
a027926 n k = a027926_tabf !! n !! k
a027926_row n = a027926_tabf !! n
a027926_tabf = iterate (\xs -> zipWith (+)
([0] ++ xs ++ [0]) ([1, 0] ++ xs)) [1]
-- Variant, cf. example:
a027926_tabf' = zipWith (++) a104763_tabl (map tail a105809_tabl)
-- Reinhard Zumkeller, Aug 15 2013
(Magma) [&+[Binomial(n-j, 2*n-k-2*j): j in [0..Floor((2*n-k+1)/2)]]: k in [0..2*n], n in [0..10]]; // G. C. Greubel, Sep 05 2019
(Sage) [[sum(binomial(n-j, 2*n-k-2*j) for j in (0..floor((2*n-k+1)/2))) for k in (0..2*n)] for n in (0..10)] # G. C. Greubel, Sep 05 2019
(GAP) Flat(List([0..10], n-> List([0..2*n], k-> Sum([0..Int((2*n-k+1)/2) ], j-> Binomial(n-j, 2*n-k-2*j) )))); # G. C. Greubel, Sep 05 2019
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
EXTENSIONS
Incorporates comments from Michael Somos.
Example extended by Reinhard Zumkeller, Aug 15 2013
STATUS
approved