A038719 Triangle T(n,k) (0 <= k <= n) giving number of chains of length k in partially ordered set formed from subsets of n-set by inclusion.

1, 2, 1, 4, 5, 2, 8, 19, 18, 6, 16, 65, 110, 84, 24, 32, 211, 570, 750, 480, 120, 64, 665, 2702, 5460, 5880, 3240, 720, 128, 2059, 12138, 35406, 57120, 52080, 25200, 5040, 256, 6305, 52670, 213444, 484344, 650160, 514080, 221760, 40320, 512, 19171

Offset

0,2

Comments

The relation of this triangle to A143494 given in the Formula section leads to the following combinatorial interpretation: T(n,k) gives the number of partitions of the set {1,2,...,n+2} into k + 2 blocks where 1 and 2 belong to two distinct blocks and the remaining k blocks are labeled from a fixed set of k labels. - Peter Bala, Jul 10 2014

Also, the number of distinct k-level fuzzy subsets of a set consisting of n elements ordered by set inclusion. - Rajesh Kumar Mohapatra, Mar 16 2020

Links

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

Peter Bala, Deformations of the Hadamard product of power series

L. Bartlomiejczyk and J. Drewniak, A characterization of sets and operations invariant under bijections, Aequationes Mathematicae 68 (2004), pp. 1-9.

M. Dukes and C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.

Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.

R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1991), 23-31.

Index entries for sequences related to posets

Formula

T(n, k) = Sum_{j=0..k} (-1)^j*C(k, j)*(k+2-j)^n.

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

E.g.f.: exp(2*x)/(1+y*(1-exp(x))). - Vladeta Jovovic, Jul 21 2003

A038719 as a lower triangular matrix is the binomial transform of A028246. - Gary W. Adamson, May 15 2005

Binomial transform of n-th row = 2^n + 3^n + 4^n + ...; e.g., binomial transform of [8, 19, 18, 6] = 2^3 + 3^3 + 4^3 + 5^3 + ... = 8, 27, 64, 125, ... - Gary W. Adamson, May 15 2005

From Peter Bala, Jul 09 2014: (Start)

T(n,k) = k!*( Stirling2(n+2,k+2) - Stirling2(n+1,k+2) ).

T(n,k) = k!*A143494(n+2,k+2).

n-th row polynomial = 1/(1 + x)*( sum {k >= 0} (k + 2)^n*(x/(1 + x))^k ). Cf. A028246. (End)

The row polynomials have the form (2 + x) o (2 + x) o ... o (2 + x), where o denotes the black diamond multiplication operator of Dukes and White. See example E12 in the Bala link. - Peter Bala, Jan 18 2018

Z(P,m) = Sum_{k=0..n} T(n,k)Binomial(m-2,k) = m^n, the zeta polynomial of the poset B_n. Each length m multichain from 0 to 1 in B_n corresponds to a function from [n] into [m]. - Geoffrey Critzer, Dec 25 2020

The entries in row n are the first terms in a table of the successive differences of the sequence [2^n, 3^n, 4^n, ...]. Examples are given below. - Peter Bala, Feb 02 2022

Example

Triangle begins
   1;
   2,   1;
   4,   5,   2;
   8,  19,  18,   6;
  16,  65, 110,  84,  24;
  ...
From Peter Bala, Feb 02 2022: (Start)
Table of successive differences of k^2 starting at k = 2
4   9   16
  5   7
    2
gives [4, 5, 2] as row 2 of this triangle.
Table of successive differences of k^3 starting at k = 2
8   27   64   125
  19   37   61
     18   24
        6
gives [8, 19, 8, 6] as row 3 of this triangle. (End)

Maple

T:= proc(n, k) option remember;
      `if` (n=0, `if`(k=0, 1, 0), k*T(n-1, k-1) +(k+2)*T(n-1, k))
    end:
seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Aug 02 2011

Mathematica

t[n_, k_] := Sum[ (-1)^(k-i)*Binomial[k, i]*(2+i)^n, {i, 0, k}]; Flatten[ Table[ t[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, after Pari *)

Prog

(PARI) T(n, k)=sum(i=0, k, (-1)^(k-i)*binomial(k, i)*(2+i)^n)
(Haskell)
a038719 n k = a038719_tabl !! n !! k
a038719_row n = a038719_tabl !! n
a038719_tabl = iterate f [1] where
   f row = zipWith (+) (zipWith (*) [0..] $ [0] ++ row)
                       (zipWith (*) [2..] $ row ++ [0])
-- Reinhard Zumkeller, Jul 08 2012

Crossrefs

Row sums give A007047. Columns give A000079, A001047, A038721. Next-to-last diagonal gives A038720.

Diagonal gives A000142. - Rajesh Kumar Mohapatra, Mar 16 2020

Cf. A028246. A019538, A143494.

Sequence in context: A144332 A209153 A209141 * A125751 A210860 A099492

Adjacent sequences: A038716 A038717 A038718 * A038720 A038721 A038722

Keyword

nonn,easy,nice,tabl

Author

N. J. A. Sloane, May 02 2000

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), May 09 2000

Status

approved