A097861 -id:A097861 - cp's OEIS frontend

A180281 Triangle read by rows: T(n,k) = number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to k.

1, 1, 2, 1, 6, 3, 1, 18, 12, 4, 1, 50, 50, 20, 5, 1, 140, 195, 90, 30, 6, 1, 392, 735, 392, 147, 42, 7, 1, 1106, 2716, 1652, 672, 224, 56, 8, 1, 3138, 9912, 6804, 2970, 1080, 324, 72, 9, 1, 8952, 35850, 27600, 12825, 4950, 1650, 450, 90, 10, 1, 25652, 128865, 110715, 54450, 22022, 7865, 2420, 605, 110, 11

Offset: 1

R. H. Hardin, Aug 24 2010

To clarify a slight ambiguity in the definition, the heaviest box in such an arrangement should contain exactly k balls. - Gus Wiseman, Sep 22 2016

			The T(4,2)=18 arrangements are {0022, 0112, 0121, 0202, 0211, 0220, 1012, 1021, 1102, 1120, 1201, 1210, 2002, 2011, 2020, 2101, 2110, 2200}.
Triangle starts
  1
  1   2
  1   6   3
  1  18  12  4
  1  50  50 20  5
  1 140 195 90 30 6
  ...

Alois P. Heinz, Rows n = 1..200, flattened (first 59 rows from R. H. Hardin)

Cf. A097861, A180282, A180291.
Row sums give A088218.
T(n,ceiling(n/2)) gives A318160.
T(2n,n) gives A318161.
T(2n-1,n) gives A318161.

b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i=0, 0, add(b(n-j, i-1, k), j=0..min(n, k))))
    end:
T:= (n, k)-> b(n$2, k)-b(n$2, k-1):
seq(seq(T(n,k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 16 2018
# second Maple program:
T:= (n, k)-> coeff(series(((x^(k+1)-1)/(x-1))^n
             -((x^k-1)/(x-1))^n, x, n+1), x, n):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 17 2018

T[n_,k_]:=Select[Tuples[Range[0,k],n],And[Max[#]===k,Total[#]===n]&]; (* Gus Wiseman, Sep 22 2016 *)
SequenceForm@@@T[4,2] (* example *)
Join@@Table[Length[T[n,k]],{n,1,6},{k,1,n}] (* sequence *)
(* Second program: *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i == 0, 0, Sum[b[n-j, i-1, k], {j, 0, Min[n, k]}]]];
T[n_, k_] := b[n, n, k] - b[n, n, k-1];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Aug 28 2022, after Alois P. Heinz *)

Empirical: right half of table, T(n,k) = n*binomial(2*n-k-2,n-2) for 2*k > n; also, T(n,2) = Sum_{j=1..n} binomial(n,j)*binomial(n-j,j) = 2*A097861(n). - Robert Gerbicz in the Sequence Fans Mailing List
From Alois P. Heinz, Aug 17 2018: (Start)
T(n,k) = [x^n] ((x^(k+1)-1)/(x-1))^n - ((x^k-1)/(x-1))^n.
T(n,k) = A305161(n,k) - A305161(n,k-1). (End)

A257520 Number of factorizations of m^2 into 2 factors, where m is a product of exactly n distinct primes and each factor is a product of n primes (counted with multiplicity).

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 71, 197, 554, 1570, 4477, 12827, 36895, 106471, 308114, 893804, 2598314, 7567466, 22076405, 64498427, 188689685, 552675365, 1620567764, 4756614062, 13974168191, 41088418151, 120906613076, 356035078102, 1049120176954, 3093337815410

Offset: 0

Alois P. Heinz, Apr 27 2015

nonn

Also number of ways to partition the multiset consisting of 2 copies each of 1, 2, ..., n into 2 multisets of size n.

			a(4) = 10: (2*3*5*7)^2 = 44100 = 210*210 = 225*196 = 294*150 = 315*140 = 350*126 = 441*100 = 490*90 = 525*84 = 735*60 = 1225*36.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Row n=2 of A257462.

Cf. A002426, A097861.

a:= proc(n) option remember; `if`(n<3, [1, 1, 2][n+1],
      ((3*n^2-7*n+3)*a(n-1) +(n-1)*(n-3)*a(n-2)
       -3*(n-1)*(n-2)*a(n-3)) / (n*(n-2)))
    end:
seq(a(n), n=0..40);

G.f.: (1/sqrt((1+x)*(1-3*x))+1/(1-x))/2.
E.g.f.: exp(x)*(1+BesselI(0,2*x))/2.
a(n) = ((3*n^2-7*n+3)*a(n-1) +(n-1)*(n-3)*a(n-2) -3*(n-1)*(n-2)*a(n-3)) / (n*(n-2)) for n>2, a(0) = a(1) = 1, a(2) = 2.
a(n) = (A002426(n)+1)/2.
a(n) = A097861(n)+1.

A182013 Triangle of partial sums of Motzkin numbers.

Original entry on oeis.org

1, 2, 1, 4, 3, 2, 8, 7, 6, 4, 17, 16, 15, 13, 9, 38, 37, 36, 34, 30, 21, 89, 88, 87, 85, 81, 72, 51, 216, 215, 214, 212, 208, 199, 178, 127, 539, 538, 537, 535, 531, 522, 501, 450, 323, 1374, 1373, 1372, 1370, 1366, 1357, 1336, 1285, 1158, 835, 3562, 3561

Offset: 0

Emanuele Munarini, Apr 06 2012

			Triangle begins:
  1
  2,   1
  4,   3,   2
  8,   7,   6,   4
  17,  16,  15,  13,  9
  38,  37,  36,  34,  30,  21
  89,  88,  87,  85,  81,  72,  51
  216, 215, 214, 212, 208, 199, 178, 127
  539, 538, 537, 535, 531, 522, 501, 450, 323

Diagonal elements = Motzkin numbers (A001006).
First column = partial sums of Motzkin numbers (A086615).
Row sums = A097861(n+1).
Diagonal sums = A182015.
Row square-sums = A182017.
Central coefficients = A182016.

M[n_] := If[n==0, 1, Coefficient[(1+x+x^2)^(n+1), x^n]/(n+1)]; Flatten[Table[Sum[M[i], {i,k,n}], {n,0,30}, {k,0,n}]]

M(n):=coeff(expand((1+x+x^2)^(n+1)),x^n)/(n+1);
create_list(sum(M(i),i,k,n),n,0,6,k,0,n);

T(n, k) = Sum_{i=k..n} M(i), where the M(n)'s are the Motzkin numbers.
Recurrence: T(n+1, k+1) = T(n, k) + M(n+1) - M(k).
G.f. (M(x) - y*M(x*y))/((1 - x)*(1 - y)), where M(x) is the generating series for Motzkin numbers.

A345340 The number of squares with vertices from the vertices of the n-dimensional hypercube.

Original entry on oeis.org

0, 0, 1, 6, 36, 200, 1120, 6272, 35392, 200832, 1145856, 6566912, 37779456, 218050560, 1262030848, 7322034176, 42570760192, 247970693120, 1446799212544, 8453937692672, 49463868522496, 289761061240832, 1699288462655488, 9975342691254272, 58611909535989760

Offset: 0

Peter Kagey, Jun 14 2021

nonn

			For n = 4, there are a(4) = 36 such squares, nine of which contain the origin:
(0,0,0,0),(0,0,0,1),(0,0,1,0),(0,0,1,1);
(0,0,0,0),(0,0,0,1),(0,1,0,0),(0,1,0,1);
(0,0,0,0),(0,0,0,1),(1,0,0,0),(1,0,0,1);
(0,0,0,0),(0,0,1,0),(0,1,0,0),(0,1,1,0);
(0,0,0,0),(0,0,1,0),(1,0,0,0),(1,0,1,0);
(0,0,0,0),(0,1,0,0),(1,0,0,0),(1,1,0,0);
(0,0,0,0),(0,0,1,1),(1,1,0,0),(1,1,1,1);
(0,0,0,0),(0,1,0,1),(1,0,1,0),(1,1,1,1); and
(0,0,0,0),(0,1,1,0),(1,0,0,1),(1,1,1,1).

Cf. A097861, A362706.

Cf. A001788 (2-dimensional faces), A016283 (rectangles), A344854 (equilateral triangles).

a(n) = 2^(n-2) * Sum_{k=1..floor(n/2)} n!/(2*k!*k!*(n-2*k)!). - Drake Thomas, Jun 14 2021

a(n) = 2^(n-2) * A097861(n).

A180282 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to 2.

Original entry on oeis.org

2, 6, 18, 50, 140, 392, 1106, 3138, 8952, 25652, 73788, 212940, 616226, 1787606, 5196626, 15134930, 44152808, 128996852, 377379368, 1105350728, 3241135526, 9513228122, 27948336380, 82176836300, 241813226150, 712070156202, 2098240353906, 6186675630818

Offset: 2

R. H. Hardin, Aug 24 2010

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..1665 (terms n=2..59 from R. H. Hardin)

Column 2 of A180281.

Cf. A097861, A002426.

b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i=0, 0, add(b(n-j, i-1, k), j=0..min(n, k))))
    end:
a:= n-> (k-> b(n$2, k)-b(n$2, k-1))(2):
seq(a(n), n=2..30);  # Alois P. Heinz, Aug 17 2018

for(n=2,29,print1(sum(j=1,n, binomial(n,j)*binomial(n-j,j)),", ")) \\ Hugo Pfoertner, Dec 13 2019

a(n) = Sum_{j=1..n} binomial(n,j)*binomial(n-j,j) = 2*A097861(n).

a(n) = A002426(n) - 1. - Jeppe Stig Nielsen, Dec 13 2019

A379838 Triangle read by rows: T(n,k) is the total number of humps with height k in all Motzkin paths of order n, n >= 2 and 1 <= k <= n/2.

Original entry on oeis.org

1, 3, 8, 1, 20, 5, 50, 19, 1, 126, 63, 7, 322, 196, 34, 1, 834, 588, 138, 9, 2187, 1728, 507, 53, 1, 5797, 5016, 1749, 253, 11, 15510, 14454, 5786, 1067, 76, 1, 41834, 41470, 18590, 4147, 416, 13, 113633, 118690, 58487, 15223, 1976, 103, 1, 310571, 339274, 181181, 53599, 8528, 635, 15

Offset: 2

Xiaomei Chen, Jan 04 2025

			Triangle begins:
   [2]     1;
   [3]     3;
   [4]     8,    1;
   [5]    20,    5;
   [6]    50,   19,   1;
   [7]   126,   63,   7;
   [8]   322,  196,  34,  1;
   [9]   834,  588, 138,  9;
  [10]  2187, 1728, 507, 53, 1;
  ...

Xiaomei Chen, Table of n, a(n) for n = 2..401
Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], Dec 2024.
David He and Daniel Tubbenhauer, Tensor powers of representations of (diagram) monoids, arXiv:2508.04054 [math.RT], 2025. See p. 10.

Row lengths give A004526.
Row sums give A097861.
Column 1 gives A140662.
Cf. A064189.

def A379838_triangel(dim):
    M = matrix(ZZ, dim, dim)
    for n in (2..dim+1):
        for k in (1..math.floor(n/2)+1):
            for i in range(n-2*k+1):
                if ((n-i)%2)==0:
                    M[n-2,k-1]=M[n-2, k-1]+(4*k)/(n-i+2*k)*binomial(n,i)*binomial(n-i-1,(n-i)/2+k-1)
    return M

G.f.: Sum_{n>=2, k>=1} T(n,k) * x^n * y^k = x^2 * M^2(x) * y / ((1-x) * (1 - x^2 * M^2(x) * y)), where M(x) is the g.f. for A001006.
T(n,k) = Sum_{i=0..n-2*k, i==n (mod 2)} (4*k) / (n-i+2*k) * binomial(n,i) * binomial(n-i-1,(n-i)/2+k-1).
T(n,k) = Sum_{i=2k-1..n-1} A064189(i,2k-1).
T(n,k) + T(n,k+1) = A064189(n,2k).

A262875 Number of equal-sized disjoint subset combinations from a set of n items.

Original entry on oeis.org

0, 1, 4, 14, 41, 127, 400, 1297, 4520, 17064, 64857, 262286, 1156325, 5199261, 23835336, 117674608, 609741279, 3268286263, 18109939168, 102866828839, 620474818814, 4005211833858, 25747541532731, 166978138395205, 1168773990780772

Offset: 1

Viktar Karatchenia, Oct 03 2015

nonn

a(n) is the total number of combinations of m disjoint subsets of equal size k from a set of n>=2 items, for 2 <= m <= n, 1 <= k <= n/m. m starts at 2 in order to have more than one subset, and m <= n because a subset must contain at least one item.
Given m, for each subset size k, k items are chosen from n; then k items are chosen from the remaining n-k items; then k items are chosen from the remaining n-2*k items; and so on until there are fewer than k items left. Since each m-tuple "kSubSet|kSubSet| ... |kSubSet" is chosen m! times (for example, pairs are chosen as "A|B" and as "B|A"), in order to remove repetitions, we must then divide by m!. Since binomial(n, n + d) = 0 when d>0, the upper limit can be safely increased from floor(n/m) to n.
Thus a(n) = Sum_{m=2..n} b(n,m), where b(n,m) = Sum_{k=1..floor(n/m)} (Product_{j=0..m-1} binomial(n-k*j, k))/m!.

			a(5) = 25+10+5+1 = 41 combinations of equal size disjoint subsets, i.e., given 5 items, there can be 2, 3, 4 or 5 subsets:
A) Pairs can have 1 or 2 items, contributing 10+15=25:
A.1) There are 10 distinct pairs of size 1: "1|2, 1|3, 1|4, 1|5, and 2|3, 2|4, 2|5, and 3|4, 3|5, 4|5".
A.2) And 15 distinct pairs of size 2: "12|34, 12|35, 12|45, and 13|24, 13|25, 13|45, and 14|23, 14|25, 14|35, and 15|23, 15|24, 15|34, and 23|45, 24|35, 25|34".
B) Triplet can have only 1 item, 10 of them: 1|2|3, 1|2|4, 1|2|5, and 1|3|4, 1|3|5, 1|4|5, and 2|3|4, 2|3|5, 2|4|5, 3|4|5.
C) Four-tuple from one item, 5 in total: 1|2|3|4, and 1|2|3|5, 1|2|4|5, 1|3|4|5, finally 2|3|4|5.
D) There is one 5-tuple: 1|2|3|4|5.

Vaclav Kotesovec, Table of n, a(n) for n = 1..600 (terms 1..100 from Viktar Karatchenia)
Viktar Karatchenia, C++ program to calculate b(n,m) and a(n).
Viktar Karatchenia, C++ file for InfInt class
Viktar Karatchenia, Header file for InfInt class

Cf. A097861 (b(n,2)).

Table[Sum[Sum[Product[Binomial[n - k*j, k], {j, 0, m - 1}]/m!, {k, 1, Floor[n/m]}], {m, 2, n}], {n, 1, 30}] (* Vaclav Kotesovec, Aug 05 2019 *)
Table[Sum[Sum[n!/(k!^m * (n - k*m)! * m!), {k, 1, Floor[n/m]}], {m, 2, n}], {n, 1, 30}] (* Vaclav Kotesovec, Aug 05 2019 *)

a(n) = sum(m=2, n, sum(k=1, n\m, prod(j=0, m-1, binomial(n-k*j, k))/m!)); \\ Michel Marcus, Oct 04 2015

a(n) = Sum_{m=2..n} b(n,m), where b(n,m) = Sum_{k=1..floor(n/m)} (Product_{j=0..(m-1)} binomial(n-k*j, k))/m!.

A346906 Triangle read by rows: T(n,k) is the number of ways of choosing a k-dimensional cube from the vertices of an n-dimensional hypercube, where one of the vertices is the origin; 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 3, 1, 1, 15, 9, 4, 1, 1, 31, 25, 10, 5, 1, 1, 63, 70, 35, 15, 6, 1, 1, 127, 196, 140, 35, 21, 7, 1, 1, 255, 553, 476, 175, 56, 28, 8, 1, 1, 511, 1569, 1624, 1071, 126, 84, 36, 9, 1, 1, 1023, 4476, 6070, 4935, 1197, 210, 120, 45, 10, 1

Offset: 0

Peter Kagey, Aug 06 2021

			Triangle begins:
n\k | 0     1     2     3     4     5    6    7   8   9
----+--------------------------------------------------
  0 | 1;
  1 | 1,    1;
  2 | 1,    3,    1;
  3 | 1,    7,    3,    1;
  4 | 1,   15,    9,    4,    1;
  5 | 1,   31,   25,   10,    5,    1;
  6 | 1,   63,   70,   35,   15,    6,   1;
  7 | 1,  127,  196,  140,   35,   21,   7,   1;
  8 | 1,  255,  553,  476,  175,   56,  28,   8,  1;
  9 | 1,  511, 1569, 1624, 1071,  126,  84,  36,  9,  1
One of the T(7,3) = 140 ways of choosing a 3-cube from the vertices of a 7-cube where one of the vertices is the origin is the cube with the following eight points:
(0,0,0,0,0,0,0);
(1,1,0,0,0,0,0);
(0,0,1,0,0,1,0);
(0,0,0,0,1,0,1);
(1,1,1,0,0,1,0);
(1,1,0,0,1,0,1);
(0,0,1,0,1,1,1); and
(1,1,1,0,1,1,1).

Columns: A000012 (k=0), A000225 (k=1), A097861 (k=2), A344559 (k=3).

Cf. A346905.

T[n_, 0] := 1
T[n_, k_] := Sum[n!/(k!*(i!)^k*(n - i*k)!), {i, 1, n/k}]

T(n,k) = A346905(n,k)/2^(n-k).

cp's OEIS Frontend

A180281 Triangle read by rows: T(n,k) = number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A257520 Number of factorizations of m^2 into 2 factors, where m is a product of exactly n distinct primes and each factor is a product of n primes (counted with multiplicity).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A182013 Triangle of partial sums of Motzkin numbers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Maxima

Formula

A345340 The number of squares with vertices from the vertices of the n-dimensional hypercube.

Views

Author

Keywords

Examples

Crossrefs

Formula

A180282 Number of arrangements of n indistinguishable balls in n boxes with the maximum number of balls in any box equal to 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A379838 Triangle read by rows: T(n,k) is the total number of humps with height k in all Motzkin paths of order n, n >= 2 and 1 <= k <= n/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Formula

A262875 Number of equal-sized disjoint subset combinations from a set of n items.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A346906 Triangle read by rows: T(n,k) is the number of ways of choosing a k-dimensional cube from the vertices of an n-dimensional hypercube, where one of the vertices is the origin; 0 <= k <= n.

Views

Author

Keywords

Examples

Crossrefs

Programs