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,4

Comments

This triangle is a refinement of A179525.

Links

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

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.

Example

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

Prog

(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(j<s-1&&k>1, 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

Crossrefs

A179525.

Sequence in context: A367065 A360180 A127554 * A204182 A103324 A221073

Adjacent sequences: A182316 A182317 A182318 * A182320 A182321 A182322

Keyword

nonn,tabl

Author

Peter Bala, Apr 24 2012

Extensions

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

Status

approved