A317828 -id:A317828 - cp's OEIS frontend

A317829 Number of set partitions of multiset {1, 2, 2, 3, 3, 3, ..., n X n}.

1, 1, 4, 52, 2776, 695541, 927908528, 7303437156115, 371421772559819369, 132348505150329265211927, 355539706668772869353964510735, 7698296698535929906799439134946965681, 1428662247641961794158621629098030994429958386, 2405509035205023556420199819453960482395657232596725626

Offset: 0

Antti Karttunen, Aug 10 2018

nonn

Number of factorizations of the superprimorial A006939(n) into factors > 1. - Gus Wiseman, Aug 21 2020

			For n = 2 we have a multiset {1, 2, 2} which can be partitioned as {{1}, {2}, {2}} or {{1, 2}, {2}} or {{1}, {2, 2}} or {{1, 2, 2}}, thus a(2) = 4.

Index entries for sequences related to partitions

Cf. A033312, A317826.
Subsequence of A317828.
A000142 counts submultisets of the same multiset.
A022915 counts permutations of the same multiset.
A337069 is the strict case.
A001055 counts factorizations.
A006939 lists superprimorials or Chernoff numbers.
A076716 counts factorizations of factorials.
A076954 can be used instead of A006939 (cf. A307895, A325337).
A181818 lists products of superprimorials, with complement A336426.
Cf. A000178, A002110, A022559, A027423, A124010, A303279, A318284, A322583, A336417, A336496.

g:= proc(n, k) option remember; uses numtheory; `if`(n>k, 0, 1)+
     `if`(isprime(n), 0, add(`if`(d>k or max(factorset(n/d))>d, 0,
        g(n/d, d)), d=divisors(n) minus {1, n}))
    end:
a:= n-> g(mul(ithprime(i)^i, i=1..n)$2):
seq(a(n), n=0..5);  # Alois P. Heinz, Jul 26 2020

chern[n_]:=Product[Prime[i]^(n-i+1),{i,n}];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[facs[chern[n]]],{n,3}] (* Gus Wiseman, Aug 21 2020 *)

\\ See A318284 for count.
a(n) = {if(n==0, 1, count(vector(n,i,i)))} \\ Andrew Howroyd, Aug 31 2020

a(n) = A317826(A033312(n+1)) = A317826((n+1)!-1) = A001055(A076954(n)).
a(n) = A001055(A006939(n)). - Gus Wiseman, Aug 21 2020
a(n) = A318284(A002110(n)). - Andrew Howroyd, Aug 31 2020

a(0)=1 prepended and a(7) added by Alois P. Heinz, Jul 26 2020

a(8)-a(13) from Andrew Howroyd, Aug 31 2020

A317826 Number of partitions of n with carry-free sum in factorial base.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 1, 2, 2, 5, 4, 11, 2, 4, 4, 11, 9, 26, 3, 7, 7, 21, 16, 52, 1, 2, 2, 5, 4, 11, 2, 5, 5, 15, 11, 36, 4, 11, 11, 36, 26, 92, 7, 21, 21, 74, 52, 198, 2, 4, 4, 11, 9, 26, 4, 11, 11, 36, 26, 92, 9, 26, 26, 92, 66, 249, 16, 52, 52, 198, 137, 560, 3, 7, 7, 21, 16, 52, 7, 21, 21, 74, 52, 198, 16, 52, 52, 198, 137, 560, 31, 109

Offset: 0

Antti Karttunen, Aug 08 2018

nonn

"Carry-free sum" in this context means that when the digits of summands (written in factorial base, see A007623) are lined up (right-justified), then summing up of each column will not result in carries to any columns left of that column, that is, the sum of digits of the k-th column from the right (with the rightmost as column 1) over all the summands is the same as the k-th digit of n, thus at most k. Among other things, this implies that in any solution, at most one of the summands may be odd. Moreover, such an odd summand is present if and only if n is odd.
a(n) is the number of set partitions of the multiset that contains d copies of each number k, collected over all k in which digit-positions (the rightmost being k=1) there is a nonzero digit d in true factorial base representation of n, where also digits > 9 are allowed.
Distinct terms are the distinct terms in A050322, that is, A045782. - David A. Corneth & Antti Karttunen, Aug 10 2018

			  n  in fact.base  a(n) carry-free partitions
------------------------------
  0     "0"         1   {}    (unique empty partition, thus a(0) = 1)
  1     "1"         1   {1}
  2    "10"         1   {2}
  3    "11"         2   {2, 1} and {3}, in fact.base: {"10", "1"} and {"11"}
  4    "20"         2   {2, 2} and {4}, in fact.base: {"10" "10"} and {"20"}
  5    "21"         4   {2, 2, 1}, {3, 2}, {4, 1} and {5},
    in factorial base:  {"10", "10", "1"}, {"11", "10"}, {"20", "1"} and {"21"}.

Cf. A001055, A007623, A025487, A045782 (range of this sequence), A050322, A276076, A278236.
Cf. A317827 (positions of records), A317828 (record values), A317829.
Cf. also A227154, A317836.

fcnt(n, m) = {local(s); s=0; if(n == 1, s=1, fordiv(n, d, if(d > 1 & d <= m, s=s+fcnt(n/d, d)))); s};
A001055(n) = fcnt(n, n); \\ From A001055
A276076(n) = { my(i=0,m=1,f=1,nextf); while((n>0),i=i+1; nextf = (i+1)*f; if((n%nextf),m*=(prime(i)^((n%nextf)/f));n-=(n%nextf));f=nextf); m; };
A317826(n) = A001055(A276076(n));

\\ Slightly faster, memoized version:
memA001055 = Map();
A001055(n) = {my(v); if(mapisdefined(memA001055,n), v = mapget(memA001055,n), v = fcnt(n, n); mapput(memA001055,n,v); (v));}; \\ Cached version.
A276076(n) = { my(i=0,m=1,f=1,nextf); while((n>0),i=i+1; nextf = (i+1)*f; if((n%nextf),m*=(prime(i)^((n%nextf)/f));n-=(n%nextf));f=nextf); m; };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ From A046523
A317826(n) = A001055(A046523(A276076(n)));

a(n) = A001055(A276076(n)) = A001055(A278236(n)).
a(A000142(n)) = 1.
a(A001563(n)) = A000041(n).
a(A033312(n+1)) = A317829(n) for n >= 1.

cp's OEIS Frontend

A317829 Number of set partitions of multiset {1, 2, 2, 3, 3, 3, ..., n X n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A317826 Number of partitions of n with carry-free sum in factorial base.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A317827 Positions of records in A317826, computed from its term A317826(1) = 1 onward.

Views

Author

Keywords

Crossrefs