cp's OEIS Frontend

A355388 Number of composable pairs (y, v) of integer compositions of n, where a composition is regarded as an arrow from the number of parts to the number of distinct parts.

%I A355388 #15 Jan 01 2023 20:19:59
%S A355388 1,1,2,6,18,58,174,536,1656,4947,14800,43157,126572,364070,1039926,
%T A355388 2938898,8223400,22846370,62930113,172177400,467002792,1259736804,
%U A355388 3371190792,8973530491,23728305128,62421018163,163255839779,424842462529,1100006243934,2834558927244,7270915592897
%N A355388 Number of composable pairs (y, v) of integer compositions of n, where a composition is regarded as an arrow from the number of parts to the number of distinct parts.
%C A355388 Being composable here means that the length of v equals the number of distinct parts in y.
%H A355388 Alois P. Heinz, <a href="/A355388/b355388.txt">Table of n, a(n) for n = 0..800</a> (first 201 terms from Andrew Howroyd)
%F A355388 a(n) = Sum_{k>=1} binomial(n-1, k-1)*A235998(n, k) for n > 0. - _Andrew Howroyd_, Jan 01 2023
%e A355388 The a(0) = 1 through a(4) = 18 pairs:
%e A355388   ()()  (1)(1)  (2)(2)   (3)(3)    (4)(4)
%e A355388                 (11)(2)  (21)(21)  (31)(31)
%e A355388                          (21)(12)  (31)(13)
%e A355388                          (12)(21)  (31)(22)
%e A355388                          (12)(12)  (13)(31)
%e A355388                          (111)(3)  (13)(13)
%e A355388                                    (13)(22)
%e A355388                                    (22)(4)
%e A355388                                    (211)(31)
%e A355388                                    (211)(13)
%e A355388                                    (211)(22)
%e A355388                                    (121)(31)
%e A355388                                    (121)(13)
%e A355388                                    (121)(22)
%e A355388                                    (112)(31)
%e A355388                                    (112)(13)
%e A355388                                    (112)(22)
%e A355388                                    (1111)(4)
%p A355388 b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
%p A355388       expand(add(b(n-i*j, i-1, p+j)/j!*`if`(j=0, 1, x), j=0..n/i))))
%p A355388     end:
%p A355388 a:= n-> (p-> add(coeff(p, x, i)*binomial(n-1, i-1), i=0..degree(p)))(b(n$2, 0)):
%p A355388 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jan 01 2023
%t A355388 Table[Length[Select[Tuples[Join@@Permutations/@IntegerPartitions[n],2], Length[Union[#[[1]]]]==Length[#[[2]]]&]],{n,0,10}]
%o A355388 (PARI) a(n) = {if(n==0, 1, my(s=0); forpart(p=n, p=Vec(p); my(S=Set(p)); s += binomial(n-1, #S-1)*(#p)!/prod(i=1, #S, my(c=#select(t->t==S[i], p)); c! )); s)} \\ _Andrew Howroyd_, Jan 01 2023
%o A355388 (PARI) \\ for larger n.
%o A355388 a(n) = { local(Cache=Map());
%o A355388   my(F(r,m,p,q) = my(key=[r,m,p,q], z); if(!mapisdefined(Cache, key, &z),
%o A355388   z = if(m==0, if(r==0, p!*binomial(n-1, q-1)), self()(r, m-1, p, q) + sum(j=1, r\m, self()(r-j*m, min(m-1, r-j*m), p+j, q+1)/j!));
%o A355388   mapput(Cache, key, z) ); z);
%o A355388   if(n==0, 1, F(n, n, 0, 0))
%o A355388 } \\ _Andrew Howroyd_, Jan 01 2023
%Y A355388 The case with containment is A032020.
%Y A355388 The inhomogeneous version with containment is A355384, partitions A355383.
%Y A355388 The version for partitions is A355385, with containment A000009.
%Y A355388 A133494 counts compositions of each part of a composition, strict A336139.
%Y A355388 A323583 counts splittings of partitions.
%Y A355388 Cf. A001970, A022811, A063834, A070933, A316245, A319910, A355382.
%K A355388 nonn
%O A355388 0,3
%A A355388 _Gus Wiseman_, Jul 02 2022
%E A355388 Terms a(14) and beyond from _Andrew Howroyd_, Jan 01 2023