Search: a060690 -id:a060690
|
|
A014070
|
|
a(n) = binomial(2^n, n).
|
|
+0
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
|
|
|
|
|
A016121
|
|
Number of sequences (a_1, a_2, ..., a_n) of length n with a_1 = 1 satisfying a_i <= a_{i+1} <= 2*a_i.
|
|
+0
17
|
|
|
1, 2, 5, 17, 86, 698, 9551, 226592, 9471845, 705154187, 94285792211, 22807963405043, 10047909839840456, 8110620438438750647, 12062839548612627177590, 33226539134943667506533207, 170288915434579567358828997806, 1630770670148598007261992936663653
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of n X n binary symmetric matrices with rows, considered as binary numbers, in nondecreasing order. - R. H. Hardin, May 30 2008
Also, number of (n+1) X (n+1) binary symmetric matrices with zero main diagonal and rows, considered as binary numbers, in nondecreasing order. - Max Alekseyev, Feb 06 2022
|
|
LINKS
|
|
|
FORMULA
|
Equals the binomial transform of A008934 (number of tournament sequences): a(n) = Sum_{k=0..n} C(n, k)*A008934(k). - Paul D. Hanna, Sep 18 2005
|
|
MATHEMATICA
|
T[n_, k_] := T[n, k] = If[n < 0 || k > n, 0, If[n == k, 1, If[k == 0, 1, T[n - 1, k] + Sum[T[n - 1, j] T[j, k - 1], {j, 0, n - 1}]]]];
a[n_] := Sum[T[n, k], {k, 0, n}];
|
|
PROG
|
(SageMath)
@CachedFunction
if k<0 or k>n: return 0
elif k==0 or k==n: return 1
else: return T(n-1, k) + sum(T(n-1, j)*T(j, k-1) for j in range(n))
def A016121(n): return sum(T(n, k) for k in range(n+1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A060336
|
|
Number of n X n {-1,0,1} matrices modulo rows permutation (by symmetry this is the same as the number of {-1,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.
|
|
+0
3
|
|
|
3, 45, 3654, 1929501, 7355513529, 212787633478239, 47937678641708357304, 85524882506287709213421693, 1224201212028616655577478516173315, 142132497715474639139076246298436794277130
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
LINKS
|
|
|
FORMULA
|
a(n) = C(3^n + n - 1, n) (where C(n, k) denotes the binomial coefficient).
|
|
MATHEMATICA
|
Table[Binomial[3^n+n-1, n], {n, 10}] (* Harvey P. Dale, Apr 10 2012 *)
|
|
PROG
|
(PARI) { for (n=1, 47, write("b060336.txt", n, " ", binomial(3^n + n - 1, n)); ) } \\ Harry J. Smith, Jul 03 2009
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 25 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A086675
|
|
Number of n X n (0,1)-matrices modulo cyclic permutations of the rows.
|
|
+0
8
|
|
|
1, 2, 10, 176, 16456, 6710912, 11453291200, 80421421917440, 2305843009750581376, 268650182136584290872320, 126765060022823052739661424640, 241677817415439249618874010960064512, 1858395433210885261795036719974526548094976
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Also the number of digraphical necklaces with n vertices. A digraphical necklace is defined to be a directed graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of directed graphs under rotation of the vertices. These are a kind of partially labeled digraphs. - Gus Wiseman, Mar 04 2019
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n^2/d) for n > 0, a(0) = 1.
|
|
EXAMPLE
|
Inequivalent representatives of the a(2) = 10 digraphical necklace edge-sets:
{}
{(1,1)}
{(1,2)}
{(1,1),(1,2)}
{(1,1),(2,1)}
{(1,1),(2,2)}
{(1,2),(2,1)}
{(1,1),(1,2),(2,1)}
{(1,1),(1,2),(2,2)}
{(1,1),(1,2),(2,1),(2,2)}
(End)
|
|
MATHEMATICA
|
Table[Fold[ #1+EulerPhi[ #2] 2^(n^2 /#2)&, 0, Divisors[n]]/n, {n, 16}]
(* second program *)
rotdigra[g_, m_]:=Sort[g/.k_Integer:>If[k==m, 1, k+1]];
Table[Length[Select[Subsets[Tuples[Range[n], 2]], #=={}||#==First[Sort[Table[Nest[rotdigra[#, n]&, #, j], {j, n}]]]&]], {n, 0, 4}] (* Gus Wiseman, Mar 04 2019 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 27 2003
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A089006
|
|
Number of distinct n X n (0,1) matrices after double sorting: by row, by column, by row .. until reaching a fixed point.
|
|
+0
6
|
|
|
1, 2, 7, 45, 650, 24520, 2625117, 836488618, 818230288201, 2513135860300849, 24686082394548211147, 787959836124458000837941, 82905574521614049485027140026
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Also, number of n X n binary matrices with both rows and columns, considered as binary numbers, in nondecreasing order. (Ordering only rows gives A060690.) - R. H. Hardin, May 08 2008
A result of Adolf Mader and Otto Mutzbauer shows that the two definitions are equivalent. - Victor S. Miller, Feb 03 2009
For n=5, only 0.07% remain distinct. Sorting columns and\or rows does not change the permanent of the matrix and leaves the absolute value of the determinant unchanged.
|
|
REFERENCES
|
Adolf Mader and Otto Mutzbauer, "Double Orderings of (0,1) Matrices", Ars Combinatoria v. 61 (2001) pp 81-95.
|
|
LINKS
|
|
|
EXAMPLE
|
The 7 (2 X 2)-matrices are {{0,0},{0,0}}, {{0,0},{0,1}}, {{0,0},{1,1}}, {{0,1},{0,1}}, {{0,1},{1,0}}, {{0,1},{1,1}} and {{1,1},{1,1}}.
|
|
MATHEMATICA
|
baseform[li_List] := FixedPoint[Sort[Transpose[Sort[Transpose[Sort[ #1]]]]]&, li]; Table[Length@Split[Sort[baseform/@(Partition[ #, n]&/@(IntegerDigits[Range[0, -1+2^n^2], 2, n^2]))]], {n, 4}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(6)-a(12) found by R. H. Hardin, May 08 2008. These terms were found using bdd's (binary decision diagrams), just setting up the logical relations between bits in a gigantic bdd expression and using that to count the satisfying states.
|
|
STATUS
|
approved
|
|
|
|
|
A092056
|
|
Square table by antidiagonals where T(n,k) = binomial(n+2^k-1,n).
|
|
+0
4
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 10, 4, 1, 1, 16, 36, 20, 5, 1, 1, 32, 136, 120, 35, 6, 1, 1, 64, 528, 816, 330, 56, 7, 1, 1, 128, 2080, 5984, 3876, 792, 84, 8, 1, 1, 256, 8256, 45760, 52360, 15504, 1716, 120, 9, 1, 1, 512, 32896, 357760, 766480, 376992, 54264, 3432, 165, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Each column is convolution of preceding column starting from the all 1's sequence.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = Sum_{i=0..n} T(i,k-1)*T(n-i,k-1) starting with T(n,0) = 1 for n>=0.
|
|
EXAMPLE
|
Rows start:
1, 1, 1, 1, 1, 1, 1,...
1, 2, 4, 8, 16, 32, 64,...
1, 3, 10, 36, 136, 528, 2080,...
1, 4, 20, 120, 816, 5984, 45760,...
1, 5, 35, 330, 3876, 52360, 766480,...
...
|
|
CROSSREFS
|
Cf. A137153 (same with reflected antidiagonals).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A093048
|
|
a(n) = n minus exponent of 2 in n, with a(0) = 0.
|
|
+0
4
|
|
|
0, 1, 1, 3, 2, 5, 5, 7, 5, 9, 9, 11, 10, 13, 13, 15, 12, 17, 17, 19, 18, 21, 21, 23, 21, 25, 25, 27, 26, 29, 29, 31, 27, 33, 33, 35, 34, 37, 37, 39, 37, 41, 41, 43, 42, 45, 45, 47, 44, 49, 49, 51, 50, 53, 53, 55, 53, 57, 57, 59, 58, 61, 61, 63, 58, 65, 65, 67, 66, 69
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
LINKS
|
|
|
FORMULA
|
Recurrence: a(2n) = a(n) + n - 1, a(2n+1) = 2n + 1.
G.f.: Sum_{k>=0} (t*(t^3 + t^2 + 1)/(1 - t^2)^2), with t = x^2^k.
|
|
EXAMPLE
|
G.f. = x + x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 5*x^6 + 7*x^7 + 5*x^8 + 9*x^9 + ... - Michael Somos, Jan 25 2020
|
|
MAPLE
|
|
|
MATHEMATICA
|
a[ n_] := If[ n == 0, n - IntegerExponent[n, 2]]; (* Michael Somos, Jan 25 2020 *)
|
|
PROG
|
(PARI) a(n) = if(n<1, 0, if(n%2==0, a(n/2) + n/2 - 1, n))
(PARI) a(n) = n - valuation(n, 2) \\ Jianing Song, Oct 24 2018
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A094223
|
|
Number of binary n X n matrices with all rows (columns) distinct, up to permutation of columns (rows).
|
|
+0
13
|
|
|
1, 2, 7, 68, 2251, 247016, 89254228, 108168781424, 451141297789858, 6625037125817801312, 348562672319990399962384, 66545827618461283102105245248, 46543235997095840080425299916917968, 120155975713532210671953821005746669185792, 1152009540439950050422144845158703009569109376384
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling1(n, k)*binomial(2^k, n).
a(n) = Sum_{k=0..n} Stirling1(n, k)*binomial(2^k+n-1, n).
|
|
MATHEMATICA
|
a[n_] := Sum[(-1)^(n - k)*StirlingS1[n, k]*Binomial[2^k, n], {k, 0, n}]; (* or *) a[n_] := Sum[ StirlingS1[n, k]*Binomial[2^k + n - 1, n], {k, 0, n}]; Table[ a[n], {n, 0, 12}] (* Robert G. Wilson v, May 29 2004 *)
|
|
PROG
|
(PARI) a(n) = sum(k=0, n, stirling(n, k, 1)*binomial(2^k+n-1, n)); \\ Michel Marcus, Dec 17 2022
|
|
CROSSREFS
|
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A132683
|
|
a(n) = binomial(2^n + n, n).
|
|
+0
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).
|
|
+0
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
|
|
|
Search completed in 0.015 seconds
|