|
%I #42 May 03 2020 13:45:37
%S 1,1,2,6,16,44,134,414,1290,4102,13306,43718,145176,487384,1651154,
%T 5636702,19381392,67074420,233483430,817106622,2873589060,10151255976,
%U 36009769278,128231072994,458268615966,1643227382022,5910606009330,21322486928518,77132729929864
%N Number of anagram compositions of 2n that can be formed from the compositions of n.
%C A composition of n is an ordered sequence of positive integers whose sum is n. An anagram composition of n can be divided into two consecutive subsequences having the same parts, with a central part between the subsequences permitted.
%C a(n) is the number of anagram compositions of 2n with no central summand.
%C Here is a computation algorithm: List the individual partitions of n. Then for each partition, determine the corresponding number of compositions. Square each of these numbers then add them together.
%H Alois P. Heinz, <a href="/A263897/b263897.txt">Table of n, a(n) for n = 0..1000</a>
%H Miklos Bona, Rebecca Smith, <a href="https://arxiv.org/abs/1605.06158">An Involution on Involutions and a Generalization of Layered Permutations</a>, arXiv preprint arXiv:1605.06158 [math.CO], 2016. See Theorem 4.3.
%e For n=3, the compositions are [3], [1,2], [2,1], [1,1,1]. The anagram compositions of 2*3=6 are [3][3], [1,2][1,2], [1,2][2,1], [2,1][1,2], [2,1][2,1], [1,1,1][1,1,1], so there are a(3)=6 anagram compositions in all.
%e For n=4, the individual partitions are [4], [3,1], [2,2], [2,1,1] and [1,1,1,1]. The corresponding number of compositions are 1, 2, 1, 3, and 1. The corresponding squares of these numbers are 1, 4, 1, 9, and 1. The sum of these squares is a(4)=16.
%p b:= proc(n, i, p) option remember; `if`(n=0, p!^2,
%p `if`(i<1, 0, add(b(n-i*j, i-1, p+j)/j!^2, j=0..n/i)))
%p end:
%p a:= n-> b(n$2, 0):
%p seq(a(n), n=0..35); # _Alois P. Heinz_, Oct 29 2015
%t b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!^2, If[i<1, 0, Sum[b[n-i*j, i-1, p+j]/j!^2, {j, 0, n/i}]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Nov 05 2015, after _Alois P. Heinz_ *)
%o (Python)
%o from sympy.core.cache import cacheit
%o from sympy import factorial as f
%o @cacheit
%o def b(n, i, p): return f(p)**2 if n==0 else 0 if i<1 else sum(b(n - i*j, i - 1, p + j)//f(j)**2 for j in range(n//i + 1))
%o def a(n): return b(n, n, 0)
%o print([a(n) for n in range(36)]) # _Indranil Ghosh_, Aug 18 2017, after Maple code
%Y First differences of A097085.
%K nonn
%O 0,3
%A _Gregory L. Simay_, Oct 28 2015
%E a(9)-a(28) from _Alois P. Heinz_, Oct 29 2015
|
