A182319 Triangular array: T(n,k) counts upper triangular matrices with entries from {0,1} having n 1's in total, with k 1's on the main diagonal and at least one nonzero entry in each row.

1, 1, 1, 2, 4, 1, 7, 16, 9, 1, 33, 83, 64, 16, 1, 197, 530, 486, 180, 25, 1, 1419, 4026, 4144, 1930, 410, 36, 1, 11966, 35462, 39746, 21574, 5965, 812, 49, 1, 115575, 355368, 425762, 258426, 85589, 15477, 1456, 64, 1

Offset: 1

Author

Peter Bala, Apr 24 2012

Keywords

• nonn
• tabl

Comments

This triangle is a refinement of A179525.

Examples

			Triangle begins
.n\k.|...1.....2.....3.....4.....5
= = = = = = = = = = = = = = = = = =
..1..|...1
..2..|...1.....1
..3..|...2.....4.....1
..4..|...7....16.....9.....1
..5..|..33....83....64....16.....1
..6..|.197...530...486...180....25.....1
...
T(3,2) = 4: there is one 2x2 matrix and three 3x3 matrices with the specified properties:
........1..0..0.....0..1..0.....0..0..1..
1.1.....0..0..1.....0..1..0.....0..1..0..
0.1.....0..0..1.....0..0..1.....0..0..1..
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275

Crossrefs

A179525.

Programs

PARI

\\ A(n) returns vector of n'th row.
A(n)={ my(rv=if(n==1, [1], vector(n)));
my(M=matrix(2,n,k,s,k==2&&s==1));
\\ M[k,s] is number of configs with s 1's with k+1 on diagonal.
for(r=2, n, M=matrix(r+1,n,k,s, sum(j=0, min(s-1,r-1), binomial(r-1,j) * (if(j>0&&k<=r, M[k,s-j]) + if(j1, M[k-1,s-j-1]))));
  for(i=1, r, rv[i]+=M[i+1,n])); rv }
for(n=1,10,print(A(n))); \\ Andrew Howroyd, Oct 10 2017

Formula

Let F(x,t) = 1 - (1-t)*(1 - (1-x*t) + (1-x*t)*(1-x^2*t) - (1-x*t)*(1-x^2*t)*(1-x^3*t) + ...). Then F(1+x,1+x*t) = 1 + x*t + (t+t^2)*x^2 + (2*t+4*t^2+t^3)*x^3 + (7*t+16*t^2+9*t^3+t^4)*x^4 + ... is conjecturally a generating function for the triangle.

T(n+1,1) = sum {k = 1..n} T(n,k); T(n+1,n) = n^2.

First column A179525. Row sums A179525.

Extensions

Terms a(23) and beyond from Andrew Howroyd, Oct 10 2017