A027926 Triangular array T read by rows: T(n,0) = T(n,2n) = 1 for n >= 0; T(n,1) = 1 for n >= 1; T(n,k) = T(n-1,k-2) + T(n-1,k-1) for k = 2..2n-1, n >= 2.

1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 3, 4, 3, 1, 1, 1, 2, 3, 5, 7, 7, 4, 1, 1, 1, 2, 3, 5, 8, 12, 14, 11, 5, 1, 1, 1, 2, 3, 5, 8, 13, 20, 26, 25, 16, 6, 1, 1, 1, 2, 3, 5, 8, 13, 21, 33, 46, 51, 41, 22, 7, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 54, 79, 97, 92, 63, 29, 8, 1

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• tabf

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

Examples

			.   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
		

Links

• Reinhard Zumkeller, Rows n = 0..100 of table, flattened
• Index entries for triangles and arrays related to Pascal's triangle

Crossrefs

Many columns of T are A000045 (Fibonacci sequence), also in T: A001924, A004006, A000071, A000124, A014162, A014166, A027927-A027933.

Some other Fibonacci-Pascal triangles: A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

Programs

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

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

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 *)

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 */

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

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

Extensions

Incorporates comments from Michael Somos.

Example extended by Reinhard Zumkeller, Aug 15 2013