A000629 -id:A000629 - cp's OEIS frontend

A122835 Number of topologies on n labeled elements in which no element belongs to any pair of noncomparable members of the topology.

1, 1, 4, 19, 112, 811, 7024, 70939, 818752, 10630891, 153371344, 2433948859, 42137351392, 790287522571, 15962014455664, 345424786466779, 7973482022972032, 195556150543703851, 5078301994885267984

Offset: 0

Nathan K. McGregor (mcgregnk(AT)ese.wustl.edu), Sep 15 2006

The number of topologies on n labeled elements is a fundamental sequence (A000798), which many mathematicians believe is impossible to completely determine.
The present sequence is an elegant recursion that enumerates the topologies on n labeled elements that can be "drawn" (as, for example, on page 76 of Munkres) in such a way that the boundaries of the subsets do not "cross" one another. Thus I recommend that topologies be classified as "planar" if their members can be drawn without crossings and "non-planar" otherwise.
This is analogous to the way in which subgroup lattices are called planar or non-planar. Using this terminology, the above sequence gives the number of planar topologies on n labeled elements. If the number of non-planar topologies on n labeled elements (see A122836) could be enumerated, then so could the total number of topologies on n labeled elements.
Another way to state the definition is that any two members of the topology are comparable or disjoint. - Rainer Rosenthal, Jan 02 2011
Conjectural closed form for n>0: 3*2^(k-3)(LerchPhi[1/4, -k, 1/2] + 2 PolyLog[-k, 1/4]) - 1/2. - Vladimir Reshetnikov, Jan 07 2011

J. Munkres, Topology, Prentice Hall, (2000), p. 76.

Cf. A000798, A122836.

a122835:=proc(n) option remember; if n=0 then 1 else 2^(n-1) - 1 + add(a122835(n-k)*binomial(n,k),k=1..n); fi; end;

a[n_]:=a[n]=2^(n-1)-1+Sum[a[n-k]*Binomial[n,k],{k,1,n}]; a[0]=1; Table[a[n],{n,0,25}]
a[ n_] := (3/4) * (PolyLog[ -n, 1/2] + Boole[n==0]) - 1/2 (* Michael Somos, Jan 07 2011 *)

{a(n) = local(A); if( n<1, n==0, A = exp(x + x * O(x^n)) / 2; n! * polcoeff( (3/4) / (1 - A) - A, n))} /* Michael Somos, Jan 07 2011 */

a(n) = 2^(n-1) - 1 + Sum{C(n,k)*a(n-k), k = 1 ... n}
E.g.f.: (3/4) / (1 - exp(x)/2) - exp(x)/2. - Michael Somos, Jan 07 2011
a(n) = (A000629(n) + 0^n) * (3/4) - 1/2. - Michael Somos, Jan 07 2011

A128230 Expansion of exp(x)/(1 - x - x^2/2!), where a(n) = 1 + na(n-1) + C(n,2)a(n-2).

Original entry on oeis.org

1, 2, 6, 25, 137, 936, 7672, 73361, 801705, 9856342, 134640146, 2023140417, 33163934641, 588936102860, 11263023492372, 230783643185881, 5044101110058737, 117136294344278346, 2880200768035996990

Offset: 0

Paul D. Hanna, Feb 20 2007

nonn

			E.g.f.: exp(x)/(1 - x - x^2/2!) = 1 + 2*x + 6*x^2/2! + 25*x^3/3! + 137*x^4/4! + 936*x^5/5! + 7672*x^6/6! +... + a(n)*x^n/n! +...
where a(n) = 1 + n*a(n-1) + n*(n-1)*a(n-2)/2.

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A087214, A000629, A128231, A128232.

CoefficientList[Series[E^x/(1-x-x^2/2), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 20 2012 *)

a(n)=n!*polcoeff(exp(x+x*O(x^n))/(1-x-x^2/2! +x*O(x^n)),n)

a(n) ~ n!*exp(sqrt(3)-1)*((1+sqrt(3))/2)^(n+1)/sqrt(3) . - Vaclav Kotesovec, Oct 20 2012

A162313 Triangular array P(2I - P^2)^-1, where P is Pascal's triangle A007318 and I is the identity matrix.

Original entry on oeis.org

1, 3, 1, 17, 6, 1, 147, 51, 9, 1, 1697, 588, 102, 12, 1, 24483, 8485, 1470, 170, 15, 1, 423857, 146898, 25455, 2940, 255, 18, 1, 8560947, 2966999, 514143, 59395, 5145, 357, 21, 1, 197613377, 68487576, 11867996, 1371048, 118790, 8232, 476, 24, 1

Offset: 0

Peter Bala, Jul 01 2009

Unsigned inverse of A162315.
The row generating polynomials of this triangle may be used to evaluate the weighted sums of powers of odd numbers
(1)... 1^m + 2*3^m + 4*5^m + ... + 2^n*(2*n+1)^m
and also the sums
(2)... 1^m + (1/2)*3^m + (1/4)*5^m + ... + (1/2)^n*(2*n+1)^m.
See the Formula section below.
We make a few remarks about the general array M(a) := a*P*(I-a*P^2)^-1, where a <> 1, and its connection with weighted sums of powers of odd numbers. The present case corresponds to a = 1/2. Compare with the remarks in A162312.
The array M(a) begins
/
| a/(1-a)
| (a^2+a)/(1-a)^2 ................. a/(1-a)
| (a^3+6*a^2+a)/(1-a)^3 ........... 2*(a^2+a)/(1-a)^2 ... a/(1-a)
(a^4+23*a^3+23*a^2+a)/(1-a)^4 ...
| .
\ .
In the first column we recognize the numerator polynomials as the Eulerian polynomials of type B. See A060187.
The e.g.f. for this array is
(3)... a*exp((x+1)*t)/(1-a*exp(2*t)) = a/(1-a) +[(a^2+a)/(1-a)^2 + a/(1-a)*x]*t + [(a^3+6*a^2+a)/(1-a)^3 + 2*(a^2+a)*x/(1-a)^2 + a/(1-a)*x^2]*t^2/2! + ....
The row polynomials P_m(x), which depend on a, satisfy the difference equation
(4)... P_m(x) - a*P_m(x+2) = a*(x+1)^m.
for m >= 1.
The first few values are
P_0(x) = a/(1-a), P_1(x) = a*x/(1-a) + (a^2+a)/(1-a)^2 and
P_2(x) = a*x^2/(1-a) + 2*(a^2+a)*x/(1-a)^2 + (a^3+6*a^2+a)/(1-a)^3.
Using (4) leads to the evaluations of the weighted sums of powers of even and odd positive integers:
(5)... Sum_{k = 1..n} a^k*(2*k)^m = P_m(1) - a^n*P_m(2*n+1)
and
(6)... Sum_{k = 1..n} a^k*(2*k-1)^m = P_m(0) - a^n*P_m(2*n),
with m = 0,1,2,... and a <> 1.
In the remaining case a = 1 the sums are evaluated in terms of the Bernoulli polynomials.

			Triangle begins
  n\k|.......0.......1......2......3......4......5......6
  =======================================================
  0..|.......1
  1..|.......3.......1
  2..|......17.......6......1
  3..|.....147......51......9......1
  4..|....1697.....588....102.....12......1
  5..|...24483....8485...1470....170.....15......1
  6..|..423857..146898..25455...2940....255.....18......1
  ...

A000629, A007318, A060187, A080253 (column 0), A154921, A162312, A162314 (row sums), A162315 (unsigned inverse).

m = 8;
P = Table[Binomial[n, k], {n, 0, m}, {k, 0, m}];
T = P.Inverse[2 IdentityMatrix[m+1] - P.P];
Table[T[[n+1, k+1]], {n, 0, m}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 02 2019 *)

TABLE ENTRIES
(1)... T(n,k) = binomial(n,k)*A080253(n-k).
GENERATING FUNCTION
(2)... exp((x+1)*t)/(2-exp(2*t)) = 1 + (3+x)*t + (17+6*x+x^2)*t^2/2!
+ ....
The e.g.f. can also be written as
(3)... exp(x*t)*G(t), where G(t) = exp(t)/(2-exp(2*t)) is the e.g.f. for A080253.
ROW GENERATING POLYNOMIALS
The row generating polynomials R_n(x) form an Appell sequence. The first few values are R_0(x) = 1, R_1(x) = 3 + x, R_2(x) = 17 + 6*x + x^2 and R_3(x) = 147 + 51*x + 9*x^2 + x^3.
The row polynomials may be recursively computed by means of
(4)... R_n(x) = (x+1)^n + Sum_{k=0..n-1} 2^(n-k)*binomial(n,k)*R_k(x).
An explicit formula is
(5)... R_n(x) = Sum_{j = 0..n} Sum_{k = 0..j} (-1)^(j-k)*binomial(j,k)*(x+2*k+1)^n.
There is also a representation as an infinite series
(6)... R_n(x) = (1/2)*Sum_{k >= 0} (1/2)^k*(x+2*k+1)^n.
SUMS OF POWERS OF INTEGERS
The row polynomials satisfy the difference equation
(7)... 2*R_n(x) - R_n(x+2) = (x+1)^n,
and hence may be used to evaluate the weighted sums of powers of odd integers
(8)... Sum_{k=0..n-1} (1/2)^k*(2*k+1)^m = 2*R_m(0)-1/2^(n-1)*R_m(2*n)
as well as
(9)... Sum_{k=0..n-1} 2^k*(2*k+1)^m = (-1)^m*(2^n*R_m(-2*n)-R_m(0)).
For example, m = 2 gives
(10)... Sum_{k=0..n-1} (1/2)^k*(2*k+1)^2 = 34-2^(1-n)*(4*n^2+12*n+17)
and
(11)... Sum_{k = 0..n-1} 2^k*(2*k+1)^2 = 2^n*(4*n^2 - 12*n + 17)-17.
RELATIONS WITH OTHER SEQUENCES
(12)... Row sums = [1,4,24,208,2400,...] = 2^n*A000629(n) = A162314(n).
(13)... Column 0 = [1,3,17,147,1697,...] = A080253.
The identity
(14)... R_n(2*x-1) = 2^n*P_n(x),
where P_n(x) are the row generating polynomials of A154921, provides a surprising connection between (6) and the result
(15)... Sum_{k = 0..n-1} (1/2)^k*k^m = 2*P_m(0) - (1/2)^(n-1)*P_m(n).

A162314 Row sums of A162313.

Original entry on oeis.org

1, 4, 24, 208, 2400, 34624, 599424, 12107008, 279467520, 7257355264, 209403009024, 6646303019008, 230126121738240, 8632047179874304, 348695526455476224, 15091839203924574208, 696733490476660162560

Offset: 0

Peter Bala, Jul 01 2009

Conjecture: for fixed k = 1,2,..., the sequence obtained by reducing a(n) modulo k is eventually periodic with the exact period dividing phi(k), where phi(k) is the Euler totient function A000010. For example, modulo 24 the sequence becomes [1, 4, 0, 16, 0 16, 0, 16, ...] with an apparent period of 2 beginning at a(2). - Peter Bala, Jul 08 2022

Cf. A000629, A162313.

#A162314
with(combinat):
a:= n -> 2^n*add(k!*Stirling2(n+1,k+1), k = 0..n):
seq(a(n), n = 0..16);

a(n) = 2^n*A000629(n) = 2^n*Sum_{k = 0..n} k!*Stirling2(n+1,k+1).
E.g.f.: exp(2*x)/(2-exp(2*x)) = 1 + 4*x + 24*x^2/2! + 208*x^3/3! + ....
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 8*x*(k+1)/(8*x*(k+1) - 1 + 4*x*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 30 2013
From Peter Bala, Jul 08 2022: (Start)
a(n) = Sum_{k = 0..n} (-2)^(n+k)*k!*Stirling2(n,k).
Conjectural o.g.f. as a continued fraction of Stieltjes type: 1/(1 - 4*x/(1 - 2*x/(1 - 8*x/(1 - 4*x/(1 - ... - 3*n*x/(1 - 2*n*x/(1 - ...))))))). (End)

A201355 Expansion of e.g.f.: 3exp(3x) / (4 - exp(3*x)).

Original entry on oeis.org

1, 4, 20, 132, 1140, 12324, 160020, 2424132, 41967540, 817374564, 17688328020, 421061260932, 10934334077940, 307610736087204, 9319558144624020, 302518807147502532, 10474617188712332340, 385347795973248950244, 15010362565222418008020, 617178205591321673884932

Offset: 0

Paul D. Hanna, Nov 30 2011

			E.g.f.: E(x) = 1 + 4*x + 20*x^2/2! + 132*x^3/3! + 1140*x^4/4! + 12324*x^5/5! + ...
O.g.f.: A(x) = 1 + 4*x + 20*x^2 + 132*x^3 + 1140*x^4 + 12324*x^5 + ...
where A(x) = 1 + 4*x/(1+3*x) + 2!*4^2*x^2/((1+3*x)*(1+6*x)) + 3!*4^3*x^3/((1+3*x)*(1+6*x)*(1+9*x)) + 4!*4^4*x^4/((1+3*x)*(1+6*x)*(1+9*x)*(1+12*x)) + ...

G. C. Greubel, Table of n, a(n) for n = 0..390

Cf. A201354, A000629, A123227.

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!(Laplace( 3*Exp(3*x)/(4-Exp(3*x)) ))); // G. C. Greubel, Jun 09 2022

Table[Sum[(-3)^(n-k)*4^k*StirlingS2[n,k]*k!,{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Jun 13 2013 *)
With[{nn=20},CoefficientList[Series[3 Exp[3x]/(4-Exp[3x]),{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Aug 03 2020 *)

{a(n)=n!*polcoeff(3*exp(3*x+x*O(x^n))/(4 - exp(3*x+x*O(x^n))), n)}

{a(n)=polcoeff(sum(m=0, n, 4^m*m!*x^m/prod(k=1, m, 1+3*k*x+x*O(x^n))), n)}

a(n)=sum(k=0, n, (-3)^(n-k)*4^k*stirling(n,k,2)*k!);

my(x='x+O('x^66)); Vec(serlaplace(3*exp(3*x)/(4-exp(3*x)))) \\ Joerg Arndt, May 06 2013

@CachedFunction
def BB(n, k, x):  # modified cardinal B-splines
    if n == 1: return 0 if (x < 0) or (x >= k) else 1
    return x*BB(n-1, k, x) + (n*k-x)*BB(n-1, k, x-k)
def EulerianPolynomial(n, k, x):
    if n == 0: return 1
    return add(BB(n+1, k, k*m+1)*x^m for m in (0..n))
[4^n*EulerianPolynomial(n,1,1/4) for n in (0..19)]  # Peter Luschny, May 04 2013

O.g.f.: A(x) = Sum_{n>=0} n! * 4^n*x^n / Product_{k=0..n} (1+3*k*x).
O.g.f.: A(x) = 1/(1 - 4*x/(1-x/(1 - 8*x/(1-2*x/(1 - 12*x/(1-3*x/(1 - 16*x/(1-4*x/(1 - 20*x/(1-5*x/(1 - ...))))))))))), a continued fraction.
a(n) = Sum_{k=0..n} (-3)^(n-k) * 4^k * Stirling2(n,k) * k!.
a(n) = Sum_{k=0..n} A123125(n,k)*4^k. - Philippe Deléham, Nov 30 2011
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 8*x*(k+1)/(8*x*(k+1) - 1 + 2*x*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 30 2013
a(n) ~ n! * (3/log(4))^(n+1) . - Vaclav Kotesovec, Jun 13 2013
a(n) = 3^n*log(4)*Integral_{x = 0..oo} (ceiling(x))^n * 4^(-x) dx. - Peter Bala, Feb 06 2015
a(n) = 3^(n+1) * Sum_{k>=1} k^n / 4^k. - Ilya Gutkovskiy, Jun 28 2020

A300696 a(n) is the number of n-place formulas in first-order logic when variables are allowed to coincide.

Original entry on oeis.org

1, 2, 8, 46, 350, 3324, 37874, 503458, 7648564, 130722474, 2482437926, 51856030736, 1181704007894, 29172943488602, 775597634145192, 22093062633006326, 671280598744505190, 21671112459225274300, 740767465663838556074, 26727829360555847269034

Offset: 0

Tilman Piesk, Mar 13 2018

nonn

An example of a 3-place formula in predicate logic is Ex Ay Ez P(x,y,z). The number of different formulas when x, y, z have to be different is A000629(3) = 26. When variables are allowed to coincide that means that there are 20 more formulas like, e.g., Ex Ay P(x,x,y) or Ex P(x,x,x).
a(n) is the number of vertices in a cocoon concertina n-cube and the sum of row n in A300695, which shows the number of vertices in that structure by rank. A000629(n) by comparison is the number of vertices in the convex concertina n-cube.
The differences with A000629, i.e., the numbers of formulas with coinciding variables, are 0, 0, 2, 20, 200, 2242, 28508, 408872, 6556894, 116547952, 2277942800, ...

Tilman Piesk, Table of n, a(n) for n = 0..150
Tilman Piesk, List of all 46 formulas with 3 places
Tilman Piesk, Python code used to generate the sequence

Cf. A000629, A083355, A300695.

a(0) = 1, a(n) = 2 * A083355(n) for n > 0.

A330046 Expansion of e.g.f. exp(x) / (1 - sinh(x)).

Original entry on oeis.org

1, 2, 5, 17, 77, 437, 2975, 23627, 214457, 2189897, 24846395, 310095887, 4221990437, 62273111357, 989164604615, 16834483468547, 305604501324017, 5894522593612817, 120381876933435635, 2595103478745235607, 58887707028270711197, 1403084759749993342277

Offset: 0

Ilya Gutkovskiy, Nov 28 2019

nonn

Binomial transform of A006154.

Cf. A000629, A006154, A009283, A327034, A330047.

nmax = 21; CoefficientList[Series[Exp[x]/(1 - Sinh[x]), {x, 0, nmax}], x] Range[0, nmax]!

a(n) = Sum_{k=0..n} binomial(n,k) * A006154(k).

a(n) ~ n! * (1 + 1/sqrt(2)) / (log(1 + sqrt(2)))^(n+1). - Vaclav Kotesovec, Dec 03 2019

A331978 E.g.f.: -log(2 - cosh(x)) (even powers only).

Original entry on oeis.org

0, 1, 4, 46, 1114, 46246, 2933074, 263817646, 31943268634, 5009616448246, 987840438629794, 239217148602642046, 69790939492563608554, 24143849395162438623046, 9772368696995766705116914, 4575221153658910691872135246, 2453303387149157947685779986874

Offset: 0

Ilya Gutkovskiy, Feb 03 2020

nonn

Cf. A000111, A000182, A000629, A003703, A003704, A003707, A094088, A331611.

ptan := proc(n) option remember;
    if irem(n, 2) = 0 then 0 else
    add(`if`(k=0, 1, binomial(n, k)*ptan(n - k)), k = 0..n-1, 2) fi end:
A331978 := n -> ptan(2*n - 1):
seq(A331978(n), n = 0..16);  # Peter Luschny, Jun 06 2022

nmax = 16; Table[(CoefficientList[Series[-Log[2 - Cosh[x]], {x, 0, 2 nmax}], x] Range[0, 2 nmax]!)[[n]], {n, 1, 2 nmax + 1, 2}]

a(0) = 0; a(n) = A094088(n) - (1/n) * Sum_{k=1..n-1} binomial(2*n,2*k) * A094088(n-k) * k * a(k).

a(n) ~ (2*n)! / (n * log(2 + sqrt(3))^(2*n)). - Vaclav Kotesovec, Feb 07 2020

A336437 a(n) = (n!)^n * [x^n] -log(1 - Sum_{k>=1} x^k / (k!)^n).

Original entry on oeis.org

0, 1, 3, 100, 104585, 5781843126, 25450069471437282, 12456703705462747095073458, 900677059707267544414220026068619393, 12337778954350678368447638232258657486399628887370, 39982077640755835496555968029419604779794754953051698069276656138

Offset: 0

Ilya Gutkovskiy, Jul 21 2020

nonn

Cf. A000629, A102223, A326321, A336427, A336438, A336439, A336440.

Table[(n!)^n SeriesCoefficient[-Log[1 - Sum[x^k/(k!)^n, {k, 1, n}]], {x, 0, n}], {n, 0, 10}]
b[n_, k_] := If[n == 0, 0, 1 + (1/n) Sum[Binomial[n, j]^k j b[j, k], {j, 1, n - 1}]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 10}]

A346390 Expansion of e.g.f. -log( 1 - (exp(x) - 1)^3 / 3! ).

Original entry on oeis.org

1, 6, 25, 100, 511, 3626, 30045, 262800, 2470171, 25889446, 302003065, 3821936300, 51672723831, 745789322466, 11505096936085, 189023074558600, 3288243760145491, 60319276499454686, 1164282909466221105, 23603464830964817700, 501435697062735519151

Offset: 3

Ilya Gutkovskiy, Aug 08 2021

nonn

Cf. A000392, A000629, A003704, A327504, A346894, A346954, A346955.

nmax = 23; CoefficientList[Series[-Log[1 - (Exp[x] - 1)^3/3!], {x, 0, nmax}], x] Range[0, nmax]! // Drop[#, 3] &
a[n_] := a[n] = StirlingS2[n, 3] + (1/n) Sum[Binomial[n, k] StirlingS2[n - k, 3] k a[k], {k, 1, n - 1}]; Table[a[n], {n, 3, 23}]

my(x='x+O('x^25)); Vec(serlaplace(-log(1-(exp(x)-1)^3/3!))) \\ Michel Marcus, Aug 09 2021

a(n) = Stirling2(n,3) + (1/n) * Sum_{k=1..n-1} binomial(n,k) * Stirling2(n-k,3) * k * a(k).
a(n) ~ (n-1)! / (log(6^(1/3)+1))^n. - Vaclav Kotesovec, Aug 09 2021
a(n) = Sum_{k=1..floor(n/3)} (3*k)! * Stirling2(n,3*k)/(k * 6^k). - Seiichi Manyama, Jan 23 2025

cp's OEIS Frontend

A122835 Number of topologies on n labeled elements in which no element belongs to any pair of noncomparable members of the topology.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A128230 Expansion of exp(x)/(1 - x - x^2/2!), where a(n) = 1 + n*a(n-1) + C(n,2)*a(n-2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A162313 Triangular array P*(2*I - P^2)^-1, where P is Pascal's triangle A007318 and I is the identity matrix.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A162314 Row sums of A162313.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

A201355 Expansion of e.g.f.: 3*exp(3*x) / (4 - exp(3*x)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

PARI

Sage

Formula

A300696 a(n) is the number of n-place formulas in first-order logic when variables are allowed to coincide.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A330046 Expansion of e.g.f. exp(x) / (1 - sinh(x)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A331978 E.g.f.: -log(2 - cosh(x)) (even powers only).

Views

Author

Keywords

A128230 Expansion of exp(x)/(1 - x - x^2/2!), where a(n) = 1 + na(n-1) + C(n,2)a(n-2).

A162313 Triangular array P(2I - P^2)^-1, where P is Pascal's triangle A007318 and I is the identity matrix.

A201355 Expansion of e.g.f.: 3exp(3x) / (4 - exp(3*x)).