|
| |
|
|
A138265
|
|
Number of upper triangular zero-one matrices with n ones and no zero rows or columns.
|
|
19
|
|
|
|
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
|
This is also the number of rigid unlabeled interval orders with n points (see Brightwell-Keller, Theorem 2; or Dukes-Kitaev-Remmel-Steingrímsson, Theorem 8). - N. J. A. Sloane, Dec 04 2011 [Corrected by Vít Jelínek, Sep 04 2014.]
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(.) gives the number of ascents of its argument. [Joerg Arndt, Nov 05 2012]
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: Sum_{n>=0} (Product_{i=1..n} 1-1/(1+x)^i).
G.f.: Sum_{n>=0} (1+x)^(n+1)*Product_{i=1..n} (1-(1+x)^i)^2. Proved by Bringmann-Li-Rhoades, and by Andrews-Jelínek. - Vít Jelínek, Sep 04 2014
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).
G.f.: B(x/(1+x)) where B(x) is the g.f. of A022493; g.f.: Q(0,u) where u=x/(1+x), Q(k,u) = 1 + (1 - (1-x)^(2*k+1))/(1 - (1-(1-x)^(2*k+2))/(1 -(1-x)^(2*k+2) + 1/Q(k+1,u) )); (continued fraction). - Sergei N. Gladkovskii, Oct 03 2013
Asymptotics (Brightwell and Keller, 2011): a(n) ~ 12*sqrt(3)/(exp(Pi^2/12)*Pi^(5/2)) * n!*sqrt(n)*(6/Pi^2)^n. - Vaclav Kotesovec, May 03 2014
For each m, a(5m+4) mod 5 = 0. Conjectured by Andrews-Sellers, and proved by Garvan (see Remark 1.4(ii) in Garvan's paper).
For each m, a(5m+1) mod 5 = a(5m+2) mod 5 = 3*a(5m+3) mod 5. Proved by Garvan (see (1.17) in Garvan's paper).
The limit a(n)/A022493(n) is equal to exp(-Pi^2/6). This corresponds to the asymptotic probability that a random unlabeled interval order is rigid (See Brightwell-Keller; or Jelínek, Fact 5.2). (End)
Conjectural g.f.: 1 + Sum_{n >= 0} n/(1+x)^(n+1) * (Product_{i = 1..n} 1 - 1/(1+x)^i). Cf. A194530. - Peter Bala, Aug 21 2023
|
|
|
EXAMPLE
|
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
# second Maple program:
b:= proc(n, i, t) option remember; `if`(n<1, 1, add(
`if`(i=j, 0, b(n-1, j, t+`if`(j>i, 1, 0))), j=0..t+1))
end:
a:= n-> b(n-1, 0$2):
|
|
|
MATHEMATICA
|
max = 25; g = Sum[Product[1 - 1/(1 - x)^i, {i, 1, n}], {n, 0, max}]; gser = Series[g, {x, 0, max}]; a[n_] := SeriesCoefficient[gser, {x, 0, n}]; Table[a[n] // Abs, {n, 0, max-1}] (* Jean-François Alcover, Jan 24 2014, after Emeric Deutsch *)
|
|
|
PROG
|
@CachedFunction
def b(n, i, t):
if n<1: return 1
return sum(b(n-1, j, t+(j>i)) for j in range(t+2))
def a(n):
if n<1: return 1
return sum((-1)^(n-k)*binomial(n-1, k-1)*b(k-1, 0, 0) for k in range(n+1))
[a(n) for n in range(33)]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
