Displaying 1-10 of 17 results found.
2, 3, 6, 13, 29, 71, 173, 444, 1148, 3030, 8059, 21715, 58836, 160687, 441083, 1217134, 3372386, 9380948, 26180962, 73292358, 205731862, 578922864, 1632707684, 4614098810, 13064064882, 37052720050, 105257568244, 299452309023, 853094139960, 2433439189419
1, 3, 7, 16, 36, 87, 212, 541, 1403, 3714, 9931, 26880, 73230, 200944, 554216, 1535969, 4273508, 11933297, 33425583, 93891713, 264401743, 746269426, 2110694255, 5981068081, 16977958318, 48271041858
COMMENTS
Partial sums of number of connected functions (or mapping patterns) on n unlabeled points, or number of rings and branches with n edges. The subsequence of primes in this partial sum begins: 3, 7, 9931, 1535969, 5981068081.
EXAMPLE
a(26) = 1 + 2 + 4 + 9 + 20 + 51 + 125 + 329 + 862 + 2311 + 6217 + 16949 + 46350 + 127714 + 353272 + 981753 + 2737539 + 7659789 + 21492286 + 60466130 + 170510030 + 481867683 + 1364424829 + 3870373826 + 10996890237 + 31293083540.
Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled endofunctions.
(Formerly M2671 N1069)
+10
39
1, 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491, 57903, 163898, 466199, 1328993, 3799624, 10884049, 31241170, 89814958, 258604642, 745568756, 2152118306, 6218869389, 17988233052, 52078309200, 150899223268, 437571896993, 1269755237948, 3687025544605, 10712682919341, 31143566495273, 90587953109272, 263627037547365
REFERENCES
F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 41, 209.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.6.
R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.401.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 70, Table 3.4.1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
N. G. de Bruijn and D. A. Klarner, Multisets of aperiodic cycles, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359--368. MR0666861(84i:05008).
FORMULA
a(n) ~ c * d^n / sqrt(n), where d = A051491 = 2.9557652856519949747148... (Otter's rooted tree constant), c = 0.442876769782206479836... (for a closed form see "Mathematical Constants", p.308). - Vaclav Kotesovec, Mar 17 2015
EXAMPLE
The a(3) = 7 mappings are:
1->1, 2->2, 3->3
1->1, 2->2, 3->1 (equiv. to 1->1, 2->2, 3->2, or 1->1, 2->1, 3->3, etc.)
1->1, 2->3, 3->2
1->1, 2->1, 3->2
1->1, 2->1, 3->1
1->2, 2->3, 3->1
1->2, 2->1, 3->1
MAPLE
with(combstruct): M[ 2671 ] := [ F, {F=Set(K), K=Cycle(T), T=Prod(Z, Set(T))}, unlabeled ]:
a:=seq(count(M[2671], size=n), n=0..27); # added by W. Edwin Clark, Nov 23 2010
MATHEMATICA
Needs["Combinatorica`"];
nn=30; s[n_, k_]:=s[n, k]=a[n+1-k]+If[n<2 k, 0, s[n-k, k]]; a[1]=1; a[n_]:=a[n]=Sum[a[i] s[n-1, i] i, {i, 1, n-1}]/(n-1); rt=Table[a[i], {i, 1, nn}]; c=Drop[Apply[Plus, Table[Take[CoefficientList[CycleIndex[CyclicGroup[n], s]/.Table[s[j]->Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], nn], {n, 1, 30}]], 1]; CoefficientList[Series[Product[1/(1-x^i)^c[[i]], {i, 1, nn-1}], {x, 0, nn}], x] (* after code given by Robert A. Russell in A000081 *) (* Geoffrey Critzer, Oct 12 2012 *) max = 40; A[n_] := A[n] = If[n <= 1, n, Sum[DivisorSum[j, #*A[#]&]*A[n-j], {j, 1, n-1}]/(n-1)]; H[t_] := Sum[A[n]*t^n, {n, 0, max}]; F = 1 / Product[1 - H[x^n], {n, 1, max}] + O[x]^max; CoefficientList[F, x] (* Jean-François Alcover, Dec 01 2015, after Joerg Arndt *)
PROG
(PARI) N=66; A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
H(t)=subst(Ser( A000081, 't), 't, t); x='x+O('x^N);
F=1/prod(n=1, N, 1 - H(x^n));
Vec(F)
Number of connected functions on n points with a loop of length 2.
+10
21
0, 1, 1, 3, 6, 16, 37, 96, 239, 622, 1607, 4235, 11185, 29862, 80070, 216176, 586218, 1597578, 4370721, 12003882, 33077327, 91433267, 253454781, 704429853, 1962537755, 5479855546, 15332668869, 42983656210, 120716987723, 339596063606, 956840683968
COMMENTS
Number of unordered pairs of rooted trees with a total of n nodes.
Equivalently, the number of rooted trees on n+1 nodes where the root has degree 2.
Number of unicyclic graphs of n nodes with a cycle length of two (in other words, a double edge). - Washington Bomfim, Dec 02 2020
FORMULA
G.f.: A(x) = (B(x)^2 + B(x^2))/2 where B(x) is g.f. of A000081. a(n) = Sum_{k=1..(n-1)/2}( f(k)*f(n-k) ) + [n mod 2 = 0] * ( f(n/2)^2+f(n/2) ) /2, where f(n) = A000081(n). - Washington Bomfim, Jul 06 2012 and Dec 01 2020 a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = A187770 = 0.43992401257102530404090339... . - Vaclav Kotesovec, Sep 12 2014
MAPLE
with(numtheory): b:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> (add(b(i) *b(n-i), i=0..n) +`if`(irem(n, 2)=0, b(n/2), 0))/2: seq(a(n), n=1..50); # Alois P. Heinz, Aug 22 2008, revised Oct 07 2011 # second, re-usable version
local dh, Nprime;
dh := 0 ;
for Nprime from 0 to N do
end do:
if type(N, 'even') then
end if;
dh/2 ;
MATHEMATICA
Needs["Combinatorica`"]; nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[2], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {2, nn}] (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *) b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d b[d], {d, Divisors[j]}] b[n-j], {j, 1, n-1}])/(n-1)];
a[n_] := (Sum[b[i] b[n-i], {i, 0, n}] + If[Mod[n, 2] == 0, b[n/2], 0])/2;
PROG
(PARI) seq(max_n)= { my(V = f = vector(max_n), i=1, s); f[1]=1;
for(j=1, max_n - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k, d, d * f[d]) * f[j-k+1]));
for(n = 1, max_n, s = sum(k = 1, (n-1)/2, ( f[k] * f[n-k] ));
if(n % 2 == 1, V[i] = s, V[i] = s + (f[n/2]^2 + f[n/2])/2); i++); V };
CROSSREFS
Column 2 of A033185 (forests of rooted trees), A217781 (unicyclic graphs), A339303 (unoriented linear forests) and A339428 (connected functions).
a(n) = Sum_{m=1..n} T(m,n+1-m), array T as in A048887.
+10
15
0, 1, 2, 4, 7, 13, 23, 42, 76, 139, 255, 471, 873, 1627, 3044, 5718, 10779, 20387, 38673, 73561, 140267, 268065, 513349, 984910, 1892874, 3643569, 7023561, 13557019, 26200181, 50691977, 98182665, 190353369, 369393465, 717457655
COMMENTS
Define a "numbral arithmetic" by replacing addition with binary bitwise inclusive-OR (so that [3] + [5] = [7] etc.) and multiplication becomes shift-&-OR instead of shift-&-add (so that [3] * [3] = [7] etc.). [d] divides [n] means there exists an [e] with [d] * [e] = [n]. For example the six divisors of [14] are [1], [2], [3], [6], [7] and [14]. Then it appears that this sequence gives the number of proper divisors of [2^n-1]. Conjecture confirmed by Richard C. Schroeppel, Dec 14 2001. (End)
The number of "prime endofunctions" on n points, meaning the cardinality of the subset of the A001372(n) mappings (or mapping patterns) up to isomorphism from n (unlabeled) points to themselves (endofunctions) which are neither the sum of prime endofunctions (i.e., whose disjoint connected components are prime endofunctions) nor the categorical product of prime endofunctions. The n for which a(n) is prime (n such that the number of prime endofunctions on n points is itself prime) are 2, 4, 5, 6, 9, 13, 19, ... - Jonathan Vos Post, Nov 19 2006 For n>=1, compositions p(1)+p(2)+...+p(m)=n such that p(k)<=p(1)+1, see example. - Joerg Arndt, Dec 28 2012
LINKS
D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
FORMULA
G.f.: Sum_{k>0} x^k*(1-x^k)/(1-2*x+x^(k+1)). - Vladeta Jovovic, Feb 25 2003
EXAMPLE
There are a(6)=23 compositions p(1)+p(2)+...+p(m)=6 such that p(k)<=p(1)+1:
[ 1] [ 1 1 1 1 1 1 ]
[ 2] [ 1 1 1 1 2 ]
[ 3] [ 1 1 1 2 1 ]
[ 4] [ 1 1 2 1 1 ]
[ 5] [ 1 1 2 2 ]
[ 6] [ 1 2 1 1 1 ]
[ 7] [ 1 2 1 2 ]
[ 8] [ 1 2 2 1 ]
[ 9] [ 2 1 1 1 1 ]
[10] [ 2 1 1 2 ]
[11] [ 2 1 2 1 ]
[12] [ 2 1 3 ]
[13] [ 2 2 1 1 ]
[14] [ 2 2 2 ]
[15] [ 2 3 1 ]
[16] [ 3 1 1 1 ]
[17] [ 3 1 2 ]
[18] [ 3 2 1 ]
[19] [ 3 3 ]
[20] [ 4 1 1 ]
[21] [ 4 2 ]
[22] [ 5 1 ]
[23] [ 6 ]
(End)
PROG
(PARI)
N = 66; x = 'x + O('x^N);
gf = sum(n=0, N, (1-x^n)*x^n/(1-2*x+x^(n+1)) ) + 'c0;
v = Vec(gf); v[1]-='c0; v
Triangle read by rows: T(n,k) is the number of connected functions on n points with a loop of length k.
+10
15
1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 6, 3, 1, 1, 20, 16, 9, 4, 1, 1, 48, 37, 23, 11, 4, 1, 1, 115, 96, 62, 35, 14, 5, 1, 1, 286, 239, 169, 97, 46, 18, 5, 1, 1, 719, 622, 451, 282, 145, 63, 21, 6, 1, 1, 1842, 1607, 1217, 792, 440, 206, 80, 25, 6, 1, 1
FORMULA
G.f. of k-th column: (1/k)*Sum_{d|k} phi(d) * r(x^d)^(k/d) where r(x) is the g.f. of A000081.
EXAMPLE
Triangle begins:
1;
1, 1;
2, 1, 1;
4, 3, 1, 1;
9, 6, 3, 1, 1;
20, 16, 9, 4, 1, 1;
48, 37, 23, 11, 4, 1, 1;
115, 96, 62, 35, 14, 5, 1, 1;
286, 239, 169, 97, 46, 18, 5, 1, 1;
719, 622, 451, 282, 145, 63, 21, 6, 1, 1;
...
PROG
(PARI) \\ TreeGf is A000081 as g.f. TreeGf(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
ColSeq(n, k)={my(r=TreeGf(max(0, n+1-k))); Vec(sumdiv(k, d, eulerphi(d)*subst(r + O(x*x^(n\d)), x, x^d)^(k/d))/k, -n)}
M(n, m=n)=Mat(vector(m, k, ColSeq(n, k)~))
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) }
CROSSREFS
Columns 1..12 are A000081, A027852, A029852, A029853, A029868, A029869, A029870, A029871, A032205, A032206, A032207, A032208.
Number of partial mappings (or mapping patterns) from n points to themselves; number of partial endofunctions.
+10
6
1, 2, 6, 16, 45, 121, 338, 929, 2598, 7261, 20453, 57738, 163799, 465778, 1328697, 3798473, 10883314, 31237935, 89812975, 258595806, 745563123, 2152093734, 6218854285, 17988163439, 52078267380, 150899028305, 437571778542, 1269754686051, 3687025215421
COMMENTS
If an endofunction is partial, then some points may be unmapped (or mapped to "undefined").
FORMULA
Euler transform of A002861 + A000081 = [1, 2, 4, 9, 20, 51, 125, 329, 862, 2311, ... ] + [ 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, ...] = A124682. a(n) ~ c * d^n / sqrt(n), where d = 2.95576528565... is the Otter's rooted tree constant (see A051491) and c = 1.309039781943936352117502717... - Vaclav Kotesovec, Mar 29 2014
MATHEMATICA
nmax = 28;
a81[n_] := a81[n] = If[n<2, n, Sum[Sum[d*a81[d], {d, Divisors[j]}]*a81[n-j ], {j, 1, n-1}]/(n-1)];
A[n_] := A[n] = If[n<2, n, Sum[DivisorSum[j, #*A[#]&]*A[n-j], {j, 1, n-1} ]/(n-1)];
H[t_] := Sum[A[n]*t^n, {n, 0, nmax+2}];
F = 1/Product[1 - H[x^n], {n, 1, nmax+2}] + O[x]^(nmax+2);
A1372 = CoefficientList[F, x];
a[n_] := Sum[a81[k] * A1372[[n-k+2]], {k, 0, n+1}];
PROG
(Sage)
Pol.<t> = InfinitePolynomialRing(QQ)
@cached_function
def Z(n):
if n==0: return Pol.one()
return sum(t[k]*Z(n-k) for k in (1..n))/n
def pmagmas(n, k=1): # number of partial k-magmas on a set of n elements up to isomorphism
P = Z(n)
q = 0
coeffs = P.coefficients()
count = 0
for m in P.monomials():
p = 1
V = m.variables()
T = cartesian_product(k*[V])
for t in T:
r = [Pol.varname_key(str(u))[1] for u in t]
j = [m.degree(u) for u in t]
D = 1
lcm_r = lcm(r)
for d in divisors(lcm_r):
try: D += d*m.degrees()[-d-1]
except: break
p *= D^(prod(r)/lcm_r*prod(j))
q += coeffs[count]*p
count += 1
return q
Number of nonisomorphic connected functions with no fixed points, or proper rings with n edges.
(Formerly M1403 N0547)
+10
5
0, 1, 2, 5, 11, 31, 77, 214, 576, 1592, 4375, 12183, 33864, 94741, 265461, 746372, 2102692, 5938630, 16803610, 47639902, 135288198, 384812502, 1096141974, 3126648842, 8929715592, 25533447030, 73090099586, 209438176485, 600721031344, 1724585494225
REFERENCES
R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.399.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
MATHEMATICA
Needs["Combinatorica`"]; nn=30; s[n_, k_]:=s[n, k]=a[n+1-k]+If[n<2 k, 0, s[n-k, k]]; a[1]=1; a[n_]:=a[n]=Sum[a[i] s[n-1, i] i, {i, 1, n-1}]/(n-1); rt=Table[a[i], {i, 1, nn}]; cfd=Drop[Apply[Plus, Table[Take[CoefficientList[CycleIndex[CyclicGroup[n], s]/.Table[s[j]->Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], nn], {n, 2, 30}]], 1] (* Geoffrey Critzer, Oct 14 2012, after code given by Robert A. Russell in A000081 *)
Number of functional patterns on n elements; or digraphs with maximum outdegree 1, n arrows and every point connected to an arrow.
+10
5
1, 2, 7, 20, 61, 174, 514, 1478, 4303, 12437, 36084, 104494, 303167, 879283, 2552803, 7413583, 21544347, 62635823, 182199853, 530228946, 1543761513, 4496523995, 13102414665, 38193626823, 111375529695, 324891970936, 948051861938, 2767336312386, 8080206646244
COMMENTS
A001372 counts functional patterns from a set with n elements to itself; A000041 (partition function) counts functional patterns from a set with n elements to a disjoint set; this is the general case where the range may overlap the domain but may also include other values.
FORMULA
a(n) ~ c * d^n / sqrt(n), where d = A051491 = 2.95576528565199497471481752412..., c = 3.435908969217935496995961718... . - Vaclav Kotesovec, Sep 10 2014
EXAMPLE
For n=2 there are the following 7 digraphs:
o-+.o-+ o->o-+ o->o o-+.o->o o->o->o o->o o->o
^.|.^.| ...^.| ^..| ^.|..... ....... ...^ ....
+-+.+-+ ...+-+ +--+ +-+..... ....... o--+ o->o
MATHEMATICA
nmax = 750;
A002861 = Cases[Import["https://oeis.org/ A002861/b002861.txt", "Table"], {_, _}][[;; nmax + 2, 2]];
A000081 = Cases[Import["https://oeis.org/ A000081/b000081.txt", "Table"], {_, _}][[;; nmax + 2, 2]];
etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n - j], {j, 1, n}]/n]; b];
a = etr[b];
a[0] = 1;
Number of connected functions of n points with no symmetries.
+10
3
1, 1, 2, 4, 9, 18, 42, 91, 208, 470, 1089, 2509, 5869, 13730, 32371, 76510, 181708, 432635, 1033656, 2475384, 5943395, 14299532, 34475030, 83263872, 201441431, 488092897, 1184353643, 2877611984, 7000359244, 17049288304, 41568056484, 101449503960, 247828380511
FORMULA
"CHK" (necklace, identity, unlabeled) transform of A004111.
MAPLE
g:= proc(n) option remember; `if`(n<2, n, add(g(n-k)*add(g(d)*d*
(-1)^(k/d+1), d=numtheory[divisors](k)), k=1..n-1)/(n-1))
end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(j-1-a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> g(n)+b(n, n-1):
MATHEMATICA
g[n_] := g[n] = If[n < 2, n, Sum[g[n - k]*Sum[g[d]*d*(-1)^(k/d + 1), {d, Divisors[k]}], {k, 1, n - 1}]/(n - 1)];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[j - 1 - a[i], j]*b[n - i*j, i - 1], {j, 0, n/i}]]];
a[n_] := g[n] + b[n, n - 1];
PROG
(PARI) \\ here IdTreeGf is g.f. of A004111. IdTreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, (-1)^(k/d+1) * d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
CHK(p, n)={sum(d=1, n, moebius(d)/d*log(subst(1/(1+O(x*x^(n\d))-p), x, x^d)))}
Search completed in 0.015 seconds
| 
