Comptage des termes en opération récursive

Question

Supposer $X$ est une algèbre et $T :X\to X$est une fonction linéaire. Laisser$L:X\to X$ être une fonction satisfaisant la propriété suivante $$L(a \cdot b)= T(a)\cdot b + a \cdot T(b)+b\cdot T(a)+T(b)\cdot a\tag{*}$$ Maintenant, je suis intéressé à compter les termes de ce type d'expansion pour une application imbriquée de $L$; c'est-à-dire que je veux savoir combien de termes sont dans$$L(a_1\cdot L(a_2\cdots L(a_{n-2}\cdot L(a_{n-1}\cdot a_n))\cdots). \tag{**}$$ En particulier, (*) montre que pour $n=2$, nous avons quatre mandats. Je veux écrire un programme pour lequel$n$ est spécifié et me donne le nombre de termes de la décomposition de $(**)$. À titre d'exemple, l'expression$(***)$ avec $n=3$ ressemble à $L(a_1\cdot L(a_2\cdot a_3)).$

Je ne m'intéresse pas à la forme de la décomposition elle-même, seulement au nombre de termes. Tenant compte du fait que deux termes similaires fusionneront en un seul terme, par ex.$a\cdot T(b)+a\cdot T(b)=2aT(b)$.

Answer 1

Le moyen le plus simple est simplement de le résoudre. Commençons par implémenter une version de Lusing NonComutativeMultiply:

L[a_, b_] := Plus @@ Map[
   Distribute[#, Plus, NonCommutativeMultiply]&,
   {T[a] ** b, a ** T[b], b ** T[a], T[b] ** a}
]

Le Distributes'assure que toutes les multiplications sont développées. En utilisant Plus, des termes identiques seront regroupés automatiquement, il n'y a donc pas lieu de s'inquiéter à ce sujet.

Ensuite, vous pouvez générer l' Lexpression imbriquée avec a Fold, puis prendre simplement la longueur:

Fold[L[a[#2], #1] &, a[1], Range[2, 10]] // Length

1534

Vous pouvez obtenir la séquence de longueurs avec FoldList(jeter le premier élément a[1]de la séquence):

Length /@ Rest[FoldList[L[a[#2], #1] &, a[1], Range[2, 10]]]

{4, 10, 22, 46, 94, 190, 382, ​​766, 1534}

Prime

En prime, il semble que la série puisse être équipée d'une formule assez simple (ce qui n'est probablement pas trop surprenant):

FindSequenceFunction[%, n]

-2 + 3 * 2 ^ n