A144935 -id:A144935 - cp's OEIS frontend

A330038 a(1) = 1, a(n) = [n/2] + a([n/2]) + a([(n+1)/2]) for n > 1, where [x] = floor(x).

1, 3, 5, 8, 10, 13, 16, 20, 22, 25, 28, 32, 35, 39, 43, 48, 50, 53, 56, 60, 63, 67, 71, 76, 79, 83, 87, 92, 96, 101, 106, 112, 114, 117, 120, 124, 127, 131, 135, 140, 143, 147, 151, 156, 160, 165, 170, 176, 179, 183, 187, 192, 196, 201, 206, 212, 216, 221, 226, 232

Offset: 1

Stefano Spezia, Nov 28 2019

nonn

a(n) is a sharp lower bound of the greatest whole number k such that there is a hypergraph (V, H) with |V| = k having no isolated vertices and containing no partitions of size greater than n (see Brian & Larson link, i.e. Definition 3.1, Lemma 4.2 and Proof of Theorem 4.6).

Partial sums of A063787. - Robert Israel, Nov 28 2019

Will Brian and Paul B. Larson, Choosing between incompatible ideals, arXiv:1908.10914 [math.CO], 2019.

Cf. A004526, A063787 (first differences), A000788, A272011.

Cf. A144935, A325831.

I:=[1]; [n le 1 select I[n] else Floor(n/2)+Self(Floor(n/2))+Self(Floor((n+1)/2)): n in [1..60]];

f:= proc(n) option remember;
floor(n/2) + procname(floor(n/2)) + procname(floor((n+1)/2))
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Nov 28 2019

a[1] = 1; a[n_] := a[n] = Floor[n/2] + a[Floor[n/2]] + a[Floor[(n + 1)/2]];  Array[a, 60] (* Amiram Eldar, Nov 28 2019 *)

a(n) = my(v=binary(n),t=#v); for(i=1,#v, if(v[i],v[i]=t++,t--);); fromdigits(v,2)>>1; \\ Kevin Ryde, Dec 16 2021

# Kevin Ryde's first formula
def a(n): return sum(bin(i).count("1") for i in range(n)) + n
print([a(n) for n in range(1, 61)]) # Michael S. Branicky, Dec 16 2021

# Kevin Ryde's second formula
def a(n):
    b = list(map(int, bin(n)[2:]))
    e = [i for i, bi in enumerate(b[::-1]) if bi][::-1]
    return sum((ei + 2*i)*2**ei for i, ei in enumerate(e, 1))//2
print([a(n) for n in range(1, 61)]) # Michael S. Branicky, Dec 16 2021

G.f. g(z) satisfies g(z) = z^2/((1+z)(1-z)^2) + (1+z)^2 g(z^2)/z. - Robert Israel, Nov 28 2019
From Kevin Ryde, Dec 16 2021: (Start)
a(n) = A000788(n-1) + n.
a(n) = (1/2) * Sum_{i=1..k} (e[i]+2*i) * 2^e[i], where binary expansion n = 2^e[1] + ... + 2^e[k] with descending exponents e[1] > e[2] > ... > e[k] (A272011).
(End)

A144937 Number of hyperforests with n labeled vertices when edges of size 1 are allowed (with no two equal edges), with at least one component of order 1.

Original entry on oeis.org

2, 4, 32, 368, 6752, 171648, 5638656, 227787008, 10932927488, 608031869952, 38451260291072, 2724757330591744, 213848122843791360, 18412354032091807744, 1725472542353497456640, 174827224579118545174528

Offset: 1

Washington Bomfim, Sep 25 2008

nonn

			For n=2 we do not have an hypertree of order 2. The possibilities are one forest, two hyperforests composed by one loop plus one tree and one hyperforest composed by two loops. So a(2)=4.

D. E. Knuth: The Art of Computer Programming, Volume 4, Generating All Combinations and Partitions Fascicle 3, Section 7.2.1.4. Generating all partitions. Page 38, Algorithm H.

Cf. A134956(hyperforests), A144935(hyperforests without components of order 1).

a(n) = A134956(n) - A144935(n).

cp's OEIS Frontend

A330038 a(1) = 1, a(n) = [n/2] + a([n/2]) + a([(n+1)/2]) for n > 1, where [x] = floor(x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python