0,2

Table of n, a(n) for n=0..23.

a(n) = Sum_{k=0..n} binomial(n,k) * A000111(k+1).

a(n) ~ 2^(n + 7/2) * n^(n + 3/2) / (Pi^(n + 3/2) * exp(n - Pi/2)). - Vaclav Kotesovec, Oct 25 2021

b:= proc(u, o) option remember; `if`(u+o=0, 1,

      add(b(o-1+j, u-j), j=1..u))

    end:

a:= n-> add(binomial(n, k)*b(k+1, 0), k=0..n):

seq(a(n), n=0..23);  # Alois P. Heinz, Oct 24 2021

nmax = 23; CoefficientList[Series[Exp[x]/(1 - Sin[x]), {x, 0, nmax}], x] Range[0, nmax]!

(PARI) my(x='x+O('x^40)); Vec(serlaplace(exp(x)/(1-sin(x)))) \\ Michel Marcus, Oct 24 2021

Cf. A000111, A000667, A186364, A330046, A348587.

nonn,new

Ilya Gutkovskiy, Oct 24 2021

approved

0,2

The matrix inverse M = T^(-1) has terms M(n,n) = 1 for n >= 0, M(n,n-1) = -(n+1) for n > 0, and M(n,n-2) = n for n > 1, otherwise 0.

Table of n, a(n) for n=0..54.

T(n,n) = 1 and T(2*n,n) = A109398(n) for n >= 0; T(n,n-1) = n+1 for n > 0; T(n,n-2) = n^2 for n > 1.

T(n,k) - T(n-1,k) = (n!) / (k!) = A094587(n,k) for 0 <= k < n.

T(n,k) = (k+2) * (T(n,k+1) - T(n,k+2)) for 0 <= k < n-1.

T(n,k) = (T(n,k-1) - 1) / k for 0 < k <= n.

T(n,k) * T(n-1,k-1) - T(n-1,k) * T(n,k-1) = (n!) / (k!) for 0 < k < n.

T(n,1) = T(n,0)-1 = Sum_{k=0..n-1} T(n,k)/(k+2) for n > 0 (conjectured).

Sum_{k=0..n} binomial(k+r,k) * (1-k) * T(n+r,k+r) = binomial(n+r+1,n) for n >= 0 and r >= 0.

Sum_{k=0..n} (-1)^k * (k+1) * T(n,k) = (1 + (-1)^n) / 2 for n >= 0.

Sum_{k=0..n} (-1)^k * (k!) * T(n,k) = Sum_{k=0..n} (k!) * (1+(-1)^k) / 2 for n >= 0.

The row polynomials p(n,x) = Sum_{k=0..n} T(n,k) * x^k for n >= 0 satisfy the following equations:

  (a) p(n,x) - p'(n,x) = (x^(n+1)-1) / (x-1) for n >= 0, where p' is the first derivative of p;

  (b) p(n,x) - (n+1) * p(n-1,x) + n * p(n-2,x) = x^n for n > 1.

  (c) p(n,x) = (x+1) * p(n-1,x) + 1 + Sum_{i=1..n-1} (d/dx)^i p(n-1,x) for n > 0 (conjectured).

Row sums p(n,1) equal A002104(n+1) for n >= 0.

Alternating row sums p(n,-1) equal A173184(n) for n >= 0 (conjectured).

The triangle T(n,k) for 0 <= k <= n starts:

n\k :       0       1       2      3      4     5    6   7   8  9

=================================================================

  0 :       1

  1 :       2       1

  2 :       4       3       1

  3 :      10       9       4      1

  4 :      34      33      16      5      1

  5 :     154     153      76     25      6     1

  6 :     874     873     436    145     36     7    1

  7 :    5914    5913    2956    985    246    49    8   1

  8 :   46234   46233   23116   7705   1926   385   64   9   1

  9 :  409114  409113  204556  68185  17046  3409  568  81  10  1

  etc.

T[n_, k_] := Sum[i!, {i, k, n}]/k!; Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Amiram Eldar, Oct 20 2021 *)

Cf. A109398, A094587, A002104 (row sums), A173184 (alt. row sums), A000012 (main diagonal), A000027(1st subdiagonal), A000290 (2nd subdiagonal), A081437 (3rd subdiagonal), A192398 (4th subdiagonal), A003422 (column 0), A007489 (column 1), A345889 (column 2).

nonn,easy,tabl,new

Werner Schulte, Oct 20 2021

approved

1,3

Table of n, a(n) for n=1..25.

M. Bouvel, L. Cioni and B. Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021.

B. E. Tenner, Interval posets for permutations, arXiv:2007.06142 [math.CO], 2020-2021.

a(n) = (1/n) * Sum_{i=1..(n-1)} Sum_{k=0..Min(i,(n-i-1)/2)} binomial(n+i-1,i)* binomial(i,k)*binomial(n-2k-2,i-1) if n>1. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 18).

G.f. A(z) = Sum_{n>=0} a(n)*z^n satisfies the equation A(z) = z + (A(z)^2 + A(z)^4)/(1-A(z)). Proved in M. Bouvel, L. Cioni, B. Izart (Equation (1) page 14).

Asymptotic behavior of a(n) is c*n^(-3/2)*r^n with c approximately 0.0622 and r approximately 6.1403. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 19).

Join[{1}, Table[Sum[Sum[Binomial[n+i-1, i]Binomial[i, k]Binomial[n-2k-2, i-1], {k, 0, Min[i, (n-i-1)/2]}], {i, n-1}]/n, {n, 2, 25}]] (* Stefano Spezia, Oct 23 2021 *)

(PARI) a(n) = if (n==1, 1, (1/n) * sum(i=1, n-1, sum(k=0, min(i, (n-i-1)/2), binomial(n+i-1, i)* binomial(i, k)*binomial(n-2*k-2, i-1)))); \\ Michel Marcus, Oct 21 2021

For interval posets which are in addition trees, see A348515.

nonn,new

Mathilde Bouvel, Oct 21 2021

approved

1,3

Table of n, a(n) for n=1..27.

M. Bouvel, L. Cioni and B. Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021.

B. E. Tenner, Interval posets for permutations, arXiv:2007.06142 [math.CO], 2020-2021.

a(n) = (1/n) * [binomial(2n-2,n-1) + Sum_{i=1..(n-3)} Sum_{k=1..Min(i,(n-i-1)/2)} binomial(n+i-1,i)*binomial(i,k)*binomial(n-i-k-2,k-1) ] if n>1. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 21).

G.f. A(z) = Sum_{n>=0} a(n)*z^n satisfies the equation A(z) = z + A(z)^2 + A(z)^4/(1-A(z)). Proved in M. Bouvel, L. Cioni, B. Izart (Equation (6) page 17).

Asymptotic behavior of a(n) is c*n^(-3/2)*r^n with c approximately 0.0792 and r approximately 4.8920. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 22).

Array[(1/#)*(Binomial[2 # - 2, # - 1] + Sum[Sum[Binomial[# + i - 1, i]*Binomial[i, k]*Binomial[# - i - k - 2, k - 1], {k, Min[i, (# - i - 1)/2]}], {i, # - 3}]) &, 27] (* Michael De Vlieger, Oct 21 2021 *)

(PARI) a(n) = (1/n) * (binomial(2*n-2, n-1) + sum(i=1, n-3, sum(k=1, min(i, (n-i-1)/2), binomial(n+i-1, i)*binomial(i, k)*binomial(n-i-k-2, k-1)))); \\ Michel Marcus, Oct 21 2021

For interval posets which are not necessarily trees, see A348479.

nonn,new

Mathilde Bouvel, Oct 21 2021

approved

1,4

The class of threshold graphs is the smallest class of graphs that includes K1 and is closed under adding isolated vertices and dominating vertices.

Table of n, a(n) for n=1..55.

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.

Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.

T(1,1) = 1; for n >= 2, T(n,1) = A005840(n)/2; for n >= 3 and 2 <= k <= n-1, T(n,k) = binomial(n,k-1)*T(n-k+1,1); and for n >= 2, T(n,n)=1.

T(n, k) = binomial(n, k-1)*A053525(n - k + 1) if k != n, otherwise 1. - Peter Luschny, Oct 24 2021

Triangle begins:

         1;

         1,        1;

         4,        3,       1;

        23,       16,       6,       1;

       166,      115,      40,      10,      1;

      1437,      996,     345,      80,     15,     1;

     14512,    10059,    3486,     805,    140,    21,    1;

    167491,   116096,   40236,    9296,   1610,   224,   28,   1;

   2174746,  1507419,  522432,  120708,  20916,  2898,  336,  36,  1;

  31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1;

...

T := (n, k) -> `if`(n = k, 1, binomial(n, k-1)*A053525(n-k+1)):

for n from 1 to 10 do seq(T(n, k), k=1..n) od; # Peter Luschny, Oct 24 2021

eulerian[0, 0] := 1; eulerian[n_, m_] := eulerian[n, m] =

Sum[((-1)^k)*Binomial[n + 1, k]*((m + 1 - k)^n), {k, 0, m + 1}];

(* t[n] counts the number of labelled threshold graphs on n vertices *)

t[0] = 1; t[1] = 1;

t[n_] := t[n] = Sum[(n - k)*eulerian[n - 1, k - 1]*(2^k), {k, 1, n - 1}];

T[1, 1] := 1; T[n_, 1] := T[n, 1] = (1/2)*t[n]; T[n_, n_] := T[n, n] = 1;

T[n_, k_] := T[n, k] = Binomial[n, k - 1]*T[n - k + 1, 1];

Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten

Cf. A005840 (row sums), A317057 (column k=1), A053525.

nonn,tabl,new

David Galvin, Oct 18 2021

approved

1,5

Ordered partitions are also referred to as weak orders.

Table of n, a(n) for n=1..55.

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.

T(n,k) = Sum_{j=1..n-1} (n-j)*A173018(n-1, j-1)*binomial(j-1, n-k-1).

For n=3, the ordered partitions of {1,2,3} in which the first block has size at least 2 are 123, 12/3, 13/2 and 23/1, so T(3,1)=1, T(3,2)=3 and T(3,3)=0.

Triangle begins:

0;

1,     0;

1,     3,     0;

1,    10,    12,       0;

1,    25,    80,      60,       0;

1,    56,   360,     660,     360,       0;

1,   119,  1372.    4620,    5880,    2520,        0;

1,   246,  4788,   26376,   58800,   57120,    20160,        0;

1,   501, 15864,  134316,  466704,  771120,   604800,   181440,       0;

1,  1012, 50880,  637020, 3238200, 8094240, 10584000,  6955200, 1814400, 0;

...

b:= proc(n, t) option remember; expand(`if`(n=0, 1,

      add(x*b(n-j, 1)*binomial(n, j), j=t..n)))

    end:

T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 2)):

seq(T(n), n=1..10);  # Alois P. Heinz, Oct 24 2021

eulerian[n_, m_] := eulerian[n, m] =

  Sum[((-1)^k)*Binomial[n+1, k]*((m+1-k)^n), {k, 0, m+1}] (*eulerian[n, m] is an eulerian number, counting the number of permutations of [n] with m descents*);

op2[n_, k_] := op2[n, k] =

   Sum[(n-j)*eulerian[n-1, j-1]*Binomial[j-1, n-k-1], {j, 1, n-1}] (*op2[n, k] counts number of ordered partition on [n] with k parts, with first part having size at least 2*); Table[op2[n, k], {n, 1, 12}, {k, 1, n}]

(PARI) TE(n, k) = sum(j=0, k, (-1)^j * (k-j)^n * binomial( n+1, j)); \\ A008292

T(n, k) = sum(j=1, n-1, (n-j)*TE(n-1, j)*binomial(j-1, n-k-1)); \\ Michel Marcus, Oct 24 2021

Row sums are A053525.

Cf. A173018, A000247, A001710, A131689.

nonn,tabl,new

David Galvin, Oct 23 2021

approved

1,2

Do all the positive integers appear in this sequence?

Table of n, a(n) for n=1..63.

a(8) = 29 and digitsum(29) = 11 is already in the sequence, so a(9) = a(8) + 8 = 29 + 8 = 37.

a(9) = 37 and digitsum(37) = 3 + 7 = 10 is not yet in the sequence, so a(10) = 10.

Written as an irregular triangle, in which each line begins with a term which is the digit sum of its preceding term, the sequence begins:

   1,  2,   4,   7,  11,  16,  22,  29,  37;

  10, 20,  31,  43,  56,  70,  85;

  13, 30;

   3, 22,  42;

   6, 28,  51,  75;

  12, 38,  65,  93, 122;

   5, 36;

   9, 42,  76, 111, 147, 184, 222, 261, 301, 342, 384;

  15, 59;

  14, 60, 107;

  ...

seq[len_] := Module[{s = {1}, k, d, i = 1}, While[Length[s] < len, k = s[[-1]]; If[MemberQ[s, (d = Plus @@ IntegerDigits[k])], AppendTo[s, k + i], AppendTo[s, d]]; i++]; s]; seq[50] (* Amiram Eldar, Oct 21 2021 *)

Cf. A007953, A348483, A348433.

nonn,base,new

Rodolfo Kurchan, Oct 21 2021

Definition clarified by Amiram Eldar, Oct 23 2021

approved

1,2

We know there are n ways to get n as a product of terms A307720(k)*A307720(k+1) for various k's. Look at these 2*n numbers from A307720. Then a(n) is the largest of them.

Table of n, a(n) for n=1..74.

Rémy Sigrist, C program for A348582

a(p) = p for any prime number p.

a(n) * A348581(n) = n.

For n = 6:

- we have the following products equal to 6:

    A307720(7)  * A307720(8)  = 3 * 2 = 6

    A307720(12) * A307720(13) = 2 * 3 = 6

    A307720(13) * A307720(14) = 3 * 2 = 6

    A307720(14) * A307720(15) = 2 * 3 = 6

    A307720(15) * A307720(16) = 3 * 2 = 6

    A307720(16) * A307720(17) = 2 * 3 = 6

- the corresponding distinct factors are 2 and 3,

- hence a(6) = 3.

(C) See Links section.

Cf. A307720, A307730, A348581.

nonn,new

Rémy Sigrist and N. J. A. Sloane, Oct 24 2021

approved

1,4

We know there are n ways to get n as a product of terms A307720(k)*A307720(k+1) for various k's. Look at these 2*n numbers from A307720. Then a(n) is the smallest of them.

Table of n, a(n) for n=1..87.

Rémy Sigrist, C program for A348581

a(p) = 1 for any prime number p.

a(n) * A348582(n) = n.

For n = 6:

- we have the following products equal to 6:

    A307720(7)  * A307720(8)  = 3 * 2 = 6

    A307720(12) * A307720(13) = 2 * 3 = 6

    A307720(13) * A307720(14) = 3 * 2 = 6

    A307720(14) * A307720(15) = 2 * 3 = 6

    A307720(15) * A307720(16) = 3 * 2 = 6

    A307720(16) * A307720(17) = 2 * 3 = 6

- the corresponding distinct factors are 2 and 3,

- hence a(6) = 2.

(C) See Links section.

Cf. A307720, A307730, A348582.

nonn,new

Rémy Sigrist and N. J. A. Sloane, Oct 24 2021

approved

1,2

Table of n, a(n) for n=1..66.

Rémy Sigrist, PARI program for A348579

Index entries for sequences that are permutations of the natural numbers

T(n, 1) = A348246(n).

T(n, n) = A348409(n).

Triangle T(n, k) begins:

  n\k|   1   2   3   4   5   6   7   8   9  10

  ---+----------------------------------------

    1|   1

    2|   2   3

    3|   4   5   6

    4|   8   9  10  11

    5|  47  48  49  50  51

    6|   7  12  13  14  15  16

    7|  52  53  54  55  56  57  58

    8|  27  28  29  30  31  32  33  34

    9|  17  18  19  20  21  22  23  24  25

   10|  60  61  62  63  64  65  66  67  68  69

(PARI) See Links section.

Cf. A307720, A307730, A348246, A348409.

nonn,tabl,new

Rémy Sigrist and N. J. A. Sloane, Oct 24 2021

approved