A034691 -id:A034691 - cp's OEIS frontend

A004211 Shifts one place left under 2nd-order binomial transform.

1, 1, 3, 11, 49, 257, 1539, 10299, 75905, 609441, 5284451, 49134923, 487026929, 5120905441, 56878092067, 664920021819, 8155340557697, 104652541401025, 1401572711758403, 19546873773314571, 283314887789276721, 4259997696504874817, 66341623494636864963

Offset: 0

N. J. A. Sloane

Equals the eigensequence of A038207, the square of Pascal's triangle. - Gary W. Adamson, Apr 10 2009
The g.f. of the second binomial transform is 1/(1-2x-x/(1-2x/(1-2x-x/(1-4x/(1-2x-x/(1-6x/(1-2x-x/(1-8x/(1-... (continued fraction). - Paul Barry, Dec 04 2009
Length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(k)<=F(k)+2 where F(0)=0 and F(k+1)=s(k+1) if s(k+1)-s(k)=2, otherwise F(k+1)=F(k); see example and Fxtbook link. - Joerg Arndt, Apr 30 2011
It appears that the infinite set of "Shifts 1 place left under N-th order binomial transform" sequences has a production matrix of:
  1, N, 0, 0, 0, ...
  1, 1, N, 0, 0, ...
  1, 2, 1, N, 0, ...
  1, 3, 3, 1, N, ...
  ... (where a diagonal of (N,N,N,...) is appended to the right of Pascal's triangle). a(n) in each sequence is the upper left term of M^n such that N=1 generates A000110, then (N=2 - A004211), (N=3 - A004212), (N=4 - A004213), (N=5 - A005011), ... - Gary W. Adamson, Jul 29 2011
Number of "unlabeled" hierarchical orderings on set partitions of {1..n}, see comments on A034691. - Gus Wiseman, Mar 03 2016
From Lorenzo Sauras Altuzarra, Jun 17 2022: (Start)
Number of n-variate noncontradictory conjunctions of logical equalities of literals (modulo logical equivalence).
Equivalently, number of n-variate noncontradictory Krom formulas with palindromic truth-vector (modulo logical equivalence).
a(n) <= A109457(n). (End)

			From _Joerg Arndt_, Apr 30 2011: (Start)
Restricted growth strings: a(0)=1 corresponds to the empty string;
a(1)=1 to [0]; a(2)=3 to [00], [01], and [02]; a(3) = 11 to
        RGS           F
[ 1]  [ 0 0 0 ]    [ 0 0 0 ]
[ 2]  [ 0 0 1 ]    [ 0 0 0 ]
[ 3]  [ 0 0 2 ]    [ 0 0 2 ]
[ 4]  [ 0 1 0 ]    [ 0 0 0 ]
[ 5]  [ 0 1 1 ]    [ 0 0 0 ]
[ 6]  [ 0 1 2 ]    [ 0 0 2 ]
[ 7]  [ 0 2 0 ]    [ 0 2 2 ]
[ 8]  [ 0 2 1 ]    [ 0 2 2 ]
[ 9]  [ 0 2 2 ]    [ 0 2 2 ]
[10]  [ 0 2 3 ]    [ 0 2 2 ]
[11]  [ 0 2 4 ]    [ 0 2 4 ]. (End)
From _Lorenzo Sauras Altuzarra_, Jun 17 2022: (Start)
The 11 trivariate noncontradictory conjunctions of logical equalities of literals are (x <-> y) /\ (y <-> z), (~ x <-> y) /\ (y <-> z), (x <-> ~ y) /\ (~ y <-> z), (x <-> y) /\ (y <-> ~ z), (x <-> y) /\ (z <-> z), (~ x <-> y) /\ (z <-> z), (x <-> z) /\ (y <-> y), (~ x <-> z) /\ (y <-> y), (y <-> z) /\ (x <-> x), (~ y <-> z) /\ (x <-> x), and (x <-> x) /\ (y <-> y) /\ (z <-> z) (modulo logical equivalence).
The third complete Bell polynomial is x^3 + 3 x y + z; and note that (2^0)^3 + 3*2^0*2^1 + 2^2 = 11.
The truth-vector of (x <-> y) /\ (y <-> z), 10000001, is palindromic. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.5, pp. 366-368
Paul Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.
Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, On the Limiting Vacillating Tableaux for Integer Sequences, arXiv:2208.13091 [math.CO], 2022.
Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See pp. 22, 29.
David Callan (Proposer), Problem 11567, Amer. Math. Monthly, 118 (2011), 371-378.
Agustina Czenky, Unoriented 2-dimensional TQFTs and the category Rep(S_t wr Z_2), arXiv:2306.08826 [math.QA], 2023. See p. 40.
I. M. Gessel, Applications of the classical umbral calculus, arXiv:math/0108121v3 [math.CO], 2001.
Adam M. Goyt and Lara K. Pudwell, Solution to Monthly Problem 11567, 14 May 2011.
Adalbert Kerber, A matrix of combinatorial numbers related to the symmetric groups, Discrete Math., 21 (1978), 319-321.
Adalbert Kerber, A matrix of combinatorial numbers related to the symmetric groups<, Discrete Math., 21 (1978), 319-321. [Annotated scanned copy]
Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 20.
Janusz Milek, Quantum Implementation of Risk Analysis-relevant Copulas, arXiv:2002.07389 [stat.ME], 2020.
N. J. A. Sloane, Transforms

Cf. A075497 (row sums).
Cf. A038207.
Cf. A000110 (RGS where s(k) <= F(k) + 1), A004212 (RGS where s(k) <= F(k) + 3), A004213 (s(k) <= F(k) + 4), A005011 (s(k) <= F(k) + 5), A005012 (s(k) <= F(k) + 6), A075506 (s(k) <= F(k) + 7), A075507 (s(k) <= F(k) + 8), A075508 (s(k) <= F(k) + 9), A075509 (s(k) <= F(k) + 10).
Cf. A000587, A009235, A317996, A318179 - A318181.
Main diagonal of A261275.
Cf. A034691, A075729, A109457.

a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*binomial(n-1, j-1)*2^(j-1), j=1..n))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, May 30 2021
# second Maple program:
a:= n -> CompleteBellB(n, seq(2^k, k=0..n)):
seq(a(n), n=0..23);  # Lorenzo Sauras Altuzarra, Jun 17 2022

Table[ Sum[ StirlingS2[ n, k ] 2^(-k+n), {k, n} ], {n, 16} ] (* Wouter Meeussen *)
Table[2^n BellB[n, 1/2], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 20 2015 *)

a(n):=if n=0 then 1 else sum(2^(n-k)*binomial(n-1,k-1)*a(k-1),k,1,n); /* Vladimir Kruchinin, Nov 28 2011 */

x='x+O('x^66);
egf=exp(intformal(exp(2*x))); /* = 1 + x + 3/2*x^2 + 11/6*x^3 + ... */
/* egf=exp(1/2*(exp(2*x)-1)) */ /* alternative e.g.f. */
Vec(serlaplace(egf))  /* Joerg Arndt, Apr 30 2011 */

def A004211(n): return sum(2^(n-k)*stirling_number2(n, k) for k in (0..n))
print([A004211(n) for n in range(21)]) # Peter Luschny, Apr 15 2020

E.g.f. A(x) satisfies A'(x)/A(x) = e^(2x).
E.g.f.: exp(sinh(x)*exp(x)) = exp(Integral_{t = 0..x} exp(2*t)) = exp((exp(2*x)-1)/2). - Joerg Arndt, Apr 30 2011 and May 13 2011
a(n) = Sum_{k=0..n} 2^(n-k)*Stirling2(n, k). - Emeric Deutsch, Feb 11 2002
G.f.: Sum_{k >= 0} x^k/Product_{j = 1..k} (1-2*j*x). - Ralf Stephan, Apr 18 2004
Stirling transform of A000085. - Vladeta Jovovic May 14 2004
O.g.f.: A(x) = 1/(1-x-2*x^2/(1-3*x-4*x^2/(1-5*x-6*x^2/(1-... -(2*n-1)*x-2*n*x^2/(1- ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
Define f_1(x), f_2(x), ... such that f_1(x)=e^x, f_{n+1}(x) = (d/dx)(x*f_n(x)), for n=2,3,.... Then a(n) = e^(-1/2)*2^{n-1}*f_n(1/2). - Milan Janjic, May 30 2008
G.f.: 1/(1-x/(1-2x/(1-x/(1-4x/(1-x/(1-6x/(1-x/(1-8x/(1-... (continued fraction). - Paul Barry, Dec 04 2009
a(n) = upper left term in M^n, M = an infinite square production matrix with an appended diagonal of (2,2,2,...) to the right of Pascal's triangle:
  1, 2, 0, 0, 0, ...
  1, 1, 2, 0, 0, ...
  1, 2, 1, 2, 0, ...
  1, 3, 3, 1, 2, ...
  ... - Gary W. Adamson, Jul 29 2011
a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+2*x)*d/dx. Cf. A000110. - Peter Bala, Nov 25 2011
G.f. A(x) satisfies A(x)=1+x/(1-2*x)*A(x/(1-2*x)), a(n) = Sum_{k=1..n} binomial(n-1,k-1)*2^(n-k)*a(k-1), a(0)=1. - Vladimir Kruchinin, Nov 28 2011 [corrected by Ilya Gutkovskiy, May 02 2019]
From Peter Bala, May 16 2012: (Start)
Recurrence equation: a(n+1) = Sum_{k = 0..n} 2^(n-k)*C(n,k)*a(k).
Written umbrally this is a(n+1) = (a + 2)^n (expand the binomial and replace a^k with a(k)). More generally, a*f(a) = f(a+2) holds umbrally for any polynomial f(x). An inductive argument then establishes the umbral recurrence a*(a-2)*(a-4)*...*(a-2*(n-1)) = 1 with a(0) = 1. Compare with the Bell numbers B(n) = A000110(n), which satisfy the umbral recurrence B*(B-1)*...*(B-(n-1)) = 1 with B(0) = 1. Cf. A009235.
Touchard's congruence holds: for odd prime p, a(p+k) == (a(k) + a(k+1)) (mod p) for k = 0,1,2,... (adapt the proof of Theorem 10.1 in Gessel). In particular, a(p) == 2 (mod p) for odd prime p. (End)
G.f.: (2/E(0) - 1)/x  where E(k) = 1 + 1/(1 + 2*x/(1 - 4*(k+1)*x/E(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Sep 20 2012
G.f.: (1/E(0)-1)/x  where E(k) = 1 - x/(1 + 2*x - 2*x*(k+1)/E(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Sep 21 2012
a(n) = -1 + 2*Sum_{k=0..n} C(n,k)*A166922(k). - Peter Luschny, Nov 01 2012
G.f.: G(0)- 1/x where G(k) = 1 - (4*x*k-1)/(x - x^4/(x^3 - (4*x*k-1)*(4*x*k+2*x-1)*(4*x*k+4*x-1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 08 2013.
G.f.: (G(0) - 1)/(x-1) where G(k) =  1 - 1/(1-2*k*x)/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 15 2013
G.f.: -G(0) where G(k) = 1 + 2*(1-k*x)/(2*k*x - 1 - x*(2*k*x - 1)/(x - 2*(1-k*x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 29 2013
G.f.: 1/Q(0), where Q(k) = 1 - x/(1 - 2*x*(2*k+1)/( 1 - x/(1 - 4*x*(k+1)/Q(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Apr 15 2013
G.f.: 1 + x/Q(0), where Q(k)= 1 - x*(2*k+3) - x^2*(2*k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 05 2013
For n > 0, a(n) = exp(-1/2)*Sum_{k > 0} (2*k)^n/(k!*2^k). - Vladimir Reshetnikov, May 09 2013
G.f.: -(1+(2*x+1)/G(0))/x, where G(k)= 2*x*k - x - 1 - 2*(k+1)*x^2/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Jul 20 2013
G.f.: T(0)/(1-x), where T(k) = 1 - 2*x^2*(k+1)/( 2*x^2*(k+1) - (1-x-2*x*k)*(1-3*x-2*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 19 2013
Sum_{k=0..n} C(n,k)*a(k)*a(n-k) = 2^n*Bell(n) = A055882(n). - Vaclav Kotesovec, Apr 03 2016
a(n) ~ 2^n * n^n * exp(n/LambertW(2*n) - n - 1/2) / (sqrt(1 + LambertW(2*n)) * LambertW(2*n)^n). - Vaclav Kotesovec, Jan 07 2019, simplified Oct 01 2022
a(n) = B_n(2^0, ..., 2^(n - 1)), where B_n(x_1, ..., x_n) is the n-th complete Bell polynomial. - Lorenzo Sauras Altuzarra, Jun 17 2022

A275024 Total weight of the n-th twice-prime-factored multiset partition.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 3, 2, 3, 2, 3, 1, 2, 3, 4, 3, 3, 2, 4, 2, 3, 2, 4, 4, 2, 3, 3, 1, 4, 3, 5, 3, 4, 3, 4, 1, 3, 2, 5, 2, 3, 2, 4, 4, 3, 4, 5, 2, 5, 4, 3, 1, 4, 4, 4, 3, 2, 3, 5, 1, 4, 3, 6, 3, 4, 3, 5, 3, 4, 2, 5, 2, 2, 5, 4, 3, 3, 1, 6, 4, 3, 4, 4, 5, 3, 2, 5, 2, 5, 2, 4, 4, 5, 4, 6, 2, 3, 4, 6, 3, 5, 3, 4

Offset: 1

Gus Wiseman, Nov 12 2016

nonn

A multiset partition is a finite multiset of finite nonempty multisets of positive integers. The n-th twice-prime-factored multiset partition is constructed by factoring n into prime numbers and then factoring each prime index plus 1 into prime numbers. This produces a unique multiset of multisets of prime numbers which can then be normalized (see example) to produce each possible multiset partition as n ranges over all positive integers.

			The sequence of multiset partitions begins:
(), ((1)), ((2)), ((1)(1)), ((11)), ((1)(2)), ((3)),
((1)(1)(1)), ((2)(2)), ((1)(11)), ((12)), ((1)(1)(2)),
((4)), ((1)(3)), ((2)(11)), ((1)(1)(1)(1)), ((111)),
((1)(2)(2)), ((22)), ((1)(1)(11)), ((2)(3)), ((1)(12)),
((13)), ((1)(1)(1)(2)), ((11)(11)), ((1)(4)), ((2)(2)(2)),
((1)(1)(3)), ((5)), ((1)(2)(11)), ((112)), ((1)(1)(1)(1)(1)),
((2)(12)), ((1)(111)), ((3)(11)), ((1)(1)(2)(2)), ((6)), ...

Mathematics Stack Exchange, Why does mathematical convention deal so ineptly with multisets?
Wikiversity, Partitions of multisets

Cf. A007716, A034691, A096443, A255906, A249620.

Table[Total[Cases[FactorInteger[n],{p_,k_}:>k*PrimeOmega[PrimePi[p]+1]]],{n,1,100}]

If prime(k) has weight equal to the number of prime factors (counting multiplicity) of k+1, then a(n) is the sum of weights over all prime factors (counting multiplicity) of n.

A335454 Number of normal patterns matched by the n-th composition in standard order (A066099).

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 5, 3, 6, 5, 5, 2, 3, 3, 5, 3, 5, 6, 7, 3, 6, 5, 9, 5, 9, 7, 6, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 4, 7, 5, 10, 9, 9, 3, 6, 5, 9, 4, 9, 10, 12, 5, 9, 7, 13, 7, 12, 9, 7, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 5, 7, 6, 10, 9, 9, 3, 5, 6, 8, 5

Offset: 0

Gus Wiseman, Jun 14 2020

We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The a(n) patterns for n = 0, 1, 3, 7, 11, 13, 23, 83, 27, 45:
  0:  1:   11:   111:   211:   121:   2111:   2311:   1211:   2121:
---------------------------------------------------------------------
  ()  ()   ()    ()     ()     ()     ()      ()      ()      ()
      (1)  (1)   (1)    (1)    (1)    (1)     (1)     (1)     (1)
           (11)  (11)   (11)   (11)   (11)    (11)    (11)    (11)
                 (111)  (21)   (12)   (21)    (12)    (12)    (12)
                        (211)  (21)   (111)   (21)    (21)    (21)
                               (121)  (211)   (211)   (111)   (121)
                                      (2111)  (231)   (121)   (211)
                                              (2311)  (211)   (212)
                                                      (1211)  (221)
                                                              (2121)

John Tyler Rascoe, Table of n, a(n) for n = 0..8192
Wikipedia, Permutation pattern
Gus Wiseman, Statistics, classes, and transformations of standard compositions
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

References found in the links are not all included here.
Summing over indices with binary length n gives A335456(n).
The contiguous case is A335458.
The version for Heinz numbers of partitions is A335549.
Patterns are counted by A000670 and ranked by A333217.
The n-th composition has A124771(n) distinct consecutive subsequences.
Knapsack compositions are counted by A325676 and ranked by A333223.
The n-th composition has A333257(n) distinct subsequence-sums.
The n-th composition has A334299(n) distinct subsequences.
Minimal avoided patterns are counted by A335465.
Cf. A034691, A056986, A108917, A124767, A124770, A158005, A269134, A333218, A333222, A333224, A334030.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Union[mstype/@Subsets[stc[n]]]],{n,0,30}]

from itertools import combinations
def comp(n):
    # see A357625
    return
def A335465(n):
    A,B,C = set(),set(),comp(n)
    c = range(len(C))
    for j in c:
        for k in combinations(c, j):
            A.add(tuple(C[i] for i in k))
    for i in A:
        D = {v: rank + 1 for rank, v in enumerate(sorted(set(i)))}
        B.add(tuple(D[v] for v in i))
    return len(B)+1 # John Tyler Rascoe, Mar 12 2025

A166861 Euler transform of Fibonacci numbers.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 30, 56, 108, 203, 384, 716, 1342, 2487, 4614, 8510, 15675, 28749, 52652, 96102, 175110, 318240, 577328, 1045068, 1888581, 3406455, 6134530, 11029036, 19799363, 35490823, 63531134, 113570988, 202767037, 361565865, 643970774, 1145636750

Offset: 0

Franklin T. Adams-Watters, Oct 21 2009

nonn

In general, the sequence with g.f. Product_{k>=1} 1/(1-x^k)^Fibonacci(k+z), where z is nonnegative integer, is asymptotic to phi^(n + z/4) / (2 * sqrt(Pi) * 5^(1/8) * n^(3/4)) * exp((phi/10 - 1/2) * Fibonacci(z) - Fibonacci(z+1)/10 + 2 * 5^(-1/4) * phi^(z/2) * sqrt(n) + s), where s = Sum_{k>=2} (Fibonacci(z) + Fibonacci(z+1) * phi^k) / ((phi^(2*k) - phi^k - 1)*k) and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Aug 06 2015

			G.f. = 1 + x + 2*x^2 + 4*x^3 + 8*x^4 + 15*x^5 + 30*x^6 + 56*x^7 + 108*x^8 + 203*x^9 + ...

Vaclav Kotesovec, Table of n, a(n) for n = 0..4550
Loic Foissy, The Hopf algebra of Fliess operators and its dual pre-Lie algebra, 2013.
W. S. Gray, K. Ebrahimi-Fard, Affine SISO Feedback Transformation Group and Its Faa di Bruno Hopf Algebra, arXiv:1411.0222 [math.OC], 2014.
Vaclav Kotesovec, Asymptotics of the Euler transform of Fibonacci numbers, arXiv:1508.01796 [math.CO], Aug 07 2015
Vaclav Kotesovec, Asymptotics of sequence A034691

Cf. A000045, A034691, A109509, A200544, A260787, A261031, A261050, A260916, row sums of A337009.

F:= proc(n) option remember; (<<1|1>, <1|0>>^n)[1, 2] end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
      F(d), d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 12 2017

CoefficientList[Series[Product[1/(1-x^k)^Fibonacci[k], {k, 1, 40}], {x, 0, 40}], x] (* Vaclav Kotesovec, Aug 05 2015 *)

ET(v)=Vec(prod(k=1,#v,1/(1-x^k+x*O(x^#v))^v[k]))
ET(vector(40,n,fibonacci(n)))

def EulerTransform(a):
    @cached_function
    def b(n):
        if n == 0: return 1
        s = sum(sum(d * a(d) for d in divisors(j)) * b(n-j) for j in (1..n))
        return s//n
    return b
a = BinaryRecurrenceSequence(1, 1)
b = EulerTransform(a)
print([b(n) for n in range(36)]) # Peter Luschny, Nov 11 2020

G.f.: Product_{k>0} 1/(1 - x^k)^Fibonacci(k).
a(n) ~ phi^n / (2 * sqrt(Pi) * 5^(1/8) * n^(3/4)) * exp(-1/10 + 2*5^(-1/4)*sqrt(n) + s), where s = Sum_{k>=2} phi^k / ((phi^(2*k) - phi^k - 1)*k) = 0.600476601392575912969719494850393576083765123939643511355547131467... and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Aug 06 2015
G.f.: exp(Sum_{k>=1} x^k/(k*(1 - x^k - x^(2*k)))). - Ilya Gutkovskiy, May 29 2018

First formula corrected by Vaclav Kotesovec, Aug 05 2015

A320456 Numbers whose multiset multisystem spans an initial interval of positive integers.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 15, 16, 18, 19, 21, 24, 26, 27, 28, 30, 32, 35, 36, 37, 38, 39, 42, 45, 48, 49, 52, 53, 54, 56, 57, 60, 61, 63, 64, 65, 69, 70, 72, 74, 75, 76, 78, 81, 84, 89, 90, 91, 95, 96, 98, 104, 105, 106, 108, 111, 112, 113, 114, 117

Offset: 1

Gus Wiseman, Oct 13 2018

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The n-th multiset multisystem is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the 78th multiset multisystem is {{},{1},{1,2}}.

			The sequence of terms together with their multiset multisystems begins:
   1: {}
   2: {{}}
   3: {{1}}
   4: {{},{}}
   6: {{},{1}}
   7: {{1,1}}
   8: {{},{},{}}
   9: {{1},{1}}
  12: {{},{},{1}}
  13: {{1,2}}
  14: {{},{1,1}}
  15: {{1},{2}}
  16: {{},{},{},{}}
  18: {{},{1},{1}}
  19: {{1,1,1}}
  21: {{1},{1,1}}
  24: {{},{},{},{1}}
  26: {{},{1,2}}
  27: {{1},{1},{1}}
  28: {{},{},{1,1}}
  30: {{},{1},{2}}
  32: {{},{},{},{},{}}

Cf. A001222, A003963, A034691, A034729, A055932, A056239, A112798, A255906, A290103, A302242, A305052.

Cf. A320458, A320459, A320461, A320462, A320463, A320464, A320532, A320533.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
normQ[sys_]:=Or[Length[sys]==0,Union@@sys==Range[Max@@Max@@sys]];
Select[Range[100],normQ[primeMS/@primeMS[#]]&]

A306005 Number of non-isomorphic set-systems of weight n with no singletons.

Original entry on oeis.org

1, 0, 1, 1, 3, 4, 12, 19, 51, 106, 274, 647, 1773, 4664, 13418, 38861, 118690, 370588, 1202924, 4006557, 13764760, 48517672, 175603676, 651026060, 2471150365, 9590103580, 38023295735, 153871104726, 635078474978, 2671365285303, 11444367926725, 49903627379427

Offset: 0

Gus Wiseman, Jun 16 2018

nonn

A set-system is a finite set of finite nonempty sets (edges). The weight is the sum of cardinalities of the edges. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(6) = 12 set-systems:
  {{1,2,3,4,5,6}}
  {{1,2},{3,4,5,6}}
  {{1,5},{2,3,4,5}}
  {{3,4},{1,2,3,4}}
  {{1,2,3},{4,5,6}}
  {{1,2,5},{3,4,5}}
  {{1,3,4},{2,3,4}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{3,4},{5,6}}
  {{1,2},{3,5},{4,5}}
  {{1,3},{2,4},{3,4}}
  {{1,4},{2,4},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The complement is counted by A330053.

Cf. A007716, A034691, A048143, A049311, A054921, A116540, A283877, A293606, A293607, A304867, A305999, A305854-A305857, A306005-A306008.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k)) - Vec(sum(j=1, #q, if(t%q[j]==0, q[j])) + O(x*x^k), -k)}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, my(g=sum(t=1, n, subst(x*Ser(K(q, t, n\t)/t),x,x^t) )); s+=permcount(q)*polcoef(exp(g - subst(g,x,x^2)), n)); s/n!)} \\ Andrew Howroyd, Jan 16 2024

a(n) = A283877(n) - A330053(n). - Gus Wiseman, Dec 09 2019

Terms a(11) and beyond from Andrew Howroyd, Sep 01 2019

A302243 Total weight of the n-th twice-odd-factored multiset partition.

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 2, 2, 1, 3, 3, 2, 2, 3, 2, 1, 2, 3, 3, 3, 1, 2, 3, 2, 4, 2, 4, 2, 4, 1, 3, 4, 3, 1, 3, 3, 2, 3, 3, 2, 4, 1, 2, 3, 4, 4, 2, 4, 2, 3, 2, 3, 4, 3, 1, 4, 3, 3, 4, 3, 2, 2, 3, 1, 3, 5, 5, 4, 2, 2, 3, 3, 3, 5, 2, 4, 3, 2, 1, 5, 4, 2, 3, 2, 4, 5, 4, 4

Offset: 0

Gus Wiseman, Apr 03 2018

nonn

A multiset partition is a finite multiset of finite nonempty multisets of positive integers. The n-th twice-odd-factored multiset partition is constructed by factoring 2n + 1 into prime numbers and then factoring each prime index into prime numbers and taking their prime indices.

			Sequence of multiset partitions begins: (), ((1)), ((2)), ((11)), ((1)(1)), ((3)), ((12)), ((1)(2)), ((4)), ((111)), ((1)(11)), ((22)), ((2)(2)), ((1)(1)(1)), ((13)), ((5)), ((1)(3)), ((2)(11)), ((112)), ((1)(12)), ((6)).

Cf. A003963, A007716, A034691, A048673, A056239, A061775, A063834 A064216, A096443, A249620, A255397, A255906, A275024, A279789, A281113, A299757, A302242.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Sum[PrimeOmega[k],{k,primeMS[2n-1]}],{n,100}]

a(n) = A302242(2n + 1).

A316651 Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.

Original entry on oeis.org

1, 2, 12, 112, 1444, 24086, 492284, 11910790, 332827136, 10546558146, 373661603588, 14636326974270, 628032444609396, 29296137817622902, 1476092246351259964, 79889766016415899270, 4622371378514020301740, 284719443038735430679268, 18601385258191195218790756

Offset: 1

Gus Wiseman, Jul 09 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(3) = 12 trees:
  (1(11)), (111),
  (1(12)), (2(11)), (112),
  (1(22)), (2(12)), (122),
  (1(23)), (2(13)), (3(12)), (123).

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000081, A000311, A000669, A001678, A005804, A034691, A141268, A292504.
Cf. A316652, A316653, A316654, A316655, A316656, A319369.
Row sums of A319376.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
a:= n-> add(add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1), k=1..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Sep 18 2018

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]
(* Second program: *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0,
     Sum[Binomial[A[i, k] + j - 1, j] b[n - i*j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n*k, b[n, n - 1, k]];
a[n_] := Sum[Sum[A[n, k-j]*(-1)^j*Binomial[k, j], {j, 0, k-1}], {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)

\\ here R(n,k) is A000669, A050381, A220823, ...
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v,[0]))[n])); v}
seq(n)={sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k)) )} \\ Andrew Howroyd, Sep 14 2018

From Vaclav Kotesovec, Sep 18 2019: (Start)
a(n) ~ c * d^n * n^(n-1), where d = 1.37392076830840090205551979... and c = 0.41435722857311602982846...
a(n) ~ 2*log(2)*A326396(n)/n. (End)

Terms a(9) and beyond from Andrew Howroyd, Sep 14 2018

A381718 Number of normal multiset partitions of weight n into sets with distinct sums.

Original entry on oeis.org

1, 1, 2, 6, 23, 106, 549, 3184, 20353, 141615, 1063399, 8554800, 73281988, 665141182, 6369920854, 64133095134, 676690490875, 7462023572238, 85786458777923, 1025956348473929, 12739037494941490

Offset: 0

Gus Wiseman, Mar 26 2025

nonn

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The weight of a multiset partition is the sum of sizes of its blocks.

			The a(1) = 1 through a(3) = 6 multiset partitions:
  {{1}}  {{1,2}}    {{1,2,3}}
         {{1},{2}}  {{1},{1,2}}
                    {{1},{2,3}}
                    {{2},{1,2}}
                    {{2},{1,3}}
                    {{1},{2},{3}}
The a(4) = 23 factorizations:
  2*3*6  5*30    3*30    2*30    210
         10*15   6*15    6*10    2*105
         2*5*15  2*3*15  2*3*10  3*70
         3*5*10                  5*42
                                 7*30
                                 6*35
                                 10*21
                                 2*3*35
                                 2*5*21
                                 2*7*15
                                 3*5*14
                                 2*3*5*7

For distinct blocks instead of sums we have A116539, see A050326.
Without distinct sums we have A116540 (normal set multipartitions).
Twice-partitions of this type are counted by A279785.
Without strict blocks we have A326519.
Factorizations of this type are counted by A381633.
For constant instead of strict blocks we have A382203.
For distinct sizes instead of sums we have A382428, non-strict blocks A326517.
For equal instead of distinct block-sums we have A382429, non-strict blocks A326518.
A000670 counts patterns, ranked by A055932 and A333217, necklace A019536.
A001055 count factorizations, strict A045778.
Normal multiset partitions: A034691, A035310, A255906.
Set multipartitions: A089259, A270995, A296119, A318360.
Cf. A000110, A007716, A050320, A255903, A275780, A317532, A317583, A321469, A381635, A382204, A382214, A382216.

allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[mset_]:=Union[Sort[Sort/@(#/.x_Integer:>mset[[x]])]&/@sps[Range[Length[mset]]]];
Table[Length[Join@@(Select[mps[#],UnsameQ@@Total/@#&&And@@UnsameQ@@@#&]&/@allnorm[n])],{n,0,5}]

a(10)-a(11) from Robert Price, Mar 31 2025

a(12)-a(20) from Christian Sievers, Apr 05 2025

cp's OEIS Frontend

A004211 Shifts one place left under 2nd-order binomial transform.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

SageMath

Formula

A275024 Total weight of the n-th twice-prime-factored multiset partition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335454 Number of normal patterns matched by the n-th composition in standard order (A066099).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A166861 Euler transform of Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A320456 Numbers whose multiset multisystem spans an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A306005 Number of non-isomorphic set-systems of weight n with no singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A302243 Total weight of the n-th twice-odd-factored multiset partition.

Views

Author

Keywords

Comments