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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A105422 Triangle read by rows: T(n,k) is the number of compositions of n having exactly k parts equal to 1. 8
1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 2, 3, 0, 1, 3, 5, 3, 4, 0, 1, 5, 8, 9, 4, 5, 0, 1, 8, 15, 15, 14, 5, 6, 0, 1, 13, 26, 31, 24, 20, 6, 7, 0, 1, 21, 46, 57, 54, 35, 27, 7, 8, 0, 1, 34, 80, 108, 104, 85, 48, 35, 8, 9, 0, 1, 55, 139, 199, 209, 170, 125, 63, 44, 9, 10, 0, 1, 89, 240, 366, 404, 360 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

T(n,k) is also the number of length n bit strings beginning with 0 having k singletons. Example: T(4,2)=3 because we have 0010, 0100 and 0110. - Emeric Deutsch, Sep 21 2008

The cyclic version of this array is A320341(n,k), which counts the (unmarked) cyclic compositions of n with exactly k parts equal to 1, with a minor exception for k=0. The sequence (A320341(n, k=0) - 1: n >= 1) counts the (unmarked) cyclic compositions of n with no parts equal to 1. - Petros Hadjicostas, Jan 08 2019

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

D. Baccherini, D. Merlini and R. Sprugnoli, Level generating trees and proper Riordan arrays, Applicable Analysis and Discrete Mathematics, 2, 2008, 69-91 (see p. 83). [Emeric Deutsch, Sep 21 2008]

Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.

FORMULA

G.f.: (1-z)/(1 - z - z^2 - tz + tz^2).

T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) - T(n-2,k-1), T(0,0)=1, T(1,0)=0. - Philippe Deléham, Nov 18 2009

If the triangle's columns are transposed into rows, then T(n,k) can be interpreted as the number of compositions of n+k having exactly k 1's. Then g.f.: ((1-x)/(1-x-x^2))^(k-1) and T(n,k) = T(n-2,k) + T(n-1,k) - T(n-1, k-1) + T(n, k-1). Also, Sum_{j=1..n} T(n-j, j) = 2^(n-1), the number of compositions of n. - Gregory L. Simay, Jun 28 2019

EXAMPLE

T(6,2) = 9 because we have (1,1,4), (1,4,1), (4,1,1), (1,1,2,2), (1,2,1,2), (1,2,2,1), (2,1,1,2), (2,1,2,1) and (2,2,1,1).

Triangle begins:

00:    1;

01:    0,   1;

02:    1,   0,   1;

03:    1,   2,   0,   1;

04:    2,   2,   3,   0,   1;

05:    3,   5,   3,   4,   0,   1;

06:    5,   8,   9,   4,   5,   0,   1;

07:    8,  15,  15,  14,   5,   6,   0,   1;

08:   13,  26,  31,  24,  20,   6,   7,   0,  1;

09:   21,  46,  57,  54,  35,  27,   7,   8,  0,  1;

10:   34,  80, 108, 104,  85,  48,  35,   8,  9,  0,  1;

11:   55, 139, 199, 209, 170, 125,  63,  44,  9, 10,  0,  1;

12:   89, 240, 366, 404, 360, 258, 175,  80, 54, 10, 11,  0, 1;

13:  144, 413, 666, 780, 725, 573, 371, 236, 99, 65, 11, 12, 0, 1;

...

MAPLE

G:=(1-z)/(1-z-z^2-t*z+t*z^2): Gser:=simplify(series(G, z=0, 15)): P[0]:=1: for n from 1 to 14 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 13 do seq(coeff(t*P[n], t^k), k=1..n+1) od; # yields sequence in triangular form

# second Maple program:

T:= proc(n) option remember; local j; if n=0 then 1

      else []; for j to n do zip((x, y)-> x+y, %,

      [`if`(j=1, 0, [][]), T(n-j)], 0) od; %[] fi

    end:

seq(T(n), n=0..20);  # Alois P. Heinz, Nov 05 2012

MATHEMATICA

nn = 10; a = x/(1 - x) - x + y x;

CoefficientList[CoefficientList[Series[1/(1 - a), {x, 0, nn}], x], y] // Flatten (* Geoffrey Critzer, Dec 23 2011 *)

CROSSREFS

Column 0 yields A000045 (the Fibonacci numbers). Column 1 yields A006367. Column 2 yields A105423. Row sums yield A011782. Cyclic version is A320341.

Sequence in context: A029275 A058739 A128627 * A166291 A162986 A319203

Adjacent sequences:  A105419 A105420 A105421 * A105423 A105424 A105425

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Apr 07 2005

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 10:00 EDT 2019. Contains 328257 sequences. (Running on oeis4.)