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, 10010, 12870, 6006, 910, 30

Offset: 0

Author

Emeric Deutsch, May 21 2006

Keywords

• nonn
• tabf

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]Lara Pudwell, Dec 19 2018

Examples

			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;
  ...
		

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.

Crossrefs

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

Programs

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

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

Mathematica

T[0,0]:=1; T[n_,k_]:= 2*Binomial[n,2k]; Table[T[n,k],{n,0,15},{k,0,Floor[n/2]}]//Flatten (* Stefano Spezia, Apr 19 2025 *)

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