A038720 -id:A038720 - cp's OEIS frontend

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

1, 1, 1, 1, 2, 2, 2, 3, 9, 9, 3, 8, 28, 48, 28, 8, 20, 90, 250, 250, 90, 20, 80, 360, 1200, 1760, 1200, 360, 80, 210, 1526, 5922, 12502, 12502, 5922, 1526, 210, 896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896, 3360, 32460, 185460, 576060, 1017060, 1017060, 576060, 185460, 32460, 3360

Offset: 0

Alois P. Heinz, Feb 08 2019

A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of permutations p of [n] having exactly k indices i in {1,...,n} such that p(i) > p(floor(i/2)).
T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
T(4,3) = 3: 1234, 1243, 1324.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    1;
    1;
    1,    1;
    2,    2,     2;
    3,    9,     9,     3;
    8,   28,    48,    28,      8;
   20,   90,   250,   250,     90,    20;
   80,  360,  1200,  1760,   1200,   360,    80;
  210, 1526,  5922, 12502,  12502,  5922,  1526,  210;
  896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;
  ...

Alois P. Heinz, Rows n = 0..190, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Columns k=0-10 give: A056971, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.
Row sums give A000142.
T(n,floor(n/2)) gives A306356.
Cf. A001286, A001710, A008292, A038720, A229039, A230056, A264902, A306393.

b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o)*x)
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = Module[{n = u + o, g, l},
     If[n == 0, 1, g := 2^Floor@Log[2, n]; l = Min[g-1, n-g/2]; Expand[
     Sum[Sum[ Binomial[j-1, i]* Binomial[n-j, l-i]*b[i, l-i]*
     b[j-1-i, n-l-j+i], {i, 0, Min[j-1, l]}], {j, 1, u}]+
     Sum[Sum[Binomial[j - 1, i]* Binomial[n-j, l-i]*b[l-i, i]*
     b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]*x]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 17 2021, after Alois P. Heinz *)

T(n,k) = T(n,n-1-k) for n > 0.
Sum_{k>=0} k * T(n,k) = A001286(n).
Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.
Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.
Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.
Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.

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.

Original entry on oeis.org

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

N. J. A. Sloane, May 02 2000

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

			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)

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

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.

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

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

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 *)

T(n,k)=sum(i=0,k,(-1)^(k-i)*binomial(k,i)*(2+i)^n)

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

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

A285793 Sum T(n,k) of the k-th entries in all cycles of all permutations of [n]; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 4, 2, 18, 13, 5, 96, 83, 43, 18, 600, 582, 342, 192, 84, 4320, 4554, 2874, 1824, 1068, 480, 35280, 39672, 26232, 17832, 11784, 7080, 3240, 322560, 382248, 261288, 185688, 131256, 88920, 54360, 25200, 3265920, 4044240, 2834640, 2078640, 1534320, 1110960, 765360, 473760, 221760

Offset: 1

Alois P. Heinz, Apr 26 2017

Each cycle is written with the smallest element first and cycles are arranged in increasing order of their first elements.

			T(3,2) = 13 because the sum of the second entries in all cycles of all permutations of [3] ((123), (132), (12)(3), (13)(2), (1)(23), (1)(2)(3)) is 2+3+2+3+3+0 = 13.
Triangle T(n,k) begins:
:      1;
:      4,      2;
:     18,     13,      5;
:     96,     83,     43,     18;
:    600,    582,    342,    192,     84;
:   4320,   4554,   2874,   1824,   1068,   480;
:  35280,  39672,  26232,  17832,  11784,  7080,  3240;
: 322560, 382248, 261288, 185688, 131256, 88920, 54360, 25200;

Wikipedia, Permutation

Columns k=1-2 give: A001563, A285795.
Main diagonal and first lower diagonal give: A038720(n-1) (for n>1), A286175.
Row sums give A000142 * A000217 = A180119.
Cf. A285439, A285595, A286231.

T(n,1) = n * n!.

T(n,n) = floor((n-1)!*(n+2)/2).

A052572 Expansion of e.g.f.: (1+2x-2x^2)/(1-x)^2.

Original entry on oeis.org

1, 4, 10, 36, 168, 960, 6480, 50400, 443520, 4354560, 47174400, 558835200, 7185024000, 99632332800, 1482030950400, 23538138624000, 397533007872000, 7113748561920000, 134449847820288000, 2676192208994304000

Offset: 0

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

a(n) equals the permanent of the (n+1) X (n+1) matrix whose entry directly below the entry in the top right corner is 3, and all of whose other entries are 1. - John M. Campbell, May 25 2011

In factorial base representation (A007623) the terms are written as: 1, 20, 120, 1200, 12000, 120000, ... From a(2) = 10 = "120" onward each term begins always with "120", followed by n-2 additional zeros. - Antti Karttunen, Sep 24 2016

G. C. Greubel, Table of n, a(n) for n = 0..440
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 515
Index entries for sequences related to factorial base representation

Essentially twice A038720.
Row 7 of A276955, from a(2)=10 onward.
Cf. sequences with formula (n + k)*n! listed in A282466.
Cf. A000142.

A052572:= func< n | n eq 0 select 1 else (n+3)*Factorial(n) >; // G. C. Greubel, May 11 2025

spec := [S,{S=Prod(Union(Z,Z,Sequence(Z)),Sequence(Z))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

With[{nn=20},CoefficientList[Series[(1+2x-2x^2)/(1-x)^2,{x,0,nn}],x] Range[ 0,nn]!] (* Harvey P. Dale, Jul 03 2020 *)
Table[If[n==0, 1, (n+3)*n!], {n,0,30}] (* G. C. Greubel, May 11 2025 *)

def A052572(n): return 1 if n==0 else (n+3)*factorial(n) # G. C. Greubel, May 11 2025

E.g.f.: (1 + 2*x - 2*x^2)/(1 - x)^2.
Recurrence: (n+2)*a(n) = n*(n+3)*a(n-1), with a(0) = 1, a(1) = 4, a(2) = 10.
a(n) = (n+3)*n! for n > 0.
For n <= 1, a(n) = (n+1)^2, for n > 1, a(n) = (n+1)! + 2*n! - Antti Karttunen, Sep 24 2016
From Amiram Eldar, Nov 06 2020: (Start)
Sum_{n>=0} 1/a(n) = e - 4/3.
Sum_{n>=0} (-1)^n/a(n) = 8/3 - 5/e. (End)

A144495 Row 2 of array in A144502.

Original entry on oeis.org

2, 7, 30, 155, 946, 6687, 53822, 486355, 4877250, 53759351, 646098622, 8409146187, 117836551730, 1768850337295, 28318532194206, 481652022466307, 8673291031865602, 164849403644999655, 3297954931572397790, 69274457019123638011, 1524368720086682440242

Offset: 0

David Applegate and N. J. A. Sloane, Dec 13 2008

nonn

Robert Israel, Table of n, a(n) for n = 0..447

Cf. A000522, A001339, A038720, A144496, A144497, A144498.

Cf. A144499, A144500, A144501, A144502, A144503.

A144495:= func< n | (&+[Binomial(n,k)*(k+4)*Factorial(k+1) : k in [0..n]])/2 >;
[A144495(n): n in [0..40]]; // G. C. Greubel, Oct 07 2023

f:= rectoproc({a(n)=((4+3*n)*a(n-1)-(n+3)*(n-1)*a(n-2)+(n-1)*(n-2)*a(n-3))/2,a(0)=2,a(1)=7,a(2)=30},a(n),remember):
map(f, [$0..40]); # Robert Israel, Oct 02 2016

(* First program *)
t[0, ] = 1; t[n, 0] := t[n, 0] = t[n-1, 1];
t[n_, k_] := t[n, k] = t[n-1, k+1] + k*t[n, k-1];
a[n_] := t[2, n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Aug 19 2022 *)
(* Second program *)
a[n_]:= a[n]= If[n==0, 2, (n*(n^2+3*n+1)*a[n-1] -(n+2))/(n^2+n-1)];
Table[a[n], {n,0,40}] (* G. C. Greubel, Oct 07 2023 *)

def A144495(n): return sum(binomial(n,j)*factorial(j+1)*(j+4) for j in range(n+1))/2
[A144495(n) for n in range(41)] # G. C. Greubel, Oct 07 2023

E.g.f.: exp(x)*(2-x)/(1-x)^3.
a(n) = (1/2) * (floor((n+1)*(n+1)!*e) + floor(n*n!*e)). [Gary Detlefs, Jun 06 2010]
a(n) = (1/2) * ( A001339(n) + A001339(n+1) ). [Gary Detlefs, Jun 06 2010]
a(n) = (1/2) * (3 + n + (1 + 3*n + n^2) * A000522(n)). - Gerry Martens, Oct 02 2016
a(n) = ((4+3*n)*a(n-1) - (n+3)*(n-1)*a(n-2) + (n-1)*(n-2)*a(n-3))/2. - Robert Israel, Oct 02 2016
From Peter Bala, May 27 2022: (Start)
a(n) = (1/2)*(A000522(n+2) - A000522(n)).
a(n) = (1/2)*Sum_{k = 0..n} binomial(n,k)*(k+4)*(k+1)!; binomial transform of A038720(n+1).
a(n) = (1/2)*e*Integral_{x >= 1} x^n*(x^2 - 1)*exp(-x).
a(2*n) is even and a(2*n+1) is odd. More generally, a(n+k) == a(n) (mod k) for all n and k. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with the exact period dividing k. Various divisibility properties of the sequence follow from this; for example, a(3*n+2) == 0 (mod 3), a(5*n+2) == a(5*n+3) (mod 5), a(7*n+1) == 0 (mod 7) and a(11*n+4) == 0 (mod 11). (End)
a(n) = (n*(n^2 + 3*n + 1)*a(n-1) - (n + 2))/(n^2 + n - 1), with a(0) = 2. - G. C. Greubel, Oct 07 2023

A229039 G.f.: Sum_{n>=0} (n+2)^n * x^n / (1 + (n+2)*x)^n.

Original entry on oeis.org

1, 3, 7, 24, 108, 600, 3960, 30240, 262080, 2540160, 27216000, 319334400, 4071513600, 56043187200, 828193766400, 13076743680000, 219689293824000, 3912561709056000, 73627297615872000, 1459741204905984000, 30411275102208000000, 664182248232222720000

Offset: 0

Paul D. Hanna, Sep 11 2013

nonn

More generally, we have the identity:
if Sum_{n>=0} a(n)*x^n = Sum_{n>=0} (b*n+c)^n * x^n / (1 + (b*n+c)*x)^n,
then Sum_{n>=0} a(n)*x^n/n! = (2 - 2*(b-c)*x + b*(b-2*c)*x^2)/(2*(1-b*x)^2)
so that a(n) = (b*n + (b+2*c)) * b^(n-1) * n!/2 for n>0 with a(0)=1.

			O.g.f.: A(x) = 1 + 3*x + 7*x^2 + 24*x^3 + 108*x^4 + 600*x^5 + 3960*x^6 +...
where
A(x) = 1 + 3*x/(1+3*x) + 4^2*x^2/(1+4*x)^2 + 5^3*x^3/(1+5*x)^3 + 6^4*x^4/(1+6*x)^4 + 7^5*x^5/(1+7*x)^5 +...
E.g.f.: E(x) = 1 + 3*x + 7*x^2/2! + 24*x^3/3! + 108*x^4/4! + 600*x^5/5! +...
where
E(x) = 1 + 3*x + 7/2*x^2 + 4*x^3 + 9/2*x^4 + 5*x^5 + 11/2*x^6 + 6*x^7 +...
which is the expansion of: (2 + 2*x - 3*x^2) / (2 - 4*x + 2*x^2).

Cf. A038720, A230056, A187735, A187738, A187739, A229039, A221160, A221161, A187740.

a[n_] := (n + 5)*n!/2; a[0] = 1; Array[a, 20, 0] (* Amiram Eldar, Dec 11 2022 *)

{a(n)=polcoeff( sum(m=0, n, ((m+2)*x)^m / (1 + (m+2)*x +x*O(x^n))^m), n)}
for(n=0, 20, print1(a(n), ", "))

{a(n)=if(n==0,1, (n+5) * n!/2 )}
for(n=0, 20, print1(a(n), ", "))

a(n) = (n+5) * n!/2 for n>0 with a(0)=1.
E.g.f.: (2 + 2*x - 3*x^2)/(2*(1-x)^2).
From Amiram Eldar, Dec 11 2022: (Start)
Sum_{n>=0} 1/a(n) = 18*e - 237/5.
Sum_{n>=0} (-1)^n/a(n) = 243/5 - 130/e. (End)

A038721 k=2 column of A038719.

Original entry on oeis.org

2, 18, 110, 570, 2702, 12138, 52670, 223290, 931502, 3842058, 15718430, 63928410, 258885902, 1045076778, 4208939390, 16921719930, 67944897902, 272553908298, 1092539107550, 4377127901850, 17529428119502, 70180466208618, 280910134414910, 1124205363178170, 4498515962822702

Offset: 1

N. J. A. Sloane, May 02 2000

For n>=1, a(n) is equal to the number of functions f: {1,2,...,n+1}->{1,2,3,4} such that Im(f) contains 2 fixed elements. - Aleksandar M. Janjic and Milan Janjic, Feb 27 2007
Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if x is not a subset of y and y is not a subset of x. Then a(n+1) = |R|. - Ross La Haye, Mar 19 2009
Number of ordered (n+1)-tuples of positive integers, whose minimum is 0 and maximum 3. - Ovidiu Bagdasar, Sep 19 2014
a(n-2) is the number of possible player-reduced binary games observed by each player in an n X 2 game assuming k < n - 1 players reverse their initially fixed individual strategies and the remaining n - k - 1 players will play as one, either maintaining their status quo strategies or jointly adopting an alternative strategy. - Ambrosio Valencia-Romero, Apr 11 2024

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
O. Bagdasar, On Some Functions Involving the lcm and gcd of Integer Tuples, Scientific publications of the state university of Novi Pazar, Ser. A: Appl. Maths. Inform. and Mech., Vol. 6, 2 (2014), 91-100.
K. S. Immink, Coding Schemes for Multi-Level Channels that are Intrinsically Resistant Against Unknown Gain and/or Offset Using Reference Symbols, Electronics Letters, Volume50, Issue1, January 2014, pp. 20-22.
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
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.
Ambrosio Valencia-Romero and P. T. Grogan, The strategy dynamics of collective systems: Underlying hindrances beyond two-actor coordination, PLOS ONE 19(4): e0301394 (S1 Appendix).
Index entries for sequences related to posets
Index entries for linear recurrences with constant coefficients, signature (9,-26,24).

Cf. A016269, A038719, A038720.

import Data.List (transpose)
a038721 n = a038721_list !! (n-1)
a038721_list = (transpose a038719_tabl) !! 2
-- Reinhard Zumkeller, Jul 08 2012

Table[4^n-2*3^n+2^n,{n,2,30}] (* or *) LinearRecurrence[{9,-26,24},{2,18,110},30] (* Harvey P. Dale, Aug 16 2012 *)

a(n) = 4^(n+1) - 2*3^(n+1) + 2^(n+1).
a(1)=2, a(2)=18, a(3)=110, a(n)=9*a(n-1)-26*a(n-2)+24*a(n-3). - Harvey P. Dale, Aug 16 2012
G.f.: -2*x/((2*x-1)*(3*x-1)*(4*x-1)). - Colin Barker, Nov 27 2012
E.g.f.: 2*exp(2*x)*(1 - 3*exp(x) + 2*exp(2*x)). - Stefano Spezia, Jun 04 2024
a(n) = 2 * A016269(n-1). - Alois P. Heinz, Jun 04 2024

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

A319495 Number T(n,k) of multisets of nonempty words with a total of n letters over k-ary alphabet such that for k>0 the k-th letter occurs at least once and within each word every letter of the alphabet is at least as frequent as the subsequent alphabet letter; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 2, 0, 3, 5, 6, 0, 5, 20, 18, 24, 0, 7, 46, 86, 84, 120, 0, 11, 137, 347, 456, 480, 720, 0, 15, 313, 1216, 2136, 2940, 3240, 5040, 0, 22, 836, 4253, 11128, 15300, 22200, 25200, 40320, 0, 30, 1908, 15410, 44308, 90024, 127680, 191520, 221760, 362880

Offset: 0

Alois P. Heinz, Sep 20 2018

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k <= n. T(n,k) = 0 for k > n.

			T(3,1) = 3: {aaa}, {aa,a}, {a,a,a}.
T(3,2) = 5: {aab}, {aba}, {baa}, {ab,a}, {ba,a}.
T(3,3) = 6: {abc}, {acb}, {bac}, {bca}, {cab}, {cba}.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  2,   2;
  0,  3,   5,    6;
  0,  5,  20,   18,    24;
  0,  7,  46,   86,    84,   120;
  0, 11, 137,  347,   456,   480,   720;
  0, 15, 313, 1216,  2136,  2940,  3240,  5040;
  0, 22, 836, 4253, 11128, 15300, 22200, 25200, 40320;
  ...

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

Columns k=0-1 give: A000007, A000041 (for n>0).
Row sums give A292713.
Main diagonal gives A000142.
First lower diagonal gives A038720.
Cf. A292712, A319498.

b:= proc(n, i, t) option remember; `if`(t=1, 1/n!,
      add(b(n-j, j, t-1)/j!, j=i..n/t))
    end:
g:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), n!*b(n, 0, k)):
A:= proc(n, k) option remember; `if`(n=0, 1, add(add(d*
      g(d, k), d=numtheory[divisors](j))*A(n-j, k), j=1..n)/n)
    end:
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

b[n_, i_, t_] := b[n, i, t] = If[t == 1, 1/n!,
     Sum[b[n - j, j, t - 1]/j!, {j, i, n/t}]];
g[n_, k_] := If[k == 0, If[n == 0, 1, 0], n!*b[n, 0, k]];
A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[Sum[d*
     g[d, k], {d, Divisors[j]}]*A[n - j, k], {j, 1, n}]/n];
T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k - 1]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 09 2021, after Alois P. Heinz *)

T(n,k) = A292712(n,k) - A292712(n,k-1) for k > 0, T(n,0) = A000007(n).

A319498 Number T(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet such that for k>0 the k-th letter occurs at least once and within each word every letter of the alphabet is at least as frequent as the subsequent alphabet letter; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 2, 5, 6, 0, 2, 16, 18, 24, 0, 3, 39, 80, 84, 120, 0, 4, 106, 323, 432, 480, 720, 0, 5, 245, 1106, 2052, 2820, 3240, 5040, 0, 6, 621, 3822, 10576, 14820, 21480, 25200, 40320, 0, 8, 1431, 13840, 41896, 86724, 124440, 186480, 221760, 362880

Offset: 0

Alois P. Heinz, Sep 20 2018

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k <= n. T(n,k) = 0 for k > n.

			T(3,1) = 2: {aaa}, {aa,a}.
T(3,2) = 5: {aab}, {aba}, {baa}, {ab,a}, {ba,a}.
T(3,3) = 6: {abc}, {acb}, {bac}, {bca}, {cab}, {cba}.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,    2;
  0, 2,    5,     6;
  0, 2,   16,    18,    24;
  0, 3,   39,    80,    84,   120;
  0, 4,  106,   323,   432,   480,    720;
  0, 5,  245,  1106,  2052,  2820,   3240,   5040;
  0, 6,  621,  3822, 10576, 14820,  21480,  25200,  40320;
  ...

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

Columns k=0-1 give: A000007, A000009 (for n>0).
Row sums give A292796.
Main diagonal gives A000142.
First lower diagonal gives A038720 (for n>1).
Cf. A292795, A319495.

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

b[n_, i_, t_] := b[n, i, t] = If[t == 1, 1/n!,
     Sum[b[n - j, j, t - 1]/j!, {j, i, n/t}]];
g[n_, k_] := If[k == 0, If[n == 0, 1, 0], n!*b[n, 0, k]];
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[g[i, k], j], {j, 0, n/i}]]];
T[n_, k_] := h[n, n, k] - If[k == 0, 0, h[n, n, k - 1]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 09 2021, after Alois P. Heinz *)

T(n,k) = A292795(n,k) - A292795(n,k-1) for k > 0, T(n,0) = A000007(n).

A369596 Number T(n,k) of permutations of [n] whose fixed points sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 2, 1, 1, 1, 0, 0, 1, 9, 2, 2, 3, 3, 2, 1, 1, 0, 0, 1, 44, 9, 9, 11, 11, 13, 5, 5, 4, 4, 2, 1, 1, 0, 0, 1, 265, 44, 44, 53, 53, 62, 64, 29, 22, 24, 16, 16, 8, 6, 5, 4, 2, 1, 1, 0, 0, 1, 1854, 265, 265, 309, 309, 353, 362, 406, 150, 159, 126, 126, 93, 86, 44, 36, 29, 19, 19, 9, 7, 5, 4, 2, 1, 1, 0, 0, 1

Offset: 0

Alois P. Heinz, Mar 02 2024

			T(3,0) = 2: 231, 312.
T(3,1) = 1: 132.
T(3,2) = 1: 321.
T(3,3) = 1: 213.
T(3,6) = 1: 123.
T(4,0) = 9: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
Triangle T(n,k) begins:
   1;
   0, 1;
   1, 0, 0,  1;
   2, 1, 1,  1,  0,  0, 1;
   9, 2, 2,  3,  3,  2, 1, 1, 0, 0, 1;
  44, 9, 9, 11, 11, 13, 5, 5, 4, 4, 2, 1, 1, 0, 0, 1;
  ...

Alois P. Heinz, Rows n = 0..50, flattened
Wikipedia, Permutation

Column k=0 gives A000166.
Column k=3 gives A000255(n-2) for n>=2.
Row sums give A000142.
Row lengths give A000124.
Reversed rows converge to A331518.
T(n,n) gives A369796.
Cf. A000217, A001710, A008289, A008290, A038720, A053632, A062869, A124327, A143946, A143947, A161680, A263753, A263756, A317527, A367955, A368338.

b:= proc(s) option remember; (n-> `if`(n=0, 1, add(expand(
      `if`(j=n, x^j, 1)*b(s minus {j})), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n})):
seq(T(n), n=0..7);
# second Maple program:
g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
T:= (n, k)-> b(k, min(n, k), n):
seq(seq(T(n, k), k=0..n*(n+1)/2), n=0..7);

g[n_] := g[n] = If[n == 0, 1, n*g[n - 1] + (-1)^n];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0,
   If[n == 0, g[m], b[n, i-1, m] + b[n-i, Min[n-i, i-1], m-1]]];
T[n_, k_] := b[k, Min[n, k], n];
Table[Table[T[n, k], {k, 0, n*(n + 1)/2}], {n, 0, 7}] // Flatten (* Jean-François Alcover, May 24 2024, after Alois P. Heinz *)

Sum_{k=0..A000217(n)} k * T(n,k) = A001710(n+1) for n >= 1.
Sum_{k=0..A000217(n)} (1+k) * T(n,k) = A038720(n) for n >= 1.
Sum_{k=0..A000217(n)} (n*(n+1)/2-k) * T(n,k) = A317527(n+1).
T(n,A161680(n)) = A331518(n).
T(n,A000217(n)) = 1.

cp's OEIS Frontend

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A285793 Sum T(n,k) of the k-th entries in all cycles of all permutations of [n]; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A052572 Expansion of e.g.f.: (1+2*x-2*x^2)/(1-x)^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A144495 Row 2 of array in A144502.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A229039 G.f.: Sum_{n>=0} (n+2)^n * x^n / (1 + (n+2)*x)^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A038721 k=2 column of A038719.

Views

Author

Keywords

Comments

Links

A052572 Expansion of e.g.f.: (1+2x-2x^2)/(1-x)^2.