|
| |
|
|
A138265
|
|
Number of upper triangular zero-one matrices with n ones and no zero rows or columns.
|
|
8
|
|
|
|
1, 1, 1, 2, 5, 16, 61, 271, 1372, 7795, 49093, 339386, 2554596, 20794982, 182010945, 1704439030, 17003262470, 180011279335, 2015683264820, 23801055350435, 295563725628564, 3850618520827590, 52514066450469255, 748191494586458700, 11115833059268126770
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Row sums of A193357.
Apparently (see Brightwell-Keller, Theorem 2) this is also the number of unlabeled interval orders with n points. - N. J. A. Sloane, Dec 04 2011
Number of length-n ascent sequences without flat steps (i.e., no two adjacent digits are equal). An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(k)>=0 and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the number of ascents of its argument. [Joerg Arndt, Nov 05 2012]
|
|
|
REFERENCES
|
Graham Brightwell, Mitchel T. Keller, Asymptotic Enumeration of Labelled Interval Orders, arXiv 1111.6766
Soheir Mohamed Khamis, Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height, Order (journal), published on-line, 2011; DOI: 10.1007/s11083-011-9213-5.
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..185
|
|
|
FORMULA
|
G.f.: sum(n>=0, prod(i=1..n, 1-1/(1+x)^i ) ).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k)*A079144(k). a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n-1,k-1)*A022493(k).
For asymptotic behavior see Brightwell-Keller. - N. J. A. Sloane, Dec 04 2011
|
|
|
EXAMPLE
|
From Joerg Arndt, Nov 05 2012: (Start)
The a(4) = 5 such matrices with 4 ones are (dots for zeros):
1 . . . 1 1 . 1 . 1 1 1 . 1 . .
. 1 . . . . 1 . 1 . . 1 . . 1 1
. . 1 . . . 1 . . 1 . . 1 . . 1
. . . 1
The a(5)=16 ascent sequences without flat steps are (dots for zeros):
[ 1] [ . 1 . 1 . ]
[ 2] [ . 1 . 1 2 ]
[ 3] [ . 1 . 1 3 ]
[ 4] [ . 1 . 2 . ]
[ 5] [ . 1 . 2 1 ]
[ 6] [ . 1 . 2 3 ]
[ 7] [ . 1 2 . 1 ]
[ 8] [ . 1 2 . 2 ]
[ 9] [ . 1 2 . 3 ]
[10] [ . 1 2 1 . ]
[11] [ . 1 2 1 2 ]
[12] [ . 1 2 1 3 ]
[13] [ . 1 2 3 . ]
[14] [ . 1 2 3 1 ]
[15] [ . 1 2 3 2 ]
[16] [ . 1 2 3 4 ]
(End)
|
|
|
MAPLE
|
g:=sum(product(1-1/(1+x)^i, i=1..n), n=0..35): gser:=series(g, x=0, 30): seq(coeff(gser, x, n), n=0..22);
# Emeric Deutsch, Mar 23 2008
b:= proc(n, i, t) option remember; `if`(n<1, 1,
add(b(n-1, j, t+`if`(j>i, 1, 0)), j=0..t+1))
end:
a:= n-> add ((-1)^(n-k)*binomial(n-1, k-1)*b(k-1, 0, 0), k=0..n):
seq (a(n), n=0..30);
# Alois P. Heinz, Nov 09 2012
|
|
|
CROSSREFS
|
Cf. A005321, A104602, A135588.
Sequence in context: A009736 A104858 A178123 * A163747 A000111 A007976
Adjacent sequences: A138262 A138263 A138264 * A138266 A138267 A138268
|
|
|
KEYWORD
|
easy,nonn,changed
|
|
|
AUTHOR
|
Vladeta Jovovic, Mar 10 2008, Mar 11 2008
|
|
|
EXTENSIONS
|
More terms from Emeric Deutsch, Mar 23 2008
|
|
|
STATUS
|
approved
|
| |
|
|
