A120933 Triangle read by rows: T(n,k) is the number of binary words of length n for which the length of the maximal leading nondecreasing subword is k (1<=k<=n).

2, 1, 3, 2, 2, 4, 4, 4, 3, 5, 8, 8, 6, 4, 6, 16, 16, 12, 8, 5, 7, 32, 32, 24, 16, 10, 6, 8, 64, 64, 48, 32, 20, 12, 7, 9, 128, 128, 96, 64, 40, 24, 14, 8, 10, 256, 256, 192, 128, 80, 48, 28, 16, 9, 11, 512, 512, 384, 256, 160, 96, 56, 32, 18, 10, 12, 1024, 1024, 768, 512, 320

Offset: 1

Author

Emeric Deutsch, Jul 16 2006

Keywords

• nonn
• tabl

Examples

			T(4,2)=4 because we have 0100,0101,1100 and 1101.
Triangle starts:
2;
1,3;
2,2,4;
4,4,3,5;
8,8,6,4,6;
		

Links

• Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.

Crossrefs

Cf. A000079, A095151.

Programs

Maple

T:=proc(n,k) if k
				

Formula

T(n,k) = k*2^(n-k-1) if k

G.f.: G(t,z) = (1-2z+tz^2)/[(1-2z)(1-tz)^2] - 1.

Row sums are the powers of 2 (A000079).

Sum_{k=1..n} k*T(n,k) = 3*2^n-n-3 = A095151(n).

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.