Search: a132685 -id:a132685
|
|
A014070
|
|
a(n) = binomial(2^n, n).
|
|
+10
47
|
|
|
1, 2, 6, 56, 1820, 201376, 74974368, 94525795200, 409663695276000, 6208116950265950720, 334265867498622145619456, 64832175068736596027448301568, 45811862025512780638750907861652480, 119028707533461499951701664512286557511680
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
a(n) is the number of n X n (0,1) matrices with distinct rows modulo rows permutations. - Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 13 2003
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x) = Sum_{n>=0} log(1 + 2^n*x)^n / n!. - Paul D. Hanna, Dec 28 2007
a(n) = (1/n!) * Sum_{k=0..n} Stirling1(n, k) * 2^(n*k). - Paul D. Hanna, Feb 05 2023
a(n) ~ 2^(n^2) / n!.
a(n) ~ 2^(n^2 - 1/2) * exp(n) / (sqrt(Pi) * n^(n+1/2)).
(End)
|
|
MAPLE
|
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) a(n)=binomial(2^n, n)
(PARI) /* G.f. A(x) as Sum of Series: */
a(n)=polcoeff(sum(k=0, n, log(1+2^k*x +x*O(x^n))^k/k!), n) \\ Paul D. Hanna, Dec 28 2007
(PARI) {a(n) = (1/n!) * sum(k=0, n, stirling(n, k, 1) * 2^(n*k) )}
(Sage) [binomial(2^n, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), this sequence (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A060690
|
|
a(n) = binomial(2^n + n - 1, n).
|
|
+10
32
|
|
|
1, 2, 10, 120, 3876, 376992, 119877472, 131254487936, 509850594887712, 7145544812472168960, 364974894538906616240640, 68409601066028072105113098240, 47312269462735023248040155132636160, 121317088003402776955124829814219234385920
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Also the number of n X n (0,1) matrices modulo rows permutation (by symmetry this is the same as the number of (0,1) matrices modulo columns permutation), i.e., the number of equivalence classes where two matrices A and B are equivalent if one of them is the result of permuting the rows of the other. The total number of (0,1) matrices is in sequence A002416.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = [x^n] 1/(1-x)^(2^n).
a(n) = (1/n!)*Sum_{k=0..n} ( (-1)^(n-k)*Stirling1(n, k)*2^(k*n) ). - Vladeta Jovovic, May 28 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(2^n+n,k) - Vladeta Jovovic, Jan 21 2008
a(n) = Sum_{k=0..n} Stirling1(n,k)*(2^n+n-1)^k/n!. - Vladeta Jovovic, Jan 21 2008
G.f.: A(x) = Sum_{n>=0} [ -log(1 - 2^n*x)]^n / n!. More generally, Sum_{n>=0} [ -log(1 - q^n*x)]^n/n! = Sum_{n>=0} C(q^n+n-1,n)*x^n ; also Sum_{n>=0} log(1 + q^n*x)^n/n! = Sum_{n>=0} C(q^n,n)*x^n. - Paul D. Hanna, Dec 29 2007
|
|
MAPLE
|
with(combinat): for n from 0 to 20 do printf(`%d, `, binomial(2^n+n-1, n)) od:
|
|
MATHEMATICA
|
Table[Binomial[2^n+n-1, n], {n, 0, 20}] (* Harvey P. Dale, Apr 19 2012 *)
|
|
PROG
|
(PARI) a(n)=binomial(2^n+n-1, n)
(PARI) {a(n)=polcoeff(sum(k=0, n, (-log(1-2^k*x +x*O(x^n)))^k/k!), n)} \\ Paul D. Hanna, Dec 29 2007
(PARI) a(n) = sum(k=0, n, stirling(n, k, 1)*(2^n+n-1)^k/n!); \\ Paul D. Hanna, Nov 20 2014
(Sage) [binomial(2^n +n-1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^n +n-1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021
(Python)
from math import comb
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), this sequence (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 19 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A136556
|
|
a(n) = binomial(2^n - 1, n).
|
|
+10
27
|
|
|
1, 1, 3, 35, 1365, 169911, 67945521, 89356415775, 396861704798625, 6098989894499557055, 331001552386330913728641, 64483955378425999076128999167, 45677647585984911164223317311276545, 118839819203635450208125966070067352769535, 1144686912178270649701033287538093722740144666625
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Number of n x n binary matrices without zero rows and with distinct rows up to permutation of rows, cf. A014070.
Also the number of n-element sets of nonempty subsets of {1..n}, or set-systems with n vertices and n edges (not necessarily covering). The covering case is A054780. For example, the a(3) = 35 set-systems are:
{1}{2}{3} {1}{2}{12} {1}{2}{123} {1}{12}{123} {12}{13}{123}
{1}{2}{13} {1}{3}{123} {1}{13}{123} {12}{23}{123}
{1}{2}{23} {1}{12}{13} {1}{23}{123} {13}{23}{123}
{1}{3}{12} {1}{12}{23} {2}{12}{123}
{1}{3}{13} {1}{13}{23} {2}{13}{123}
{1}{3}{23} {2}{3}{123} {2}{23}{123}
{2}{3}{12} {2}{12}{13} {3}{12}{123}
{2}{3}{13} {2}{12}{23} {3}{13}{123}
{2}{3}{23} {2}{13}{23} {3}{23}{123}
{3}{12}{13} {12}{13}{23}
{3}{12}{23}
{3}{13}{23}
Of these, only {{1},{2},{1,2}}, {{1},{3},{1,3}}, and {{2},{3},{2,3}} do not cover the vertex set.
(End)
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(2^n,k).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k) * (2^n-1)^k.
G.f.: Sum_{n>=0} log(1 + 2^n*x)^n / (n! * (1 + 2^n*x)).
|
|
EXAMPLE
|
G.f.: A(x) = 1 + x + 3*x^2 + 35*x^3 + 1365*x^4 + 169911*x^5 +...
A(x) = 1/(1+x) + log(1+2*x)/(1+2*x) + log(1+4*x)^2/(2!*(1+4*x)) + log(1+8*x)^3/(3!*(1+8*x)) + log(1+16*x)^4/(4!*(1+16*x)) + log(1+32*x)^5/(5!*(1+32*x)) +...
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[Length[Subsets[Rest[Subsets[Range[n]]], {n}]], {n, 0, 4}] (* Gus Wiseman, Dec 19 2023 *)
|
|
PROG
|
(PARI) {a(n) = binomial(2^n-1, n)}
for(n=0, 20, print1(a(n), ", "))
(PARI) /* As coefficient of x^n in the g.f.: */
{a(n) = polcoeff( sum(i=0, n, 1/(1 + 2^i*x +x*O(x^n)) * log(1 + 2^i*x +x*O(x^n))^i/i!), n)}
for(n=0, 20, print1(a(n), ", "))
(Sage) [binomial(2^n -1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^n -1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021
(Python)
from math import comb
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): this sequence (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A136555
|
|
Square array, read by antidiagonals, where T(n,k) = binomial(2^k + n-1, k).
|
|
+10
16
|
|
|
1, 1, 1, 1, 2, 3, 1, 3, 6, 35, 1, 4, 10, 56, 1365, 1, 5, 15, 84, 1820, 169911, 1, 6, 21, 120, 2380, 201376, 67945521, 1, 7, 28, 165, 3060, 237336, 74974368, 89356415775, 1, 8, 36, 220, 3876, 278256, 82598880, 94525795200, 396861704798625, 1, 9, 45, 286, 4845, 324632, 90858768, 99949406400, 409663695276000, 6098989894499557055
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Let vector R_{n} equal row n of this array; then R_{n+1} = P * R_{n} for n>=0, where triangle P = A132625 such that row n+1 of P = row n of P^(2^n) with appended '1' for n>=0.
|
|
LINKS
|
|
|
FORMULA
|
G.f. for row n: Sum_{i>=0} (1 + 2^i*x)^(n-1) * log(1 + 2^i*x)^i / i!.
For the square array:
For the number triangle:
t(n, k) = T(n-k, k) = binomial(2^k + n - k -1, k).
Sum_{k=0..n} t(n,k) = Sum_{k=0..n} T(n-k, k) = A136557(n). (End)
|
|
EXAMPLE
|
Square array begins:
1, 1, 3, 35, 1365, 169911, 67945521, 89356415775, ... A136556;
1, 2, 6, 56, 1820, 201376, 74974368, 94525795200, ... A014070;
1, 3, 10, 84, 2380, 237336, 82598880, 99949406400, ... A136505;
1, 4, 15, 120, 3060, 278256, 90858768, 105637584000, ... A136506;
1, 5, 21, 165, 3876, 324632, 99795696, 111600996000, ... ;
1, 6, 28, 220, 4845, 376992, 109453344, 117850651776, ... ;
1, 7, 36, 286, 5985, 435897, 119877472, 124397910208, ... ;
1, 8, 45, 364, 7315, 501942, 131115985, 131254487936, ... ;
...
Form column vector R_{n} out of row n of this array;
then row n+1 can be generated from row n by:
R_{n+1} = P * R_{n} for n>=0,
where triangular matrix P = A132625 begins:
1;
1, 1;
2, 1, 1;
14, 4, 1, 1;
336, 60, 8, 1, 1;
25836, 2960, 248, 16, 1, 1;
6251504, 454072, 24800, 1008, 32, 1, 1; ...
where row n+1 of P = row n of P^(2^n) with appended '1' for n>=0.
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[Binomial[2^k +n-k-1, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Mar 14 2021 *)
|
|
PROG
|
(PARI) T(n, k)=binomial(2^k+n-1, k)
(PARI) /* Coefficient of x^k in g.f. of row n: */ T(n, k)=polcoeff(sum(i=0, k, (1+2^i*x+x*O(x^k))^(n-1)*log((1+2^i*x)+x*O(x^k))^i/i!), k)
(Sage) flatten([[binomial(2^k +n-k-1, k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^k +n-k-1, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 14 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A136505
|
|
a(n) = binomial(2^n + 1, n).
|
|
+10
14
|
|
|
1, 3, 10, 84, 2380, 237336, 82598880, 99949406400, 422825581068000, 6318976181520699840, 337559127276933693852160, 65182103393445184131620004864, 45946437874792132748338425828443136
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x) = Sum_{n>=0} (1 + 2^n*x) * log(1 + 2^n*x)^n/n!.
|
|
MAPLE
|
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) {a(n)=polcoeff(sum(i=0, n, (1+2^i*x +x*O(x^n))*log(1+2^i*x +x*O(x^n))^i/i!), n)}
(Sage) [binomial(2^n +1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^n +1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), this sequence (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A136506
|
|
a(n) = binomial(2^n + 2, n).
|
|
+10
14
|
|
|
1, 4, 15, 120, 3060, 278256, 90858768, 105637584000, 436355999662176, 6431591598617108352, 340881559632021623909760, 65533747894341651530074060800, 46081376018330435634530315478453248
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x) = Sum_{n>=0} (1 + 2^n*x)^2 * log(1 + 2^n*x)^n/n!.
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[Binomial[2^n+2, n], {n, 0, 20}] (* Harvey P. Dale, Jun 20 2011 *)
|
|
PROG
|
(PARI) {a(n)=polcoeff(sum(i=0, n, (1+2^i*x +x*O(x^n))^2*log(1+2^i*x +x*O(x^n))^i/i!), n)}
(Sage) [binomial(2^n +2, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^n +2, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), A136505 (0,1), this sequence (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A132683
|
|
a(n) = binomial(2^n + n, n).
|
|
+10
13
|
|
|
1, 3, 15, 165, 4845, 435897, 131115985, 138432467745, 525783425977953, 7271150092378906305, 368539102493388126164865, 68777035446753808820521420545, 47450879627176629761462147774626305
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = [x^n] 1/(1-x)^(2^n + 1).
G.f.: Sum_{n>=0} (-log(1 - 2^n*x))^n / ((1 - 2^n*x)*n!). - Paul D. Hanna, Feb 25 2009
|
|
EXAMPLE
|
G.f.: A(x) = 1 + 3*x + 15*x^2 + 165*x^3 + 4845*x^4 + 435897*x^5 + ...
A(x) = 1/(1-x) - log(1-2x)/(1-2x) + log(1-4x)^2/((1-4x)*2!) - log(1-8x)^3/((1-8x)*3!) +- ... (End)
|
|
MAPLE
|
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) a(n)=binomial(2^n+n, n)
(PARI) {a(n)=polcoeff(sum(m=0, n, (-log(1-2^m*x))^m/((1-2^m*x +x*O(x^n))*m!)), n)} \\ Paul D. Hanna, Feb 25 2009
(Sage) [binomial(2^n +n, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^n +n, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), this sequence (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A132684
|
|
a(n) = binomial(2^n + n + 1, n).
|
|
+10
13
|
|
|
1, 4, 21, 220, 5985, 501942, 143218999, 145944307080, 542150225230185, 7398714129087308170, 372134605932348010322571, 69146263065062394421802892300, 47589861944854471977019273909187085
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = [x^n] 1/(1-x)^(2^n + 2).
G.f.: Sum_{n>=0} (-log(1 - 2^n*x))^n / ((1 - 2^n*x)^2*n!). - Paul D. Hanna, Feb 25 2009
|
|
EXAMPLE
|
G.f.: A(x) = 1 + 4*x + 21*x^2 + 220*x^3 + 5985*x^4 + 501942*x^5 +...
A(x) = 1/(1-x)^2 - log(1-2x)/(1-2x)^2 + log(1-4x)^2/((1-4x)^2*2!) - log(1-8x)^3/((1-8x)^2*3!) +- ... (End)
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[Binomial[2^n+n+1, n], {n, 0, 20}] (* Harvey P. Dale, Nov 10 2011 *)
|
|
PROG
|
(PARI) a(n)=binomial(2^n+n+1, n)
(PARI) {a(n)=polcoeff(sum(m=0, n, (-log(1-2^m*x))^m/((1-2^m*x +x*O(x^n))^2*m!)), n)} \\ Paul D. Hanna, Feb 25 2009
(Sage) [binomial(2^n +n+1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021
(Magma) [Binomial(2^n +n+1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), this sequence (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A132686
|
|
a(n) = binomial(2^n + 2*n + 1, n).
|
|
+10
13
|
|
|
1, 5, 36, 455, 12650, 962598, 237093780, 209004408899, 689960224294614, 8639439963148103450, 409865407260324119340236, 73328394245057556170201283726, 49287010273876375495535472789937580
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = [x^n] 1/(1-x)^(2^n + n + 2).
|
|
MATHEMATICA
|
Table[Binomial[2^n +2*n +1, n], {n, 0, 20}] (* G. C. Greubel, Mar 13 2021 *)
|
|
PROG
|
(PARI) a(n)=binomial(2^n+2*n+1, n)
(Sage) [binomial(2^n +2*n +1, n) for n in (0..20)] # G. C. Greubel, Mar 13 2021
(Magma) [Binomial(2^n +2*n +1, n): n in [0..20]]; // G. C. Greubel, Mar 13 2021
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), this sequence (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A132687
|
|
a(n) = binomial(2^n + 3*n - 1, n).
|
|
+10
13
|
|
|
1, 4, 36, 560, 17550, 1370754, 324540216, 267212177232, 822871715492970, 9728874233306696390, 442491588454024774291770, 76919746769405407508866898400, 50743487119356450255156023756871000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = [x^n] 1/(1-x)^(2^n + 2*n).
|
|
MATHEMATICA
|
Table[Binomial[2^n+3n-1, n], {n, 0, 20}] (* Harvey P. Dale, Sep 07 2017 *)
|
|
PROG
|
(PARI) a(n)=binomial(2^n+3*n-1, n)
(Sage) [binomial(2^n +3*n -1, n) for n in (0..20)] # G. C. Greubel, Mar 13 2021
(Magma) [Binomial(2^n +3*n -1, n): n in [0..20]]; // G. C. Greubel, Mar 13 2021
|
|
CROSSREFS
|
Sequences of the form binomial(2^n +p*n +q, n): A136556 (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), this sequence (3,-1), A132688 (3,0), A132689 (3,1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.011 seconds
|