A360634 -id:A360634 - cp's OEIS frontend

A102866 Number of finite languages over a binary alphabet (set of nonempty binary words of total length n).

1, 2, 5, 16, 42, 116, 310, 816, 2121, 5466, 13937, 35248, 88494, 220644, 546778, 1347344, 3302780, 8057344, 19568892, 47329264, 114025786, 273709732, 654765342, 1561257968, 3711373005, 8797021714, 20794198581, 49024480880, 115292809910, 270495295636

Offset: 0

Philippe Flajolet, Mar 01 2005

nonn

Analogous to A034899 (which also enumerates multisets of words)

			a(2) = 5 because the sets are {a,b}, {aa}, {ab}, {ba}, {bb}.
a(3) = 16 because the sets are {a,aa}, {a,ab}, {a,ba}, {a,bb}, {b,aa}, {b,ab}, {b,ba}, {b,bb}, {aaa}, {aab}, {aba}, {abb}, {baa}, {bab}, {bba}, {bbb}.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 64
Stefan Gerhold, Counting finite languages by total word length, INTEGERS 11 (2011), #A44.
Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.

Cf. A000079, A034899, A256142.
Column k=2 of A292804.
Row sums of A208741 and of A360634.

series(exp(add((-1)^(j-1)/j*(2*z^j)/(1-2*z^j),j=1..40)),z,40);

nn = 20; p = Product[(1 + x^i)^(2^i), {i, 1, nn}]; CoefficientList[Series[p, {x, 0, nn}], x] (* Geoffrey Critzer, Mar 07 2012 *)
CoefficientList[Series[E^Sum[(-1)^(k-1)/k*(2*x^k)/(1-2*x^k), {k,1,30}], {x, 0, 30}], x] (* Vaclav Kotesovec, Sep 13 2014 *)

G.f.: exp(Sum((-1)^(j-1)/j*(2*z^j)/(1-2*z^j), j=1..infinity)).
Asymptotics (Gerhold, 2011): a(n) ~ c * 2^(n-1)*exp(2*sqrt(n)-1/2) / (sqrt(Pi) * n^(3/4)), where c = exp( Sum_{k>=2} (-1)^(k-1)/(k*(2^(k-1)-1)) ) = 0.6602994483152065685... . - Vaclav Kotesovec, Sep 13 2014
Weigh transform of A000079. - Alois P. Heinz, Jun 25 2018

A095944 Number of subsets S of {1,2,...,n} which contain a number that is greater than the sum of the other numbers in S.

Original entry on oeis.org

1, 3, 6, 11, 18, 28, 42, 61, 86, 119, 162, 217, 287, 375, 485, 622, 791, 998, 1251, 1558, 1929, 2376, 2912, 3552, 4314, 5218, 6287, 7548, 9031, 10770, 12805, 15180, 17945, 21158, 24883, 29193, 34171, 39909, 46511, 54095, 62792, 72749, 84132, 97125

Offset: 1

W. Edwin Clark, Jul 13 2004

Convolution of A000009 and A001477. - Vaclav Kotesovec, Mar 12 2016

			a(3) = 6 since the subsets {1},{2},{3},{1,2},{1,3},{2,3} are the only subsets of {1,2,3} which contain a number greater than the sum of the other numbers in the set.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 500 terms from T. D. Noe)

Equals 2^n - 1 - A095941(n).

Column k=1 of A360634.

r[s_, x_] := r[s,x] = 1 + Sum[r[s-i, i-1], {i, Min[x,s]}]; f[n_] := Sum[r[k-1, k-1], {k, n}]; Array[f, 50] (* Giovanni Resta, Mar 16 2006 *)
Accumulate[ Accumulate[q = PartitionsQ[ Range[1, 50]]]+1] - Accumulate[q] (* Jean-François Alcover, Nov 14 2011 *)

Second differences are A000009, partitions into distinct parts. Proof from Fred W. Helenius (fredh(AT)ix.netcom.com): Let k be the largest element (the "dictator") in S and let j be the sum of the remaining elements, so 0 <= j < k. For a given k and j, the number of subsets S is just the number of partitions j into distinct parts; call that a(j). Then b(n) = Sum_{1<=k<=n} Sum_{0<=jN. J. A. Sloane and proved by Michael Reid.
a(n) ~ 3^(3/4) * n^(1/4) * exp(sqrt(n/3)*Pi) / Pi^2. - Vaclav Kotesovec, Mar 12 2016
G.f.: (x/(1 - x)^2)*Product_{k>=1} (1 + x^k). - Ilya Gutkovskiy, Jan 03 2017

More terms from John W. Layman, Aug 10 2004

More terms from Giovanni Resta, Mar 16 2006

A208741 Triangular array read by rows. T(n,k) is the number of sets of exactly k distinct binary words with a total of n letters.

Original entry on oeis.org

2, 4, 1, 8, 8, 16, 22, 4, 32, 64, 20, 64, 156, 84, 6, 128, 384, 264, 40, 256, 888, 784, 189, 4, 512, 2048, 2152, 704, 50, 1024, 4592, 5664, 2384, 272, 1, 2048, 10240, 14368, 7328, 1232, 32, 4096, 22496, 35568, 21382, 4704, 248

Offset: 1

Geoffrey Critzer, Mar 08 2012

Equivalently, T(n,k) is the number of integer partitions of n into distinct parts with two types of 1's, four types of 2's, ... , 2^i types of i's,...; where k is the number of summands (of any type).
Row sums = A102866.
Row lengths increase by 1 at n=A061168(offset).

			T(3,2) = 8 because we have: {a,aa}, {a,ab}, {a,ba}, {a,bb}, {b,aa}, {b,ab}, {b,ba}, {b,bb}; 2 word languages with total length 3.
Triangle T(n,k) begins:
   2;
   4,     1;
   8,     8;
  16,    22,    4;
  32,    64,   20;
  64,   156,   84,   6;
  ...

Alois P. Heinz, Rows n = 0..300, flattened
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 64

Cf. A102866, A209406, A360634.

h:= proc(n, i) option remember; expand(`if`(n=0, 1, `if`(i<1, 0,
      add(h(n-i*j, i-1)*binomial(2^i, j)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(h(n$2)):
seq(T(n), n=1..15);  # Alois P. Heinz, Sep 24 2017

nn=12; p=Product[(1+y x^i)^(2^i), {i,1,nn}]; f[list_] := Select[list, #>0&]; Map[f, Drop[CoefficientList[Series[p[x,y], {x,0,nn}], {x,y}], 1]]//Flatten

O.g.f.: Product_{i>=1} (1 + y*x^i)^(2^i).

A055375 Euler transform of Pascal's triangle A007318.

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 3, 7, 7, 3, 5, 14, 21, 14, 5, 7, 26, 48, 48, 26, 7, 11, 45, 103, 131, 103, 45, 11, 15, 75, 198, 312, 312, 198, 75, 15, 22, 120, 366, 674, 830, 674, 366, 120, 22, 30, 187, 637, 1359, 1961, 1961, 1359, 637, 187, 30, 42, 284, 1078, 2584, 4302, 5066, 4302, 2584, 1078, 284, 42

Offset: 0

Christian G. Bower, May 16 2000

Number of partitions of n objects, k of which are black, into parts each of which is a sequence of objects. E.g. T(3,1) = 7; the partitions are [BWW], [WBW], [WWB], [BW,W], [WB,W], [WW,B] and [B,W,W]. - Franklin T. Adams-Watters, Jan 10 2007

			Triangle begins
   1;
   1,  1;
   2,  3,   2;
   3,  7,   7,   3;
   5, 14,  21,  14,   5;
   7, 26,  48,  48,  26,   7;
  11, 45, 103, 131, 103,  45, 11;
  15, 75, 198, 312, 312, 198, 75, 15;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
N. J. A. Sloane, Transforms
Index entries for triangles and arrays related to Pascal's triangle

Row sums give A034899.
Columns k=0-1 give: A000041, A014153(n-1) for n>=1.
T(2n,n) gives A360626.
Cf. A007318, A034691, A209406, A360634.

g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(
      g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i)+k-1, k), k=0..j))))
    end:
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
     `if`(i<1, 0, add(b(n-i*j, i-1)*g(i$2, j), j=0..n/i))))
    end:
T:= (n, k)-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2)):
seq(T(n), n=0..15);  # Alois P. Heinz, Feb 14 2023

nmax = 10; pp = Product[Product[1/(1 - x^i*y^j)^Binomial[i, j], {j, 0, i}], {i, 1, nmax}]; t[n_, k_] := SeriesCoefficient[pp, {x, 0, n}, {y, 0, k}]; Table[t[n, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 18 2017 *)

G.f.: Product_{i>=1} Product_{j=0..i} 1/(1 - x^i y^j)^C(i,j). - Franklin T. Adams-Watters, Jan 10 2007

Sum_{k=0..2n} (-1)^k * T(2n,k) = A034691(n). - Alois P. Heinz, Dec 05 2023

A360638 Number of sets of nonempty words over binary alphabet where each letter occurs n times.

Original entry on oeis.org

1, 3, 16, 100, 593, 3497, 20316, 116378, 658214, 3679450, 20350028, 111459648, 605060633, 3257784589, 17408647968, 92378535290, 487031130699, 2552197485757, 13298890952222, 68930923717598, 355507581655752, 1824924721216084, 9326440815314046, 47464093855706540

Offset: 0

Alois P. Heinz, Feb 14 2023

nonn

			a(0) = 1: {}.
a(1) = 3: {ab}, {ba}, {a,b}.
a(2) = 16: {aabb}, {abab}, {abba}, {baab}, {baba}, {bbaa}, {a,abb}, {a,bab}, {a,bba}, {aa,bb}, {aab,b}, {ab,ba}, {aba,b}, {b,baa}, {a,ab,b}, {a,b,ba}.

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

Cf. A080277, A360626 (the same for multisets), A360634.

g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(
      g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i), k), k=0..j))))
    end:
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
     `if`(i<1, 0, add(b(n-i*j, i-1)*g(i$2, j), j=0..n/i))))
    end:
a:= n-> coeff(b(2*n$2), x, n):
seq(a(n), n=0..31);

g[n_, i_, j_] := g[n, i, j] = Expand[If[j == 0, 1, If[i < 0, 0, Sum[
    g[n, i - 1, j - k]*x^(i*k)*Binomial[Binomial[n, i], k], {k, 0, j}]]]];
b[n_, i_] := b[n, i] = Expand[If[n == 0, 1,
    If[i < 1, 0, Sum[b[n - i*j, i - 1]*g[i, i, j], {j, 0, n/i}]]]];
a[n_] := Coefficient[b[2n, 2n], x, n];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Dec 09 2023, after Alois P. Heinz *)

a(n) = A360634(2n,n).

a(n) mod 2 = 1 <=> n in { A080277 } U {0}.

A200751 Expansion of Product_{k>0} (1 - x^k)^(2^(k-1)) in powers of x.

Original entry on oeis.org

1, -1, -2, -2, -3, -1, -2, 6, 12, 36, 74, 162, 301, 599, 1090, 1986, 3479, 5993, 9852, 15644, 23094, 30690, 31868, 9068, -82372, -345308, -1010956, -2577868, -6098822, -13751218, -29962588, -63604140, -132205949, -269982371, -542866266, -1076420666

Offset: 0

Michael Somos, Nov 21 2011

sign

			1 - x - 2*x^2 - 2*x^3 - 3*x^4 - x^5 - 2*x^6 + 6*x^7 + 12*x^8 + 36*x^9 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A034691, A083413, A360634.

a[n_] := SeriesCoefficient[Series[Product[(1 - x^k)^2^(k - 1),
{k, n}], {x, 0, n}], n]; Table[a[n], {n, 0, 35}] (* T. D. Noe, Nov 23 2011 *)

{a(n) = local(A); if( n<0, 0, A = x * O(x^n); polcoeff( prod( k=1, n, (1 - x^k + A) ^ 2^(k - 1)), n))}

Let F(a, x) = (1 - a) * (1 - a*x)^2 * (1 - a*x^2)^4 * ... where |x|<1/2. Then F(a, x) = (1 - a) * F(a*x, x)^2 and g.f. A(x) = F(x, x).
Euler transform of [ -1, -2, -4, -8, -16, ... ].
G.f.: (1 - x) * (1 - x^2)^2 * (1 - x^3)^4 * ...
Convolution inverse of A034691.
a(0) = 1; a(n) = -(1/n) * Sum_{k=1..n} A083413(k) * a(n-k). - Seiichi Manyama, Jul 17 2023
a(n) = Sum_{k=0..2n} (-1)^k*A360634(2n,k). - Alois P. Heinz, Sep 09 2023

A360650 Number of sets of nonempty words over binary alphabet with a total of n letters of which 2 are the first letter.

Original entry on oeis.org

0, 0, 1, 6, 16, 37, 73, 133, 227, 370, 580, 881, 1305, 1890, 2687, 3756, 5175, 7037, 9460, 12582, 16577, 21649, 28048, 36070, 46072, 58474, 73778, 92574, 115559, 143551, 177510, 218556, 267997, 327355, 398394, 483162, 584023, 703708, 845361, 1012600, 1209573

Offset: 0

Alois P. Heinz, Feb 15 2023

nonn

			a(2) = 1: {aa}.
a(3) = 6: {aab}, {aba}, {baa}, {a,ab}, {a,ba}, {aa,b}.
a(4) = 16: {aabb}, {abab}, {abba}, {baab}, {baba}, {bbaa}, {a,abb}, {a,bab}, {a,bba}, {aa,bb}, {aab,b}, {ab,ba}, {aba,b}, {b,baa}, {a,ab,b}, {a,b,ba}.

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

Column k=2 of A360634.

g:= proc(n, i, j) option remember; convert(series(`if`(j=0, 1,
      `if`(i<0, 0, add(g(n, i-1, j-k)*x^(i*k)*binomial(
          binomial(n, i), k), k=0..j))), x, 3), polynom)
    end:
b:= proc(n, i) option remember; convert(series(`if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*g(i$2, j), j=0..n/i))), x, 3), polynom)
    end:
a:= n-> coeff(b(n$2), x, 2):
seq(a(n), n=0..45);

a(n) = A360634(n,2).

cp's OEIS Frontend

A102866 Number of finite languages over a binary alphabet (set of nonempty binary words of total length n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A095944 Number of subsets S of {1,2,...,n} which contain a number that is greater than the sum of the other numbers in S.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A208741 Triangular array read by rows. T(n,k) is the number of sets of exactly k distinct binary words with a total of n letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A055375 Euler transform of Pascal's triangle A007318.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A360638 Number of sets of nonempty words over binary alphabet where each letter occurs n times.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A200751 Expansion of Product_{k>0} (1 - x^k)^(2^(k-1)) in powers of x.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A360650 Number of sets of nonempty words over binary alphabet with a total of n letters of which 2 are the first letter.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple