A119462 Triangle read by rows: T(n,k) is the number of circular binary words of length n having k occurrences of 01 (0 <= k <= floor(n/2)).

1, 2, 2, 2, 2, 6, 2, 12, 2, 2, 20, 10, 2, 30, 30, 2, 2, 42, 70, 14, 2, 56, 140, 56, 2, 2, 72, 252, 168, 18, 2, 90, 420, 420, 90, 2, 2, 110, 660, 924, 330, 22, 2, 132, 990, 1848, 990, 132, 2, 2, 156, 1430, 3432, 2574, 572, 26, 2, 182, 2002, 6006, 6006, 2002, 182, 2, 2, 210, 2730

Offset

0,2

Comments

Row n contains 1 + floor(n/2) terms.

Sum of entries in row n is 2^n (A000079).

2*binomial(n-1,2k) is also the number of permutations avoiding both 123 and 132 with k valleys, i.e., positions with w[i]>w[i+1]<w[i+2]. - Lara Pudwell, Dec 19 2018

Links

Muniru A Asiru, Rows n=0..150, flattened

M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, and T. Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv preprint arXiv:1812.07112 [math.CO], 2018.

L. Carlitz and R. Scoville, Zero-one sequences and Fibonacci numbers, Fibonacci Quarterly, 15 (1977), 246-254.

Formula

T(n,k) = 2*binomial(n,2k) for n >= 1; T(0,0) = 1.

T(n,k) = 2*T(n-1,k) - T(n-2,k) + T(n-2,k-1) for n >= 3.

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

T(n,0) = 2 for n >= 1.

T(n,1) = 2*binomial(n,2) = A002378(n-1).

T(n,2) = 2*binomial(n,4) = A034827(n).

T(n,k) = 2*A034839(n-1,k) for n >= 1. [Corrected by Georg Fischer, May 28 2023]

Sum_{k=0..floor(n/2)} k*T(n,k) = A057711(n).

Example

T(3,1) = 6 because we have 001, 010, 011, 100, 101 and 110.
Triangle starts:
  1;
  2;
  2,  2;
  2,  6;
  2, 12,  2;
  2, 20, 10;
  2, 30, 30, 2;
  ...

Maple

T:=proc(n, k) if n=0 and k=0 then 1 else 2*binomial(n, 2*k) fi end: for n from 0 to 15 do seq(T(n, k), k=0..floor(n/2)) od; # yields sequence in triangular form

Prog

(GAP) Concatenation([1], Flat(List([1..15], n->List([0..Int(n/2)], k->2*Binomial(n, 2*k))))); # Muniru A Asiru, Dec 20 2018

Crossrefs

Cf. A000079, A002378, A034827, A034839, A057711.

Sequence in context: A080400 A351031 A328236 * A293221 A334512 A096625

Adjacent sequences: A119459 A119460 A119461 * A119463 A119464 A119465

Keyword

nonn,tabf

Author

Emeric Deutsch, May 21 2006

Status

approved