A319519 -id:A319519 - cp's OEIS frontend

A319501 Number T(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet such that all k letters occur at least once in the set; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 3, 0, 2, 12, 13, 0, 2, 38, 105, 73, 0, 3, 110, 588, 976, 501, 0, 4, 302, 2811, 8416, 9945, 4051, 0, 5, 806, 12354, 59488, 121710, 111396, 37633, 0, 6, 2109, 51543, 375698, 1185360, 1830822, 1366057, 394353, 0, 8, 5450, 207846, 2209276, 10096795, 23420022, 28969248, 18235680, 4596553

Offset: 0

Alois P. Heinz, Sep 20 2018

			T(2,2) = 3: {ab}, {ba}, {a,b}.
T(3,2) = 12: {aab}, {aba}, {abb}, {baa}, {bab}, {bba}, {a,ab}, {a,ba}, {a,bb}, {aa,b}, {ab,b}, {b,ba}.
T(4,2) = 38: {aaab}, {aaba}, {aabb}, {abaa}, {abab}, {abba}, {abbb}, {baaa}, {baab}, {baba}, {babb}, {bbaa}, {bbab}, {bbba}, {a,aab}, {a,aba}, {a,abb}, {a,baa}, {a,bab}, {a,bba}, {a,bbb}, {aa,ab}, {aa,ba}, {aa,bb}, {aaa,b}, {aab,b}, {ab,ba}, {ab,bb}, {aba,b}, {abb,b}, {b,baa}, {b,bab}, {b,bba}, {ba,bb}, {a,aa,b}, {a,ab,b}, {a,b,ba}, {a,b,bb}.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,    3;
  0, 2,   12,    13;
  0, 2,   38,   105,     73;
  0, 3,  110,   588,    976,     501;
  0, 4,  302,  2811,   8416,    9945,    4051;
  0, 5,  806, 12354,  59488,  121710,  111396,   37633;
  0, 6, 2109, 51543, 375698, 1185360, 1830822, 1366057, 394353;

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A000009 (for n>0), A320203, A320204, A320205, A320206, A320207, A320208, A320209, A320210, A320211.
Main diagonal gives A000262.
Row sums give A319518.
T(2n,n) gives A319519.
Cf. A257740, A292804.

h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(h(n-i*j, i-1, k)*binomial(k^i, j), j=0..n/i)))
    end:
T:= (n, k)-> add((-1)^i*binomial(k, i)*h(n$2, k-i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);

h[n_, i_, k_] := h[n, i, k] = If[n==0, 1, If[i<1, 0, Sum[h[n-i*j, i-1, k]* Binomial[k^i, j], {j, 0, n/i}]]];
T[n_, k_] := Sum[(-1)^i Binomial[k, i] h[n, n, k-i], {i, 0, k}];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 05 2020, after Alois P. Heinz *)

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A292804(n,k-i).

A257742 Number of multisets of nonempty words with a total of 2n letters over n-ary alphabet such that all n letters occur at least once in the multiset.

Original entry on oeis.org

1, 2, 49, 3334, 428653, 87804401, 26047147641, 10515038040403, 5527943088161719, 3662449762145471938, 2981185419002290273673, 2921408464370908053081409, 3389743512704136305019696050, 4593040689601644978081159072298, 7182956101782940369861692674495595

Offset: 0

Alois P. Heinz, May 06 2015

nonn

			a(0) = 1: {}.
a(1) = 2: {aa}, {a,a}.
a(2) = 49: {aaab}, {aaba}, {aabb}, {abaa}, {abab}, {abba}, {abbb}, {baaa}, {baab}, {baba}, {babb}, {bbaa}, {bbab}, {bbba}, {a,aab}, {a,aba}, {a,abb}, {a,baa}, {a,bab}, {a,bba}, {a,bbb}, {aa,ab}, {aa,ba}, {aa,bb}, {aaa,b}, {aab,b}, {ab,ab}, {ab,ba}, {ab,bb}, {aba,b}, {abb,b}, {b,baa}, {b,bab}, {b,bba}, {ba,ba}, {ba,bb}, {a,a,ab}, {a,a,ba}, {a,a,bb}, {a,aa,b}, {a,ab,b}, {a,b,ba}, {a,b,bb}, {aa,b,b}, {ab,b,b}, {b,b,ba}, {a,a,a,b}, {a,a,b,b}, {a,b,b,b}.

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

Cf. A257740, A319519.

A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[DivisorSum[j, #*k^# &]*
     A[n - j, k], {j, 1, n}]/n];
T[n_, k_] := Sum[A[n, k - i]*(-1)^i*Binomial[k, i], {i, 0, k}];
a[n_] := T[2n, n]; Table[a[n], {n, 0, 15}]
(* Jean-François Alcover, May 10 2022, after Alois P. Heinz in A257740 *)

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

New name from Alois P. Heinz, Sep 21 2018

cp's OEIS Frontend

A319501 Number T(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet such that all k letters occur at least once in the set; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula