David Pasino - cp's OEIS frontend

A276640 Triangle T(n, k) = the number of point-labeled graphs with n points and k edges, no points isolated, no edges isolated. By rows, 0 <= n, ceiling(2*n/3) <= k <= binomial(n, 2).

1, 3, 1, 16, 15, 6, 1, 125, 222, 205, 120, 45, 10, 1, 90, 1356, 3670, 5700, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 1680, 18942, 69450, 156870, 258160, 331506, 343140, 290745, 202755, 116175, 54257, 20349, 5985, 1330, 210, 21, 1

Offset: 1

David Pasino, Sep 08 2016

In an incidence matrix for a graph of this kind, with n columns and k rows, each row has 2 ones (since it is a graph), the rows are distinct (since it is not a multigraph), no column is all zeros (since there are no isolated points), and the columns are distinct (since there are no isolated edges). The transpose of such a matrix, and only such, is an incidence matrix of a covering of a set of k elements (called points) by n distinct nonempty subsets (called blocks) such that every point belongs to exactly 2 blocks, and every 2 blocks have at most 1 point of intersection (for if 2 points each belong to both of 2 blocks, then those 2 blocks are all the blocks that either of those 2 points belong to, so the columns for those 2 points in the matrix are equal). Referring all these matrices to canonical ordered sets of n and k points, the number of matrices for each covering by blocks of these kinds is the factorial of the number of blocks. (Since the rows are distinct, every permutation of the blocks as row indices gives a different matrix.) Hence the number of these graphs, with k blocks on n points, T(n, k), is related to the number of those covers, A060052, by T(n, k) * k! = A060052(k, n) * n!.

			The triangle T(n, k) begins:
n\k 0 1 2 3  4   5    6    7    8    9   10   11   12  13  14
0   1 0 0 0  0   0    0    0    0    0    0    0    0   0   0
1   0 0 0 0  0   0    0    0    0    0    0    0    0   0   0
2   0 0 0 0  0   0    0    0    0    0    0    0    0   0   0
3   0 0 3 1  0   0    0    0    0    0    0    0    0   0   0
4   0 0 0 16 15  6    1    0    0    0    0    0    0   0   0
5   0 0 0 0  125 222  205  120  45   10   1    0    0   0   0
6   0 0 0 0  90  1356 3670 5700 6165 4945 2997 1365 455 105 15

David Pasino, Table of n, a(n) for n = 1..491

Cf. A059443, A060052.

T(n, k) = Sum{s=0..min(floor(n/2), k)} binomial(n, 2*s) * ((2*s)! / (2^s * s!)) * (-1)^s * A276639(n - 2*s, k - s). (This is the inverse relationship of A276639 in terms of T. A276639(n, k) counts graphs with no isolated points, n points, k edges. The summation range of s, the role of s in the arguments (n - 2s, k - s) of the T or A function being summed, and the coefficient function of s, are the same in the relationship going either way, except that the factor (-1)^s is absent when the function being summed is this T. The coefficient, without the -1, is the number of ways to choose 2s points among the n and group them into s pairs to be s isolated edges. A graph with no isolated points is a graph with some number s of isolated edges and a graph on the complement of the union of those with no isolated edges and no isolated points. That the inverse relationship is almost the same was found empirically for small values of n (leaving k as k), and once found, was readily proved.)

A276639 Triangle T(m, n) = the number of point-labeled graphs with n points and m edges, no points isolated. By rows, n >= 0, ceiling(n/2) <= m <= binomial(n,2).

Original entry on oeis.org

1, 1, 3, 1, 3, 16, 15, 6, 1, 30, 135, 222, 205, 120, 45, 10, 1, 15, 330, 1581, 3760, 5715, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 315, 4410, 23604, 73755, 159390, 259105, 331716, 343161, 290745, 202755, 116175, 54257, 20349, 5985, 1330, 210, 21, 1

Offset: 1

David Pasino, Sep 08 2016

The row sums are A006129, omitting row 1 and A006129(1).

			Triangle T(n, m) begins:
n/m  0  1  2  3   4    5    6    7    8    9   10
0    1  0  0  0   0    0    0    0    0    0   0
1    0  0  0  0   0    0    0    0    0    0   0
2    0  1  0  0   0    0    0    0    0    0   0
3    0  0  3  1   0    0    0    0    0    0   0
4    0  0  3  16  15   6    1    0    0    0   0
5    0  0  0  30  135  222  205  120  45   10  1

David Pasino, Table of n, a(n) for n = 1..512

Another version is A054548.

Table[Sum[Binomial[n, k] (-1)^(n - k) Binomial[Binomial[k, 2], m], {k, 0, n}], {n, 7}, {m, Ceiling[n/2], Binomial[n, 2]}] /. {} -> {1} // Flatten (* Michael De Vlieger, Sep 19 2016 *)

T(n, m) = Sum_{k=0,..n} binomial(n, k) * (-1)^(n-k) * A084546(k, m).

A242997 a(n) is the order of the group of invertible elements in the semigroup M whose elements are the closed binary operations on an n-point set S and whose operation (on operations, in this case) is given by x AB y = (x B y) A (y B x) for operations A and B on S and points x and y in S.

Original entry on oeis.org

1, 4, 288, 1105920, 445906944000, 30851909057249280000, 540013176648715369394995200000, 3299903381977999900396941913809223680000000, 9276369213749813701818662527515163802639831924736000000000

Offset: 1

David Pasino, Aug 17 2014

nonn

a(n) is also the number of permutations of the Cartesian square of an n-element set that commute with the permutation that sends each (x, y) to (y, x).

More generally, for the binary operation on k-ary operations on an n-set given by cyclically permuting k inputs to one operation to obtain k outputs to use as inputs to the other operation (as when k = 3, to illustrate, AB(x, y, z) = A(B(x, y, z), B(y, z, x), B(z, x, y))), the group of invertible operations is isomorphic to the centralizer of the cyclic permutation of coordinates, in the Symmetric Group on the k-th Cartesian power of the n-set, and the order of this group is Product(r divides k) Q(n, r)! r^Q(n, r) where Q(n, r) = (1/r) Sum_{d divides r} Mobius(r/d) n^d.

			When n = 2, the 4 invertible binary operations are the left and right projections and the left and right "conjections", the left conjection being that which sends each (x, y) to "not x", which is unique when n = 2.

M. Hall, The Theory of Groups, MacMillan, 1959, 169-172.
N. Jacobson, Basic Algebra 1, 2nd Edition, W.H. Freeman, 1985, p. 289.

J. D. Reid, On Finite Groups and Finite Fields, The American Mathematical Monthly, Vol. 98, Num. 6, June-July 1991, pp. 549-551.

a(n) = n! * (n*(n-1)/2)! * 2^(n*(n-1)/2);

a(n) = n! * (n*(n-1)/2)! * 2^(n*(n-1)/2).

A158091 The number of ways that a straight line segment of length n, marked into n equal units, can be surrounded in a plane by one layer of regular polygons of unit edge that fit together without any gaps or overlaps, such that every polygon shares either a vertex or an exact unit edge with the segment. ("Line wreaths of length n.") Ways that differ by reflection or rotation are not counted as different.

Original entry on oeis.org

21, 114, 154, 348, 748, 1824, 4402, 11177, 28334, 73281, 189501, 493774, 1286655, 3362376, 8787092, 22988862, 60144668, 157418794

Offset: 0

David Pasino, Mar 12 2009

nonn

If n > 1, the only polygons that can be on the interior of the line are squares or else triangles and hexagons. The only further determining principle on the interior is that no two hexagons can have their bases adjacent on the same side of the line, lest they overlap in area. Such scattering of hexagons leads to Fibonacci numbers in the formula. There are 11 ways to cover the two end units, and depending on the two polygons on an end unit, each end has various ways to be completed to a surrounding of the endpoint.

a(0) = 21, a(1) = 114, and if n >= 2 let F the Fibonacci sequence A000045 and let m = n/2 if n is even, or m = (n+3)/2 if n is odd, then a(n) = 7 + 6*F(n-2) + 27*F(n-1) + 31*F(n) + F(n-2)^2 + 18*F(n-1)^2 + 25*F(n)^2 + 40*F(n)*F(n-1) + 8*F(n-1)*F(n-2) + 8*F(n)*F(n-2) + 2*F(m)*F(m-1) + (3*F(m-1) + 7*F(m) + F(m-1)^2 + 5*F(m)^2)/2.
That's by slight recombination of how the formula reads off from the 11 configurations of the end units. Then by Fibonacci identities the quadratic terms can be converted to linear combinations of Fibonacci numbers with roughly double the index, producing the following formula, with F as before, and D = 1 if n is odd, D = 0 if n is even:
a(0) = 21, a(1) = 114, and if n >= 2 then a(n) = (9/5)*(F(2n+3) + F(2n+5)) + (1/10)*((51 + 6D)*F(n+2) + (56+6D)*F(n+4)) + (1/2)*(F((n+3D)/2) + 3F((n+4+3D)/2)) + 7 - (8/5)*(-1)^n - (2/5)*(-1)^((n-D)/2).

A159294 Number of ways that a 1 X n rectangular tile T, marked into n unit squares, can be surrounded by one layer of copies of itself laid in the plane grid generated by the units of T. Ways that differ by rotation or reflection are not counted as different. The surrounded tile is the exact surrounded region.

Original entry on oeis.org

1, 153, 301, 517, 825, 1234, 1774, 2454, 3310, 4351, 5619, 7123, 8911, 10992, 13420, 16204, 19404, 23029, 27145, 31761, 36949, 42718, 49146, 56242, 64090, 72699, 82159, 92479, 103755, 115996

Offset: 1

David Pasino, Apr 09 2009

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-1,-5,5,1,-3,1).

Cf. A159295 for analogous problem for strip-of-hexagons tile.

I:=[301, 517, 825, 1234, 1774, 2454, 3310]; [1, 153] cat [n le 7 select I[n] else 3*Self(n-1) -Self(n-2) -5*Self(n-3) +5*Self(n-4) + Self(n-5) -3*Self(n-6) +Self(n-7): n in [1..30]]; // G. C. Greubel, Jun 27 2018

Join[{1, 153}, LinearRecurrence[{3, -1, -5, 5, 1, -3, 1}, {301, 517, 825, 1234, 1774, 2454, 3310}, 49]] (* G. C. Greubel, Jun 27 2018 *)

x='x+O('x^30); Vec(-x*(63*x^7-173*x^6+15*x^5 +335*x^4 -228*x^3 - 157*x^2+150*x+1)/((x-1)^5*(x+1)^2)) \\ G. C. Greubel, Jun 27 2018

For n>1, a(n) = (1/16)*(n^4 + 30*n^3 + 246*n^2 + 476*n + 256 + (1 if n odd, 0 if n even)*(6*n + 9)).

G.f.: -x*(63*x^7-173*x^6+15*x^5+335*x^4-228*x^3-157*x^2+150*x+1) / ((x-1)^5*(x+1)^2). - Colin Barker, Nov 26 2012

A159295 Number of ways that a tile in the form of a strip of n congruent regular hexagons stuck together on successive parallel edges can be surrounded by one layer of copies of itself in a plane. Ways that differ by rotation or reflection are not counted as different. The surrounded tile is the exact surrounded region.

Original entry on oeis.org

1, 721, 1842, 4025, 7856, 14124, 23936, 38654, 60090, 90407, 132374, 189223, 264972, 364230, 492596, 656404, 863206, 1121449, 1441050, 1832997, 2310024, 2886128, 3577352, 4401210, 5377586, 6528059, 7876926, 9450419, 11277860

Offset: 1

David Pasino, Apr 09 2009

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (4,-3,-8,14,0,-14,8,3,-4,1).

Cf. A159294 for analogous problem for strip-of-squares tile.

I:=[1842,4025, 7856,14124,23936,38654,60090,90407,132374,189223]; [1,721] cat [n le 10 select I[n] else 4*Self(n-1) -3*Self(n-2) -8*Self(n-3) +14*Self(n-4) -14*Self(n-6) +8*Self(n-7) +3*Self(n-8) -4*Self(n-9) +Self(n-10): n in [1..30]]; // G. C. Greubel, Jun 27 2018

Join[{1,721},LinearRecurrence[{4,-3,-8,14,0,-14,8,3,-4,1},{1842,4025, 7856,14124,23936,38654,60090,90407,132374,189223},30]] (* Harvey P. Dale, Dec 04 2014 *)

x='x+O('x^30); Vec(x*(28*x^11 -285*x^10 +784*x^9 -307*x^8 -1866*x^7 +2566*x^6 +583*x^5 -3036*x^4 +1172*x^3 +1039*x^2 -717*x-1)/( (x-1)^7*(x+1)^3)) \\ G. C. Greubel, Jun 27 2018

a(1) = 1, a(2) = 721, and if n > 2 then a(n) = (1/144)*(n^6 + 30*n^5 + 463*n^4 + 3132*n^3 + 11506*n^2 + 10716*n - 1152 + (n odd)(9*n^2 + 90*n + 261)).

G.f.: x*(28*x^11 -285*x^10 +784*x^9 -307*x^8 -1866*x^7 +2566*x^6 +583*x^5 -3036*x^4 +1172*x^3 +1039*x^2 -717*x-1) / ((x-1)^7*(x+1)^3). - Colin Barker, Nov 26 2012

Typo in formula corrected by David Pasino, Apr 15 2009

A155946 Numbers d for which the volume of the regular d-dimensional simplex of unit edge is rational.

Original entry on oeis.org

0, 1, 7, 8, 17, 24, 31, 48, 49, 71, 80, 97, 120, 127, 161, 168, 199, 224, 241, 287, 288, 337, 360, 391, 440, 449, 511, 528, 577, 624, 647, 721, 728, 799, 840, 881, 960, 967

Offset: 1

David Pasino, Jan 31 2009

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

getrat[n_] := Sqrt[(n+1)/2^n];
nextdim[m_] := (p=m+1;While[!IntegerQ[Numerator[getrat[p]]*Denominator[getrat[p]]], p++]; p);
Table[Nest[nextdim, -1, q], {q, 1, 100}] (* Frank M Jackson, Feb 26 2013 *)

is(n)=if(n%2,my(o=valuation(n++,2)); o%2 && issquare(n>>o,&n) && n%2,issquare(n+1)) \\ Charles R Greathouse IV, Feb 26 2013

list(lim)=my(v=List()); forstep(q=1,sqrtint(1+lim\1), 2, listput(v,q^2-1)); for(q=1, sqrtint(1+lim\2), listput(v,2*q^2-1)); vecsort(Vec(v),,8) \\ Charles R Greathouse IV, Feb 26 2013

The volume of the regular d-dimensional simplex of unit edge is V = sqrt((d+1)/2^d)/d!. V is rational if and only if d is of the form q^2*2^k - 1 where q is odd and k is either odd or 0. The even d of this form are the odd squares minus 1. The odd d are the set generated by the function 4x + 3 from the number form 2*q^2 - 1 with q odd.

A155730 Indices of Bell numbers that are divisible by 5.

Original entry on oeis.org

3, 4, 8, 10, 11, 15, 28, 35, 43, 45, 46, 50, 56, 57, 61, 64, 70, 72, 78, 81, 91, 107, 109, 119, 126, 128, 135, 141, 147, 149, 158, 170, 179, 181, 187, 193, 208, 210, 220, 221, 223, 225, 236, 245, 254, 257, 263, 264, 268, 275, 276, 280, 286, 288, 297, 298, 300

Offset: 1

David Pasino, Jan 25 2009

nonn

First differences of terms of this sequence has a period of 156: a(156*m + n) - a(156*m + n -1) = a(156*s + n)- a(156*s + n - 1) for m and s >= 0. - Enrique Pérez Herrero, Oct 01 2013

Vaclav Kotesovec, Table of n, a(n) for n = 1..9990 (terms 1..1000 from Enrique Pérez Herrero).
J. Levine and R. E. Dalton, Minimum Periods, Modulo p, of First Order Bell Exponential Integrals, Mathematics of Computation, 16 (1962), 416-423.
Samuel S. Wagstaff Jr., Aurifeuillian factorizations and the period of the Bell numbers modulo a prime, Math. Comp. 65 (1996), 383-391.
Eric Weisstein's World of Mathematics, Bell Number

Cf. A000110, A229004, A054767, A016789.

Select[Range[300], Mod[BellB[#], 5] == 0 &] (* T. D. Noe, Oct 01 2013 *)

A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.

Original entry on oeis.org

0, 0, 1, 7, 65, 811, 12762, 244588, 5574956, 148332645, 4538695461, 157768581675, 6167103354744, 268758895112072, 12961171404183498, 687270616305277589, 39843719438374998543, 2512873126513271758171, 171643113190082528007702, 12647168303374365311984284

Offset: 0

David Pasino, Dec 06 2008, Dec 08 2008

nonn

			From _Gus Wiseman_, Dec 09 2018: (Start)
The a(3) = 7 unordered pairs:
  {{1},{2},{3}}| {{1,2,3}}
   {{1},{2,3}} |{{1,2},{3}}
   {{1},{2,3}} |{{1,3},{2}}
   {{1,2},{3}} |{{1,3},{2}}
   {{1},{2,3}} | {{1,2,3}}
   {{1,2},{3}} | {{1,2,3}}
   {{1,3},{2}} | {{1,2,3}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
Frank Ruskey and Jennifer Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.
Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, Counting and computing the Rand and block distances of pairs of set partitions, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236-248. - From _N. J. A. Sloane_, Oct 03 2012

Cf. A000110, A000258, A001247, A008277, A048993, A059849, A060639, A181939, A193297, A318393, A322441, A322442, A320768.

a:= n-> add(binomial(n,k)*binomial(combinat[bell](k),2)*
        add(Stirling2(n-k,j)*(-1)^j, j=0..n-k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 27 2018

Array[Sum[Binomial[#, k] Sum[(-1)^j*StirlingS2[# - k, j], {j, 0, # - k}] Binomial[BellB@ k, 2], {k, 0, #}] &, 20, 0] (* Michael De Vlieger, May 27 2018 *)

a000110(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);
a(n) = sum(k=0, n, binomial(n,k) * sum(j=0, n-k, (-1)^j*stirling(n-k,j, 2) * binomial(a000110(k),2))); \\ Michel Marcus, May 27 2018

a(n) = Sum_{k=0..n} binomial(n,k) * (Sum_{j=0..n-k} (-1)^j*A048993(n-k,j)) * binomial(A000110(k),2).
That is, summed on k from 0 to n, the number of k-element subsets of an n-element set, times the alternating sum of row n-k of Stirling2 numbers starting with +S(n-k, 0), times the number of pairs of partitions of k elements.
Obtained by inverting (binomial(A000110(n), 2)) = (Sum_{k=0..n} binomial(n,k)*A000110(n-k)*a(k)), which in turn is gotten by considering that a pair of conjoint partitions is gotten by choosing a partition of a subset and then choosing a pair of disjoint partitions of the complement.

A154238 Number of orbits of the action g*b = b o (g x g) of the group of permutations g of an n-element set S on the set of closed binary operations b on S.

Original entry on oeis.org

1, 1, 10, 3411, 179228736, 2483590604688125, 14325593551925794051596768, 50976900379139614139041610902600299311, 155682086692129060007763454017522652304844346252853248

Offset: 0

David Pasino, Jan 05 2009, Jan 08 2009, Jan 12 2009

nonn

Here are several different ways of expressing the condition that g*b = b:
b(u, v) = b(gu, gv) for all u, v in S.
The level sets of b are closed under g x g.
The level sets of b are unions of cycles of g x g.
The cycles of g x g are subsets of level sets of b.
b is constant on cycles of g x g.
There is no requirement for g to be an automorphism of b. Given g, the fixed b are determined by simply choosing a value in S for each cycle of g x g. The product b(u, v) is defined to be that constant value for every (u, v) in the cycle.
So the number of degrees of freedom for b is the number of cycles of g x g. How many cycles does g have on S x S? If u is in a c-cycle C and v is in a d-cycle D, then (u, v) is in an lcm(c, d)-cycle and C x D is partitioned into these cycles, so there must be cd/lcm(c, d) of them, which is gcd(c, d).
So letting s_k be the number of k-cycles of g on S for each k from 1 to n, the total number of cycles of g on S x S is the sum on k and j of gcd(k, j) s_k s_j. That's the number of degrees of freedom for b and each degree has valence n, so raise n to that power. Then multiply by the well-known number of permutations of type s, which is n! divided by the factorials of the s_k and by the powers k^s_k. Add this up over all the partitions of n and divide by n!.
Additional comments from Christian G. Bower: This is the number of nonisomorphic n-state relations on a set of n elements. If at the step of raising n to the power, we raised instead some constant m to that power, the formula would give the number of isomorphism classes of m-state relations on an n-element set.

Alois P. Heinz, Table of n, a(n) for n = 0..26

Cf. k-state relations: A000595 for k=2, A004105 for k=3, A001374 for k=4, A053516 for k=5.
Cf. A001329, A091057.
Cf. A000595, A004105, A001374, A053516. - Vladeta Jovovic, Jan 06 2009

a(n) = Sum_{1*s_1 + 2*s_2 + ... = n} (fixA[s_1, s_2,..]/(1^s_1*s_1!*2^s_2*s2!* ...)) where fixA[s_1, s_2, ...] = n^(Sum_{i, j>=1} gcd(i, j)*s_i*s_j).

Edited by Christian G. Bower and N. J. A. Sloane, Jan 08 2009

cp's OEIS Frontend

User: David Pasino

A276640 Triangle T(n, k) = the number of point-labeled graphs with n points and k edges, no points isolated, no edges isolated. By rows, 0 <= n, ceiling(2*n/3) <= k <= binomial(n, 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A276639 Triangle T(m, n) = the number of point-labeled graphs with n points and m edges, no points isolated. By rows, n >= 0, ceiling(n/2) <= m <= binomial(n,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A242997 a(n) is the order of the group of invertible elements in the semigroup M whose elements are the closed binary operations on an n-point set S and whose operation (on operations, in this case) is given by x AB y = (x B y) A (y B x) for operations A and B on S and points x and y in S.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

PARI

Formula

Views

Author

Keywords

Comments

Formula

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A155946 Numbers d for which the volume of the regular d-dimensional simplex of unit edge is rational.

Views

Author

Keywords

Links

Programs

Mathematica

PARI

PARI

Formula

A155730 Indices of Bell numbers that are divisible by 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.

Views