A084416 -id:A084416 - cp's OEIS frontend

A052875 E.g.f.: (exp(x)-1)^2/(2-exp(x)).

0, 0, 2, 12, 74, 540, 4682, 47292, 545834, 7087260, 102247562, 1622632572, 28091567594, 526858348380, 10641342970442, 230283190977852, 5315654681981354, 130370767029135900, 3385534663256845322, 92801587319328411132, 2677687796244384203114, 81124824998504073881820

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Previous name was: A simple grammar.
Stirling transform of A005359(n-1)=[0,0,2,0,24,0,...] is a(n-1)=[0,0,2,12,74,...]. - Michael Somos, Mar 04 2004
Stirling transform of -(-1)^n*A052566(n-1)=[1,-1,4,-6,48,...] is a(n-1)=[1,0,2,12,74,...]. - Michael Somos, Mar 04 2004
Stirling transform of A000142(n)=[0,2,6,24,120,...] is a(n)=[0,2,12,74,...]. - Michael Somos, Mar 04 2004
Stirling transform of A007680(n)=[2,10,42,216,...] is a(n+1)=[2,12,74,...]. - Michael Somos, Mar 04 2004
a(n) is the number of chains in the power set of {1,2,...,n} that do not contain the empty set and do not contain {1,2,...,n}.  Equivalently, a(n) is the number of ordered set partitions of {1,2,...,n} into at least 2 classes. - Geoffrey Critzer, Sep 01 2014

			a(3) = 12 because we have: {{1}}, {{2}}, {{3}}, {{1,2}}, {{1,3}}, {{2,3}}, {{1}, {1,2}}, {{1}, {1,3}}, {{2}, {1,2}}, {{2}, {2,3}}, {{3}, {1,3}}, {{3}, {2,3}}. - _Geoffrey Critzer_, Sep 01 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 846
R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1991), 23-31.
Wikipedia, Ordered Bell number

Cf. A007047, A038719.

spec := [S, {B = Set(Z, 1 <= card), C = Sequence(B, 1 <= card), S=Prod(B, C)}, labeled]: seq(combstruct[count](spec, size=n),  n=0..20);

CoefficientList[Series[(E^x-1)^2/(2-E^x), {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Feb 25 2014 *)

a(n)=if(n<0,0,n!*polcoeff(subst(y^2/(1-y),y,exp(x+x*O(x^n))-1),n))

def A052875(n):
    return add(add((-1)^(j-i)*binomial(j,i)*i^n for i in range(n+1)) for j in range(n+1)) - 1
[A052875(n) for n in range(19)] # Peter Luschny, Jul 22 2014

Second column of A084416: Sum_{i=2..n} i!*Stirling2(n, i) = A000670(n)-1. - Vladeta Jovovic, Sep 15 2003
E.g.f.: (exp(x)-1)^2/(2-exp(x)).
a(n) ~ n! / (2 * (log(2))^(n+1)). - Vaclav Kotesovec, Feb 25 2014
E.g.f.: A(x)*(1/(1 - A(x)) - 1) where A(x)=exp(x)-1. - Geoffrey Critzer, Sep 01 2014

New name using e.g.f., Vaclav Kotesovec, Feb 25 2014

A341091 Triangle read by rows: Coefficients for calculation of the sum of all the finite differences from order zero to order k. Sum_{n=0..k} T(n, k)*b(n) = b(0) + b(1) + ... + b(k) + (b(1) - b(0)) + ... + (b(k) - b(k-1)) + ((b(2) - b(1)) - (b(1) - b(0))) + ... .

Original entry on oeis.org

1, 0, 2, 1, -1, 3, 0, 3, -3, 4, 1, -2, 7, -6, 5, 0, 4, -8, 14, -10, 6, 1, -3, 13, -21, 25, -15, 7, 0, 5, -15, 35, -45, 41, -21, 8, 1, -4, 21, -49, 81, -85, 63, -28, 9, 0, 6, -24, 71, -129, 167, -147, 92, -36, 10, 1, -5, 31, -94, 201, -295, 315, -238, 129, -45, 11

Offset: 0

Thomas Scheuerle, Feb 13 2022

If we want to calculate the sum of finite differences for a sequence b(n):
  b(0)*T(0, n) + ... + b(n)*T(n, n) = b(0) + b(1) + ... + b(n) + (b(1) - b(0)) + ... + (b(n) - b(n-1)) + ((b(2) - b(1)) - (b(1) - b(0))) + ... This sum includes the sequence b(n) itself. This defines an invertible linear sequence transformation with a deep connection to Bernoulli numbers and other interesting sequences of rational numbers.
From Thomas Scheuerle, Apr 29 2024: (Start)
These are the coefficients of the polynomials defined by the recurrence: P(k, x) = P(k - 1, x) + (x^2 - x)*P(k - 2, x) + 1, with P(-1, x) = 0 and P(0, x) = 1. This can also be expressed as P(k, x) = Sum_{m=1..k+1} binomial(k+2 - m, m)*(x^2 - x)^(m - 1) = Sum_{n=0..k} T(n, k)*x^(k-n). If we would evaluate P(k, t) as sequence for some fixed t then we get the expansion of 1/((1 - x)*(1+(t-1)*x)*(1 - t*x)).
We may replace (x^2 - x) by (x^(-2) - x^(-1)) to get the coefficients in reverse order: x^k*Sum_{m=1..k+1} binomial(k+2 - m, m)*(x^(-2) - x^(-1))^(m - 1) = Sum_{n=0..k} T(n, k)*x^n = F(k, x). If we would evaluate F(k, t) as sequence for some fixed t then we get the expansion of 1/((1 - x)*(1 - (t-1)*x)*(1 - t*x)). (End)

			Triangle begins with T(n, k):
   n=   0,  1,   2,   3,   4,   5,   6,   7,   8
  k=0   1
  k=1   0,  2
  k=2   1, -1,   3
  k=3   0,  3,  -3,   4
  k=4   1, -2,   7,  -6,   5
  k=5   0,  4,  -8,  14, -10,   6
  k=6   1, -3,  13, -21,  25, -15,   7
  k=7   0,  5, -15,  35, -45,  41, -21,   8
  k=8   1, -4,  21, -49,  81, -85,  63, -28,   9
  ...

Cf. A000027, A000032, A000045, A000110, A000217.
Cf. A001045, A004006, A032346, A051744, A052875.
Cf. A084416, A130595, A145766.
Cf. A027642, A164555 (Numerators and denominators of Bernoulli numbers).
Cf. A001008, A002805 (Numerators and denominators of harmonic numbers).
Cf. A344037, A372245.
Sequences below will be obtained by evaluation of the associated polynomials:
Cf. A000295, A000392, A000975, A016208.
Cf. A016218, A016228, A016241, A016249.
Cf. A016256, A016261, A249997.

A341091(n, k) = sum(m=n, k,(-1)^(m+n)*binomial(m+1, n))

A341091(n, k) = (1/2)*(-1)^n*(2*(-1)^k*binomial(2+k, n)*hypergeom([1,k+3],k+3-n,-1)+(-1/2)^n*(2^(n+1)-1)) \\ Thomas Scheuerle, Apr 29 2024

b(0)*T(0, m) + b(1)*T(1, m) + ... + b(m)*T(m, m)
  = Sum_{j=0..m} Sum_{n=0..m-j} Sum_{k=0..n} (-1)^k*binomial(n, k)*b(j+n-k)
  = Sum_{n=0..m} b(n)*Sum_{j=n..m}(-1)^(j+n)*binomial(j+1, n).
T(n, k) = Sum_{m=n..k}(-1)^(m+n)*binomial(m+1, n).
T(n, k) = (1/2)*(-1)^n*(2*(-1)^k*binomial(2+k, n)*Hypergeometric2F1(1, k+3, k+3-n, -1)+(-1/2)^n*(2^(n+1) - 1)), where Hypergeometric2F1 is the Gaussian hypergeometric function 2F1 as defined in Mathematica. - Thomas Scheuerle, Apr 29 2024
T(k, k) = A000027(k+1) The positive integers.
|T(k-1, k)| = A000217(k) The triangular numbers.
T(k-2, k) = A004006(k).
|T(k-3, k)| = A051744(k).
T(0, k*2) = 1.
T(0, k*2 + 1) = 0.
T(1, k*2 + 1) = k + 2.
T(1, k*2 + 2) = -(k + 1).
T(n, k) with constant n and variable k, a linear recurrence relation with characteristic polynomial (x-1)*(x+1)^(n+1).
Sum_{n=0..k} T(n, k)*B_n = 1. B_n is the n-th Bernoulli number with B_1 = 1/2. B_n = A164555(n)/A027642(n).
Sum_{n=0..k} T(n, k)*(1 - B_n) = k.
Sum_{n=0..k} T(n, k)*(2*n - 3+3*B_n) = k^2.
Sum_{n=0..k} T(n, k)*A032346(n) = A032346(k+1).
From Thomas Scheuerle, Apr 29 2024: (Start)
Sum_{n=0..k} T(n, k)*A000110(n+1) = A000110(k+2) - 1.
Sum_{n=0..k} T(n, k)*(1/(1+n)) = H(1+floor(k/2)), where H(k) is the harmonic number A001008(k)/A002805(k). (End)
Sum_{n=0..k} T(n, k)*c(n) = c(k). C(k) = {-1, 0, 1/2, 1/2, 1/8, -7/20, ...} this sequence of rational numbers can be defined recursively: c(0) = -1, c(m) = (-c(m-1) + Sum_{k=0..m-1} A130595(m+1, k)*c(k))/m.
  c(m) is an eigensequence of this transformation, all eigensequences are c(m) multiplied by any factor.
Sum_{n=0..k} T(n, k)*A000045(n) = 2*(A000045(2*floor((k+1)/2) - 1) - 1). A000045 are the Fibonacci numbers.
Sum_{n=0..k} T(n, k)*A000032(n) = A000032(2*floor(k/2)+2) - 2. A000032 are the Lucas numbers.
Sum_{n=0..k} T(n, k)*A001045(n) = A145766(floor((k+1)/2)). A001045 is the Jacobsthal sequence.
This sequence acting as an operator onto a monomial n^w:
Sum_{n=0..k} T(n, k)*n^w = (1/(w+1))*k^(w+1) + Sum_{v=1..w} ((v+B_v)*(w)_v/v!)*k^(w+1-v) - A052875(w) + O_k(w) (w)_v is the falling factorial. If k > w-1 then O_k(w) = 0. If k <= w-1 then O_k(w) is A084416(w, 2+k), the sequence with the exponential generating function: (e^x-1)^(2+k)/(2-e^x).
From Thomas Scheuerle, Apr 29 2024: (Start)
This sequence acting by its inverse operator onto a monomial k^w:
Sum_{n=0..k} T(n, k)*( Sum_{m=0..k} ((-1)^(1+m+k)*binomial(k, m)*(2^(k-m) - 1)*n^m + A344037(m)*B_n) ) = k^w - A372245(w, k+3), note that A372245(w, k+3) = 0 if k+3 > w. B_n is the n-th Bernoulli number with B_1 = 1/2.
How this sequence will act as an operator onto a Dirichlet series may be developed by the formulas below:
Sum_{n=0..k} T(n, k)*2^n = A000295(k+2).
Sum_{n=0..k} T(n, k)*3^n = A000392(k+3).
Sum_{n=0..k} T(n, k)*4^n = A016208(k).
Sum_{n=0..k} T(n, k)*5^n = A016218(k).
Sum_{n=0..k} T(n, k)*6^n = A016228(k).
Sum_{n=0..k} T(n, k)*7^n = A016241(k).
Sum_{n=0..k} T(n, k)*8^n = A016249(k).
Sum_{n=0..k} T(n, k)*9^n = A016256(k).
Sum_{n=0..k} T(n, k)*10^n = A016261(k).
Sum_{n=0..k} T(n, k)*m^n = m^2*m^k/(m-1) - (m-1)^2*(m-1)^k/(m-2) + 1/((m-1)*(m-2)), for m > 2.
Sum_{n=0..k} T(n, k)*( m*B_n + (m-1)*Sum_{t=1..m} t^n )*(1/m^2) = m^k, for m > 0. B_n is the n-th Bernoulli number with B_1 = 1/2.
Sum_{n=0..k} T(n, k) zeta(-n) = Sum_{j=0..k} (-1)^(1+j)/(2+j) = (-1)^(k+1)*LerchPhi(-1, 1, k+3) - 1 + log(2).
Sum_{n=0..k} T(k - n, k)*2^n = A000975(k+1)
Sum_{n=0..k} T(k - n, k)*3^n = A091002(k+2)
Sum_{n=0..k} T(k - n, k)*4^n = A249997(k). (End)

A090665 Triangle read by rows: T(n,k) = number of preferential arrangements of n things where the first object has rank k.

Original entry on oeis.org

1, 2, 1, 6, 5, 2, 26, 25, 18, 6, 150, 149, 134, 84, 24, 1082, 1081, 1050, 870, 480, 120, 9366, 9365, 9302, 8700, 6600, 3240, 720, 94586, 94585, 94458, 92526, 82320, 57120, 25200, 5040, 1091670, 1091669, 1091414, 1085364, 1038744, 871920, 554400, 221760, 40320

Offset: 1

Eugene McDonnell (eemcd(AT)mac.com), Dec 16 2003

The rows are the reverses of the rows of A054255.
Row sums give A000670.
Column 1 is A000629. - Joerg Arndt, Dec 08 2014
From Vincent Jackson, May 01 2023: (Start)
The formula
  T(n, k) = Sum_{i=k..n-1} i!*StirlingS2(n-1, i) + (k-1)!*StirlingS2(n-1,k-1)
can be derived by splitting the weak orders with the first object at rank k into three categories:
1. weak orders where another object (of the n-1 other objects) has rank k,
2. weak orders where all other objects have rank strictly less than k, and
3. weak orders where no other object is at rank k, but some object has rank greater than k.
The number of weak orders in the first category is Sum_{i=k..n-1} i!*StirlingS2(n-1, i), the number of weak orders of length n-1 with number of ranks between k and n-1 (i.e. A084416(n-1,k)). Given a weak order of length n-1 and number of ranks i >= k, the corresponding weak order of length n with the specified object at rank k is formed by inserting the new object into the appropriate rank.
The number of weak orders in the second category is (k-1)!*StirlingS2(n-1,k-1), the number of weak orders of length n-1 with number of ranks k-1. Given a weak order of length n-1 and number of ranks k-1, the corresponding weak order is formed by appending the new object in its own rank.
Lastly, the number of weak orders in the third category is (again) Sum_{i=k..n-1} i!*StirlingS2(n-1, i). Given a weak order of length n-1 and number of ranks k-1, the corresponding weak order is formed by inserting the new object in its own rank after the rank k-1, thereby shifting by one the ranks originally greater than or equal to k. (End)

			Triangle starts:
01: 1;
02: 2, 1;
03: 6, 5, 2;
04: 26, 25, 18, 6;
05: 150, 149, 134, 84, 24;
06: 1082, 1081, 1050, 870, 480, 120;
07: 9366, 9365, 9302, 8700, 6600, 3240, 720;
08: 94586, 94585, 94458, 92526, 82320, 57120, 25200, 5040;
09: 1091670, 1091669, 1091414, 1085364, 1038744, 871920, 554400, 221760, 40320;
10: 14174522, 14174521, 14174010, 14155350, 13950720, 12930120, 10190880, 5957280, 2177280, 362880;
...

Cf. A054255, A008277, A028246, A083410.

T = {n, k} |-> 2*Sum[i!*StirlingS2[n-1, i], {i, k, n-1}] + (k-1)i!*StirlingS2[n-1, k-1]  (* Vincent Jackson, May 01 2023 *)

From Vincent Jackson, May 01 2023: (Start)
T(n, k) = 2*(Sum_{i=k..n-1} i!*StirlingS2(n-1, i)) + (k-1)!*StirlingS2(n-1,k-1).
T(n, k) = 2*A084416(n-1,k) + (k-1)!*StirlingS2(n-1,k-1).
T(n, k) = A084416(n-1,k) + A084416(n-1,k-1). (End)
Sum_{k=1..n} k * T(n,k) = A083410(n). - Alois P. Heinz, Feb 20 2025

Corrected by Alois P. Heinz, Dec 08 2014

Name clarified by Vincent Jackson, May 01 2023

A084417 Triangle read by rows: T(n,k)=sum((n+1-i)!*stirling2(n,n+1-i),i=1..k), n>=1, 1<=k<=n.

Original entry on oeis.org

1, 2, 3, 6, 12, 13, 24, 60, 74, 75, 120, 360, 510, 540, 541, 720, 2520, 4080, 4620, 4682, 4683, 5040, 20160, 36960, 45360, 47166, 47292, 47293, 40320, 181440, 372960, 498960, 539784, 545580, 545834, 545835, 362880, 1814400, 4142880, 6048000

Offset: 1

N. J. A. Sloane, Jun 24 2003

Interpolates between A000670 and factorials.

			1;2,3;6,12,13;24,60,74,75;120,360,510,540,541;

Mirror image of array in A084416.

T(n, 1)=n!=A000142(n), T(n, n)=A000670(n), T(n, n-1)=A052875(n).

with(combinat): T:=(n,k)->sum((n+1-i)!*stirling2(n,n+1-i),i=1..k): seq(seq(T(n,k),k=1..n),n=1..10);

T(n, k)=sum((n+1-i)!*stirling2(n, n+1-i), i=1..k), n>=1, 1<=k<=n.

Edited by Emeric Deutsch, May 11 2004

A372245 Triangular array T(n,k) read by rows: column k is the expansion of e.g.f: exp(-2x)(exp(x)-1)^k/(2-exp(x)).

Original entry on oeis.org

1, -1, 1, 3, -1, 2, -1, 7, 0, 6, 27, 11, 26, 12, 24, 119, 151, 120, 150, 120, 120, 1203, 1139, 1202, 1140, 1200, 1080, 720, 11759, 11887, 11760, 11886, 11760, 11760, 10080, 5040, 136587, 136331, 136586, 136332, 136584, 136080, 131040, 100800, 40320, 1771559, 1772071, 1771560, 1772070

Offset: 0

Thomas Scheuerle, Apr 26 2024

			Triangle T(n, k) starts:
[0]  1;
[1] -1,      1;
[2]  3,     -1,      2;
[3] -1,      7,      0,      6;
[4]  27,     11,     26,     12,     24;
[5]  119,    151,    120,    150,    120,    120;
[6]  1203,   1139,   1202,   1140,   1200,   1080,   720;
[7]  11759,  11887,  11760,  11886,  11760,  11760,  10080,  5040;
[8]  136587, 136331, 136586, 136332, 136584, 136080, 131040, 100800, 40320;

Cf. A000670, A052841, A084416, A341091, A344037.

T(n, k) = sum(m=0, n, ((-1)^((k > 0)+m+n)*binomial(n, m)*(2^(n-m)-(k > 0))*sum(h=max(k-1,0), m, h!*stirling(m, h, 2))))

T(n, k) = Sum_{m=0..n} ((-1)^(1+m+n)*binomial(k, n)*(2^(k - n) - 1)*A084416(m, k - 1)), for k > 0.
T(n, 0) = A344037(n).
T(n, 1) = A052841(n) - A344037(n).
T(n, 2) = A344037(n) - 2*A052841(n) + A000670(n).

cp's OEIS Frontend

A052875 E.g.f.: (exp(x)-1)^2/(2-exp(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A341091 Triangle read by rows: Coefficients for calculation of the sum of all the finite differences from order zero to order k. Sum_{n=0..k} T(n, k)*b(n) = b(0) + b(1) + ... + b(k) + (b(1) - b(0)) + ... + (b(k) - b(k-1)) + ((b(2) - b(1)) - (b(1) - b(0))) + ... .

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

Formula

A090665 Triangle read by rows: T(n,k) = number of preferential arrangements of n things where the first object has rank k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A084417 Triangle read by rows: T(n,k)=sum((n+1-i)!*stirling2(n,n+1-i),i=1..k), n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

A372245 Triangular array T(n,k) read by rows: column k is the expansion of e.g.f: exp(-2*x)*(exp(x)-1)^k/(2-exp(x)).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A372245 Triangular array T(n,k) read by rows: column k is the expansion of e.g.f: exp(-2x)(exp(x)-1)^k/(2-exp(x)).