A070289 -id:A070289 - cp's OEIS frontend

A215521 Number T(n,k) of distinct values of multinomial coefficients M(n;lambda), where lambda ranges over all partitions of n with largest part = k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 3, 2, 1, 1, 1, 4, 5, 5, 3, 2, 1, 1, 1, 4, 7, 6, 5, 3, 2, 1, 1, 1, 5, 8, 9, 7, 5, 3, 2, 1, 1, 1, 5, 10, 10, 10, 7, 5, 3, 2, 1, 1, 1, 6, 12, 14, 12, 11, 7, 5, 3, 2, 1, 1, 1, 6, 14, 16, 17, 13, 11, 7, 5, 3, 2, 1, 1

Offset: 1

Alois P. Heinz, Aug 14 2012

Differs from A008284 first at T(11,4).

			T(4,2) = 2 = |{4!/(2!*2!), 4!/(2!*1!*1!)}| = |{6, 12}|.
T(7,4) = 3 = |{35, 105, 210}|.
T(8,3) = 5 = |{560, 1120, 1680, 3360, 6720}|.
T(11,4) = 10 = |{11550, 34650, 46200, 69300, 138600, 207900, 277200, 415800, 831600, 1663200}|.
Triangle T(n,k) begins:
  1;
  1,  1;
  1,  1,  1;
  1,  2,  1,  1;
  1,  2,  2,  1,  1;
  1,  3,  3,  2,  1,  1;
  1,  3,  4,  3,  2,  1,  1;
  1,  4,  5,  5,  3,  2,  1,  1;
  1,  4,  7,  6,  5,  3,  2,  1,  1;
  1,  5,  8,  9,  7,  5,  3,  2,  1,  1;
  1,  5, 10, 10, 10,  7,  5,  3,  2,  1,  1;
  ...

Alois P. Heinz, Rows n = 1..100, flattened
Wikipedia, Multinomial coefficients

Columns k=1-3 give: A000012 (for n>0), A004526, A069905(n) = A001399(n-3) for n>=3.
T(2*n,n) gives: A070289.
Cf. A008284, A215520.

b:= proc(n, i) option remember; `if`(n=0, {1}, `if`(i<1, {},
      {b(n, i-1)[], seq(map(x-> x*i!^j, b(n-i*j, i-1))[], j=1..n/i)}))
    end:
T:= (n, k)-> nops(b(n-k, min(k, n-k))):
seq(seq(T(n, k), k=1..n), n=1..15);

b[n_, i_] := b[n, i] = If[n == 0, {1}, If[i < 1, {}, Join[b[n, i - 1], Table[ b[n - i*j, i - 1] *i!^j, {j, 1, n/i}] // Flatten]] // Union]; T[n_, k_] := Length[b[n, k]]; Table[Table[T[n - k, Min[k, n - k]], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Jan 21 2015, after Alois P. Heinz *)

A309999 Number of distinct values of multinomial coefficients M(n;lambda) where lambda ranges over all partitions of n into distinct parts.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 25, 32, 35, 44, 53, 61, 72, 81, 98, 114, 130, 147, 176, 200, 229, 257, 291, 342, 387, 442, 501, 573, 642, 714, 807, 907, 1037, 1159, 1293, 1458, 1624, 1811, 2024, 2246, 2505, 2785, 3114, 3449, 3795, 4213, 4660

Offset: 0

Alois P. Heinz, Aug 26 2019

nonn

Differs from A000009 first at n = 15: a(15) = 25 < 27 = A000009(15). There are two repeated multinomial coefficients for n = 15: 1365 = M(15;11,4) = M(15;12,2,1) and 30030 = M(15;9,5,1) = M(15;10,3,2).

Alois P. Heinz, Table of n, a(n) for n = 0..125
Wikipedia, Multinomial coefficients
Wikipedia, Partition (number theory)

Cf. A000009, A070289.

g:= proc(n, i) option remember; `if`(i*(i+1)/2binomial(n, i)*x, g(n-i, min(n-i, i-1)))[], g(n, i-1)[]}))
    end:
a:= n-> nops(g(n$2)):
seq(a(n), n=0..55);

g[n_, i_] := g[n, i] = If[i(i+1)/2 < n, {}, If[n == 0, {1}, Union[ Binomial[n, i] #& /@ g[n - i, Min[n - i, i - 1]], g[n, i - 1]]]];
a[n_] := Length[g[n, n]];
a /@ Range[0, 55] (* Jean-François Alcover, Dec 07 2020, after Alois P. Heinz *)

A165729 Number of distinct rate points of concentric permutation source codes with two initial codewords in dimension n.

Original entry on oeis.org

3, 6, 15, 27, 60, 97, 186, 335

Offset: 2

Vivek Goyal (vgoyal(AT)mit.edu), Sep 25 2009

H. Q. Nguyen, L. R. Varshney, and V. K. Goyal, Concentric Permutation Source Codes, arXiv:0909.0704 [cs.IT], 2009-2010.

Cf. A070289 (number of distinct rate points of an ordinary permutation source code).

Cf. A165730, A165731.

A165730 Number of distinct rate points of concentric permutation source codes with three initial codewords in dimension n.

Original entry on oeis.org

4, 10, 33, 68, 207, 415, 1038, 2440

Offset: 2

Vivek Goyal (vgoyal(AT)mit.edu), Sep 25 2009

H. Q. Nguyen, L. R. Varshney, and V. K. Goyal, Concentric Permutation Source Codes, arXiv:0909.0704 [cs.IT], 2009-2010.

Cf. A070289, (number of distinct rate points of an ordinary permutation source code), A165729, A165731.

A165731 Number of distinct rate points of concentric permutation source codes with four initial codewords in dimension n.

Original entry on oeis.org

5, 15, 56, 132, 517, 1202, 3888, 11911

Offset: 2

Vivek Goyal (vgoyal(AT)mit.edu), Sep 25 2009

H. Q. Nguyen, L. R. Varshney and V. K. Goyal, Concentric Permutation Source Codes, arXiv:0909.0704 [cs.IT], 2009-2010.

Cf. A070289 (number of distinct rate points of an ordinary permutation source code), A165729, A165730.

A210238 Triangle of multiplicities D(n) of multinomial coefficients corresponding to sequence A210237.

Original entry on oeis.org

1, 2, 1, 3, 6, 1, 4, 12, 6, 12, 1, 5, 20, 20, 30, 30, 20, 1, 6, 30, 30, 15, 60, 120, 20, 60, 90, 30, 1, 7, 42, 42, 42, 105, 210, 105, 245, 420, 140, 105, 210, 42, 1, 8, 56, 56, 224, 28, 336, 336, 280, 168, 168, 840, 420, 1120, 70, 1120, 560, 168, 420, 56, 1

Offset: 1

Sergei Viznyuk, Mar 18 2012

Multiplicity D(n) of multinomial coefficient M(n) is the number of ways the same value of M(n)=n!/(m1!*m2!*..*mk!) is obtained by distributing n identical balls into k distinguishable bins.
Differs from A209936 after a(21).
Differs from A035206 after a(36).
The checksum relationship: sum(M(n)*D(n)) = k^n
The number of terms per row (for each value of n starting with n=1) forms sequence A070289.

			1
2, 1
3, 6, 1
4, 12, 6, 12, 1
5, 20, 20, 30, 30, 20, 1
6, 30, 30, 15, 60, 120, 20, 60, 90, 30, 1
7, 42, 42, 42, 105, 210, 105, 245, 420, 140, 105, 210, 42, 1
Thus for n=3 (third row) the same value of multinomial coefficient follows from the following combinations:
3!/(3!0!0!) 3!/(0!3!0!) 3!/(0!0!3!) (i.e. multiplicity=3)
3!/(2!1!0!) 3!/(2!0!1!) 3!/(0!2!1!) 3!/(0!1!2!) 3!/(1!0!2!) 3!/(1!2!0!)  (i.e. multiplicity=6)
3!/(1!1!1!) (i.e. multiplicity=1)

Sergei Viznyuk, C-program for the sequence.

Cf. A210237, A209936, A035206, A070289.

Table[Last/@Tally[Multinomial@@@Compositions[k,k]],{k,8}] (* Wouter Meeussen, Mar 09 2013 *)

A213008 Triangle T(n,k) of number of distinct values of multinomial coefficients corresponding to sequence A026820 (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 3, 4, 5, 1, 3, 5, 6, 7, 1, 4, 7, 9, 10, 11, 1, 4, 8, 10, 12, 13, 14, 1, 5, 9, 14, 16, 18, 19, 20, 1, 5, 12, 17, 21, 23, 25, 26, 27, 1, 6, 13, 21, 26, 30, 32, 34, 35, 36, 1, 6, 16, 25, 33, 37, 41, 43, 45, 46, 47, 1, 7, 19, 32, 42, 50, 54, 58, 60, 62, 63, 64

Offset: 1

Sergei Viznyuk, Jun 01 2012

Differs from A026820 after position 24.

Includes sequence A070289 when k = n.

			Triangle T(n,k) begins:
  1;
  1, 2;
  1, 2, 3;
  1, 3, 4,  5;
  1, 3, 5,  6,  7;
  1, 4, 7,  9, 10, 11;
  1, 4, 8, 10, 12, 13, 14;
  ...
Thus, for n = 7 and k = 6 there are 13 distinct values of multinomial coefficients corresponding to partitions of n = 7 into at most k = 6 parts. The corresponding number of partitions from sequence A026820 is 14. That is because partitions 7 = 4 + 1 + 1 + 1 and 7 = 3 + 2 + 2 produce the same value of multinomial coefficient 7!/(4!*1!*1!*1!) = 7!/(3!*2!*2!).

Alois P. Heinz, Rows n = 1..45, flattened
Katsuhisa Yamanaka, Shin-ichiro Kawano, Yosuke Kikuchi, and Shin-ichi Nakano, Constant Time Generation of Integer Partitions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E90-A, no.5, pp. 888-895, (May-2007).
Sergei Viznyuk, C-Program for this sequence, 2012.
Sergei Viznyuk, C-Program for sequences A026820, A070289, and A213008 (local copy), 2012.

Cf. A026820, A070289.

b:= proc(n, i, k) option remember; if n=0 then {1} elif i<1
      then {} else {b(n, i-1, k)[], seq(map(x-> x*i!^j,
              b(n-i*j, i-1, k-j))[], j=1..min(n/i, k))} fi
    end:
T:= (n, k)-> nops(b(n, n, k)):
seq(seq(T(n,k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 14 2012

b[n_, i_, k_] := b[n, i, k] = If[n == 0, {1}, If[i<1, {}, Join[b[n, i-1, k], Table[ Function[#*i!^j] /@ b[n-i*j, i-1, k-j], {j, 1, Min[n/i, k]}] // Flatten] // Union] ]; T[n_, k_] := Length[b[n, n, k]]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 12 2015, after Alois P. Heinz *)

A309897 Number of not unique partition coefficients of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 6, 9, 13, 22, 33, 51, 74, 104, 142, 194, 261, 351, 464, 616, 802, 1047, 1344, 1716, 2186, 2766, 3473, 4367, 5448, 6774, 8375, 10329, 12685, 15553, 18982, 23098, 28046, 33966, 40976, 49381, 59301, 71095, 85017, 101491, 120859

Offset: 0

Peter Luschny, Sep 06 2019

nonn

We call (p1+p2+ ...)! / (p1!*p2!*p3! ...) a 'partition coefficient' of n if (p1, p2, p3, ...) is a partition, n = p1 + p2 + ... and denote it by P(n, p).

			a(7) = 1 because the partition coefficients of 7 are [1, 7, 21, 42, 35, 105, 210, 140, 210, 420, 840, 630, 1260, 2520, 5040], P(7, [3, 2, 2]) = P(7, [4, 1, 1, 1]) = 210 and all other partition coefficients are unique.
We say that two partitions of n are multinomial-equivalent if they have the same partition coefficient. For instance [6, 2, 2, 1, 1] ~ [5, 4, 1, 1, 1] ~ [5, 3, 2, 2] and [6, 4, 1, 1, 1, 1, 1] ~ [6, 3, 2, 2, 1, 1] ~ [5, 4, 3, 1, 1, 1] ~ [5, 3, 3, 2, 2].

Cf. A000041, A070289.

h := proc(n,k) option remember;
if n = 0 then return [1] elif k < 1 then return [] fi;
[h(n, k-1)[], seq(map(x -> x*k!^j, h(n-k*j, k-1))[], j=1..n/k)] end:
A309897 := proc(n) h(n, n); nops(%) - nops(convert(%, set)) end:
seq(A309897(n), n=0..48);

def A309897(n):
    P = Partitions(n)
    M = set(multinomial(x) for x in P)
    return P.cardinality() - len(M)
[A309897(n) for n in range(29)]

a(n) = A000041(n) - A070289(n).

A376821 Number of irreducible pairs of partitions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 3, 3, 6, 7, 8, 4, 6, 7, 12, 17, 23, 23, 31, 38, 36, 70, 71, 101, 127, 118, 145, 191, 209, 261, 309, 396, 462, 512, 652, 769, 878, 1097, 1320, 1563, 1827, 2098, 2533, 2932, 3475, 4185, 4756, 5726, 6614, 7686, 9189, 10825

Offset: 0

Pontus von Brömssen, Oct 05 2024

nonn

A pair of partitions of n is irreducible if the two partitions yield the same multinomial coefficient but have no parts in common. The partitions in the pair are required to be distinct, otherwise a(0) would be 1.

			   n | irreducible pairs of partitions of n
  ---+-------------------------------------
   7 | (1,1,1,4), (2,2,3)
   8 | (1,1,6), (3,5)
  10 | (1,4,5), (2,2,6)
  13 | (1,1,1,10), (6,7)
     | (1,1,3,8), (2,4,7)
     | (1,1,1,1,1,8), (2,2,2,7)
  14 | (1,2,2,9), (3,3,8)
     | (1,1,1,2,9), (3,4,7)
     | (1,1,1,1,1,1,4,4), (2,2,2,2,3,3)

George E. Andrews, Arnold Knopfmacher, and Burkhard Zimmermann, On the number of distinct multinomial coefficients, Journal of Number Theory 118 (2006), 15-30; arXiv preprint, arXiv:math/0509470 [math.CO], 2005. (See Section 7.)

Cf. A070289, A260669, A325306, A376661.

cp's OEIS Frontend

A215521 Number T(n,k) of distinct values of multinomial coefficients M(n;lambda), where lambda ranges over all partitions of n with largest part = k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A309999 Number of distinct values of multinomial coefficients M(n;lambda) where lambda ranges over all partitions of n into distinct parts.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A165729 Number of distinct rate points of concentric permutation source codes with two initial codewords in dimension n.

Views

Author

Keywords

Links

Crossrefs

A165730 Number of distinct rate points of concentric permutation source codes with three initial codewords in dimension n.

Views

Author

Keywords

Links

Crossrefs

A165731 Number of distinct rate points of concentric permutation source codes with four initial codewords in dimension n.

Views

Author

Keywords

Links

Crossrefs

A210238 Triangle of multiplicities D(n) of multinomial coefficients corresponding to sequence A210237.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A213008 Triangle T(n,k) of number of distinct values of multinomial coefficients corresponding to sequence A026820 (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A309897 Number of not unique partition coefficients of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

SageMath

Formula

A376821 Number of irreducible pairs of partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs