A003056 -id:A003056 - cp's OEIS frontend

A373118 Number T(n,k) of compositions of n such that the set of parts is [k]; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 3, 0, 1, 7, 0, 1, 11, 6, 0, 1, 20, 12, 0, 1, 32, 32, 0, 1, 54, 72, 0, 1, 87, 152, 24, 0, 1, 143, 311, 60, 0, 1, 231, 625, 180, 0, 1, 376, 1225, 450, 0, 1, 608, 2378, 1116, 0, 1, 986, 4566, 2544, 120, 0, 1, 1595, 8700, 5752, 360

Offset: 0

Alois P. Heinz, May 25 2024

			T(6,2) = 11: 1122, 1212, 1221, 2112, 2121, 2211, 11112, 11121, 11211, 12111, 21111.
T(7,3) = 12: 1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1;
  0, 1,   2;
  0, 1,   3;
  0, 1,   7;
  0, 1,  11,    6;
  0, 1,  20,   12;
  0, 1,  32,   32;
  0, 1,  54,   72;
  0, 1,  87,  152,   24;
  0, 1, 143,  311,   60;
  0, 1, 231,  625,  180;
  0, 1, 376, 1225,  450;
  0, 1, 608, 2378, 1116;
  0, 1, 986, 4566, 2544, 120;
  ...

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

Columns k=0-3 give: A000007, A057427, A245738, A372702.
Row sums give A107429.
Cf. A000124, A000142, A000217, A000290, A001710, A003056, A008289, A332721, A371417, A373305, A373306.

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, t!, 0),
     `if`(i<1 or n b(n, k, 0):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..18);

T(A000217(n),n) = n! = A000142(n).
T(A000124(n),n) = A001710(n+1) for n>=1.
T(A000290(n),n) = T(n^2,n) = A332721(n).
G.f. for column k: C({1..k},x) where C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/ (1 - Sum_{i in {s}} (x^i)) with C({},x) = 1. - John Tyler Rascoe, May 25 2024

A327803 Sum T(n,k) of multinomials M(n; lambda), where lambda ranges over all partitions of n into parts that form a set of size k; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 3, 0, 7, 3, 0, 31, 16, 0, 121, 125, 0, 831, 711, 60, 0, 5041, 5915, 525, 0, 42911, 46264, 6328, 0, 364561, 438681, 67788, 0, 3742453, 4371085, 753420, 12600, 0, 39916801, 49321745, 8924685, 166320, 0, 486891175, 588219523, 113501784, 2966040

Offset: 0

Alois P. Heinz, Sep 25 2019

			Triangle T(n,k) begins:
  1;
  0,       1;
  0,       3;
  0,       7,       3;
  0,      31,      16;
  0,     121,     125;
  0,     831,     711,     60;
  0,    5041,    5915,    525;
  0,   42911,   46264,   6328;
  0,  364561,  438681,  67788;
  0, 3742453, 4371085, 753420, 12600;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Wikipedia, Multinomial coefficients
Wikipedia, Partition (number theory)

Columns k=0-2 give: A000007, A061095, A327826.
Row sums give A005651.
Cf. A000217, A003056, A022915, A131632 (when the parts are distinct), A226874.

with(combinat):
T:= (n, k)-> add(multinomial(add(i, i=l), l[], 0), l=
             select(x-> nops({x[]})=k, partition(n))):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..14);
# second Maple program:
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
      `if`(i<1, 0, add(x^signum(j)*b(n-i*j, i-1)*
      combinat[multinomial](n, n-i*j, i$j), j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2)):
seq(T(n), n=0..14);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = Expand[If[n == 0, 1, If[i<1, 0, Sum[x^Sign[j]*b[n - i*j, i-1]*multinomial[n, Join[{n-i*j}, Table[i, {j}]]], {j, 0, n/i}]]]];
T[n_] := CoefficientList[b[n, n], x];
T /@ Range[0, 14] // Flatten (* Jean-François Alcover, May 06 2020, after 2nd Maple program *)

T(n*(n+1)/2,n) = T(A000217(n),n) = A022915(n).

A291960 Triangle read by rows: T(n,k) = T(n-k,k-1) + k * T(n-k,k) with T(0,0) = 1 for 0 <= k <= A003056(n).

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 3, 0, 1, 3, 1, 0, 1, 7, 1, 0, 1, 7, 3, 0, 1, 15, 6, 0, 1, 15, 10, 1, 0, 1, 31, 16, 1, 0, 1, 31, 33, 3, 0, 1, 63, 45, 6, 0, 1, 63, 79, 14, 0, 1, 127, 130, 20, 1, 0, 1, 127, 198, 45, 1, 0, 1, 255, 300, 69, 3, 0, 1, 255, 517, 135

Offset: 0

Seiichi Manyama, Sep 06 2017

			First few rows are:
  1;
  0, 1;
  0, 1;
  0, 1,  1;
  0, 1,  1;
  0, 1,  3;
  0, 1,  3,  1;
  0, 1,  7,  1;
  0, 1,  7,  3;
  0, 1, 15,  6;
  0, 1, 15, 10, 1.

Seiichi Manyama, Rows n = 0..481, flattened

Row sums give A204856.
Columns 0-2 give A000007, A000012, A052551(n-3).
Cf. A008289, A216652, A291969.

G.f. of column k: x^(k*(k+1)/2) / Product_{j=1..k} (1-j*x^j).

A116941 Permutation of the natural numbers in conjunction with A116939 and A003056.

Original entry on oeis.org

0, 1, 3, 2, 4, 6, 5, 7, 9, 11, 8, 10, 12, 14, 16, 13, 15, 17, 19, 21, 23, 18, 20, 22, 24, 26, 28, 30, 25, 27, 29, 31, 33, 35, 37, 39, 32, 34, 36, 38, 40, 42, 44, 46, 48, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 61, 63, 65, 67, 69, 71, 73

Offset: 0

Reinhard Zumkeller, Feb 27 2006

nonn

Inverse: A116942;

A003056(n) = A116939(a(n)).

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for sequences that are permutations of the natural numbers

a116941 n = a116941_list !! n
a116941_list = f 0 1 (zip a116939_list [0..]) [] where
   f u v xis'@((x,i):xis) ws
     | x == u    = i : f u v xis ws
     | x == v    = f u v xis (i : ws)
     | otherwise = reverse ws ++ f v x xis' []
-- Reinhard Zumkeller, Jun 28 2013

Table[ Ceiling[(n -1)^2/2] + 2k -2, {n, 12}, {k, n}] // Flatten (* Robert G. Wilson v, Mar 09 2017 after Ivan Neretin in A074147 *)

a(n) = A074147(n+1) - 1. - Robert G. Wilson v, Mar 09 2017

A121430 Number of subpartitions of partition P=[0,1,1,2,2,2,3,3,3,3,4,...] (A003056).

Original entry on oeis.org

1, 1, 2, 3, 7, 12, 18, 43, 76, 118, 170, 403, 711, 1107, 1605, 2220, 5188, 9054, 13986, 20171, 27816, 37149, 85569, 147471, 225363, 322075, 440785, 585046, 758814, 1725291, 2938176, 4441557, 6285390, 8526057, 11226958, 14459138, 18301950

Offset: 0

Paul D. Hanna, Jul 30 2006

nonn

See A115728 for the definition of subpartitions of a partition.

			The g.f. is illustrated by:
1 = (1)*(1-x)^1 + (x + 2*x^2)*(1-x)^2 +
(3*x^3 + 7*x^5 + 12*x^6)*(1-x)^3 +
(18*x^6 + 43*x^7 + 76*x^8 + 118*x^9)*(1-x)^4 +
(170*x^10 + 403*x^11 + 711*x^12 + 1107*x^13 + 1605*x^14)*(1-x)^5 + ...
When the sequence is put in the form of a triangle:
1;
1, 2;
3, 7, 12;
18, 43, 76, 118;
170, 403, 711, 1107, 1605;
2220, 5188, 9054, 13986, 20171, 27816;
37149, 85569, 147471, 225363, 322075, 440785, 585046; ...
then the columns of this triangle form column 0 (with offset)
of successive matrix powers of triangle H=A121412.
This sequence is embedded in table A121424 as follows.
Column 0 of successive powers of matrix H begin:
H^1: [1,1,3,18,170,2220,37149,758814,18301950,...];
H^2: 1, [2,7,43,403,5188,85569,1725291,41145705,...];
H^3: 1,3, [12,76,711,9054,147471,2938176,69328365,...];
H^4: 1,4,18, [118,1107,13986,225363,4441557,103755660,...];
H^5: 1,5,25,170, [1605,20171,322075,6285390,145453290,...];
H^6: 1,6,33,233,2220, [27816,440785,8526057,195579123,...];
H^7: 1,7,42,308,2968,37149, [585046,11226958,255436293,...];
H^8: 1,8,52,396,3866,48420,758814, [14459138,326487241,...];
H^9: 1,9,63,498,4932,61902,966477,18301950, [410368743,...];
the terms enclosed in brackets form this sequence.

Cf. A121412 (triangle H), A121416 (H^2), A121420 (H^3); A121424, A121425; column 0 of H^n: A121413, A121417, A121421.

{a(n)=local(A); if(n==0,1,A=x+x*O(x^n); for(k=0, n, A+=polcoeff(A, k)*x^k*(1-(1-x)^( (sqrtint(8*k+1)+1)\2 ) )); polcoeff(A, n))}

G.f.: 1 = Sum_{n>=1} (1-x)^n * Sum_{k=n*(n-1)/2..n*(n+1)/2-1} a(k)*x^k.

A291904 Triangle read by rows: T(n,k) = T(n-k,k-1) + T(n-k,k+1) with T(0,0) = 1 for 0 <= k <= A003056(n).

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 2, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 3, 2, 0, 0, 3, 2, 1, 1, 1, 0, 2, 3, 2, 1, 0, 0, 3, 4, 3, 1, 0, 0, 4, 4, 3, 2, 1, 0, 4, 6, 4, 2, 0, 0, 6, 7

Offset: 0

Seiichi Manyama, Sep 05 2017

T(n,k) is the number of integer compositions of n with first part 1, last part k, and all adjacent differences in {-1,1}. - John Tyler Rascoe, Aug 14 2023

			First few rows are:
  1;
  0, 1;
  0, 0;
  0, 0, 1;
  0, 1, 0;
  0, 0, 0;
  0, 0, 1, 1;
  0, 1, 0, 0;
  0, 0, 1, 0;
  0, 1, 1, 1;
  0, 1, 0, 0, 1;
  0, 0, 2, 1, 0;
  0, 2, 1, 1, 0.

Seiichi Manyama, Rows n = 0..481, flattened

Row sums give A291905.
Columns 0-1 give A000007, A227310 (for n>0).
Cf. A008289, A173258, A291895, A291929.

T[0, 0] = 1; T[, 0] = 0; T[n?Positive, k_] /; 0 < k <= Floor[(Sqrt[8n+1] - 1)/2] := T[n, k] = T[n-k, k-1] + T[n-k, k+1]; T[, ] = 0;
Table[T[n, k], {n, 0, 20}, {k, 0, Floor[(Sqrt[8n+1] - 1)/2]}] // Flatten (* Jean-François Alcover, May 29 2019 *)

From John Tyler Rascoe, Aug 14 2023: (Start)
This triangle is T_1(n,k) of the general triangle T_m(n,k) for compositions of this kind with first part m.
T_m(n,k) for 0 < m, 0 <= n, and 0 <= k <= A003056(n+A000217(m-1)).
T_m(0,0) = T_m(m,m) = 1.
T_m(n,k) = T_m(n-k,k-1) + T_m(n-k,k+1) for m < n and 0 < k <= A003056(n+A000217(m-1)).
T_m(n,k) = 0 for 0 < n < m or n < k.
T_m(n,0) = 0 for 0 < n. (End)

A291929 Triangle read by rows: T(n,k) = T(n-k,k-1) + 2*T(n-k,k) + T(n-k,k+1) with T(0,0) = 1 for 0 <= k <= A003056(n).

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 4, 1, 0, 9, 2, 0, 20, 6, 0, 46, 13, 1, 0, 105, 32, 2, 0, 242, 73, 6, 0, 557, 171, 15, 0, 1285, 394, 36, 1, 0, 2964, 914, 85, 2, 0, 6842, 2109, 201, 6, 0, 15793, 4877, 467, 15, 0, 36463, 11261, 1086, 38, 0, 84187, 26014, 2517, 89, 1, 0, 194388

Offset: 0

Seiichi Manyama, Sep 06 2017

			First few rows are:
  1;
  0,    1;
  0,    2;
  0,    4,   1;
  0,    9,   2;
  0,   20,   6;
  0,   46,  13,  1;
  0,  105,  32,  2;
  0,  242,  73,  6;
  0,  557, 171, 15;
  0, 1285, 394, 36, 1.

Seiichi Manyama, Rows n = 0..481, flattened

Row sums give A291930.
Columns 0-1 give A000007, A006958 (for n>0).
Cf. A008289, A291895.

A291954 Triangle read by rows: T(n,k) = T(n-k,k-1) - T(n-k,k) with T(0,0) = 1 for 0 <= k <= A003056(n).

Original entry on oeis.org

1, 0, 1, 0, -1, 0, 1, 1, 0, -1, -1, 0, 1, 0, 0, -1, 0, 1, 0, 1, 1, -1, 0, -1, -1, 0, 0, 1, 0, -1, 0, -1, 0, 2, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 0, 0, 1, 0, -2, -1, 0, -1, 0, 2, 1, 0, 1, 1, -2, 0, 1, 0, -1, -1, 2, 1, -1, 0, 1, 0, -2, -1, 0, 0, -1, 0, 3, 1, -1, 0, 1

Offset: 0

Seiichi Manyama, Sep 06 2017

			First few rows are:
  1;
  0,  1;
  0, -1;
  0,  1,  1;
  0, -1, -1;
  0,  1,  0;
  0, -1,  0,  1;
  0,  1,  1, -1;
  0, -1, -1,  0;
  0,  1,  0, -1;
  0, -1,  0,  2, 1.

Seiichi Manyama, Rows n = 0..481, flattened

Row sums give A003406.
Columns 0-1 give A000007, A062157.
Cf. A008289, A291895, A291929.

G.f. of column k: x^(k*(k+1)/2) / Product_{j=1..k} (1+x^j).

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 2, 4, 0, 7, 17, 0, 2, 118, 0, 82, 436, 202, 0, 2, 3294, 1744, 0, 1456, 18164, 20700, 0, 1515, 140659, 220706, 0, 50774, 1096994, 2317340, 163692, 0, 2, 10116767, 27136103, 2663928, 0, 3052874, 94670868, 328323746, 52954112, 0, 2, 1021089326, 4317753402, 888178070

Offset: 0

Alois P. Heinz, Jul 25 2018

			T(4,1) = 7: 1234, 1324, 1423, 2314, 2413, 3412, 4321.
Triangle T(n,k) begins:
  1;
  0,       1;
  0,       2;
  0,       2,        4;
  0,       7,       17;
  0,       2,      118;
  0,      82,      436,       202;
  0,       2,     3294,      1744;
  0,    1456,    18164,     20700;
  0,    1515,   140659,    220706;
  0,   50774,  1096994,   2317340,   163692;
  0,       2, 10116767,  27136103,  2663928;
  0, 3052874, 94670868, 328323746, 52954112;
  ...

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

Columns k=0-1 give: A000007, A317329.
Row sums give A000142.
Cf. A000217, A003056, A097591, A097592, A123125, A218868, A317273.

b:= proc(u, o, t, s) option remember;
      `if`(u+o=0, x^(nops(s union {t})-1),
       add(b(u-j, o+j-1, 1, s union {t}), j=1..u)+
       add(b(u+j-1, o-j, t+1, s), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2, {})):
seq(T(n), n=0..16);

b[u_, o_, t_, s_] := b[u, o, t, s] = If[u + o == 0, x^(Length[s ~Union~  {t}] - 1), Sum[b[u - j, o + j - 1, 1, s ~Union~ {t}], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 1, s], {j, 1, o}]];
T[n_] := With[{p = b[n, 0, 0, {}]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

T(n*(n+1)/2,n) = A317273(n).

Sum_{k=0..floor((sqrt(1+8*n)-1)/2)} k * T(n,k) = A317328(n).

A341309 Sum of odd divisors of n that are <= A003056(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 4, 1, 1, 4, 1, 1, 9, 1, 1, 4, 1, 6, 4, 1, 1, 4, 6, 1, 4, 8, 1, 9, 1, 1, 4, 1, 13, 4, 1, 1, 4, 6, 1, 11, 1, 1, 18, 1, 1, 4, 8, 6, 4, 1, 1, 13, 6, 8, 4, 1, 1, 9, 1, 1, 20, 1, 6, 15, 1, 1, 4, 13, 1, 13, 1, 1, 9, 1, 19, 4, 1, 6, 13, 1, 1, 11, 6, 1, 4, 12, 1, 18, 21

Offset: 1

N. J. A. Sloane, Feb 14 2021

nonn

Conjecture 1: a(n) is also the total number de parts in all partitions of n into an odd number of consecutive parts. - Omar E. Pol, Mar 16 2022

Conjecture 2: row sums of A352269. - Omar E. Pol, Mar 18 2022

Paolo Xausa, Table of n, a(n) for n = 1..10000

Cf. A000593, A003056, A082647, A131576, A333807, A341310.

A341309[n_]:=With[{t=Floor[(Sqrt[8n+1]-1)/2]},DivisorSum[n,#&,OddQ[#]&&#<=t&]];
Array[A341309,100] (* Paolo Xausa, Mar 25 2023 *)

a(n) = my(m=n>>valuation(n, 2), s=(sqrtint(8*n+1)-1)\2); sumdiv(m, d, if (d <= s, d)); \\ Michel Marcus, Mar 25 2023

a(n) = A204217(n) - A352446(n), conjectured. - Omar E. Pol, Mar 16 2022

cp's OEIS Frontend

A373118 Number T(n,k) of compositions of n such that the set of parts is [k]; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A327803 Sum T(n,k) of multinomials M(n; lambda), where lambda ranges over all partitions of n into parts that form a set of size k; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A291960 Triangle read by rows: T(n,k) = T(n-k,k-1) + k * T(n-k,k) with T(0,0) = 1 for 0 <= k <= A003056(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A116941 Permutation of the natural numbers in conjunction with A116939 and A003056.

Views

Author

Keywords

Comments

Links

Programs

Haskell

Mathematica

Formula

A121430 Number of subpartitions of partition P=[0,1,1,2,2,2,3,3,3,3,4,...] (A003056).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A291904 Triangle read by rows: T(n,k) = T(n-k,k-1) + T(n-k,k+1) with T(0,0) = 1 for 0 <= k <= A003056(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A291929 Triangle read by rows: T(n,k) = T(n-k,k-1) + 2*T(n-k,k) + T(n-k,k+1) with T(0,0) = 1 for 0 <= k <= A003056(n).

Views

Author

Keywords

Examples

Links

Crossrefs

A291954 Triangle read by rows: T(n,k) = T(n-k,k-1) - T(n-k,k) with T(0,0) = 1 for 0 <= k <= A003056(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords