Unicursal Circuit

Author

Eric W. Weisstein
February 4, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/UnicursalCircuit.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/UnicursalCircuit.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Distinct Unicursal Polygrams

((n^2)-7 n+9) a(n)==(n-5) ((n^2)-5 n+3) a(n-5)+((n^2)-7 n+9) a(n-4)-2 (n-6) ((n^2)-5 n+3) a(n-3)+((n^3)-8 (n^2)+18 n-21) a(n-1)+4 (n-5) n a(n-2)

RSolve[{(n^2 - 7n + 9)a[n] ==(n^3 - 8n^2 + 18n - 21)a[n - 1] + 4n(n - 5)a[n - 2] - 2(n -
              6)(n^2 - 5n + 3)a[n - 3] + (n^2 - 7n + 9)a[n - 4] + (n - 5)(n^2 - 5n + 3)a[n - 5],a[1]==1},a[n],n]

Sum

a(n)==(∑_k^(n-1))(∑_j^k)(((2^j) (((-1))^k) n (-k+n-1)! (Binomial[k-1, j-1]) (Binomial[n-k, j]))/(2 (n-k)))+(1/2) (n-1)!+(((-1))^n)

Table[(n-1)!/2+(-1)^n+Sum[(-1)^k Binomial[k-1,j-1]Binomial[n-k,j]n/(n-k)*(n-k-1)!/2*2^j,{k,n-1},{j,Min[n-k,k]}],{n,10}]

Table[(n-1)!/2+(-1)^n+Sum[(-1)^k Binomial[k-1,j-1]Binomial[n-k,j]n/(n-k)*(n-k-1)!/2*2^j,{k,n-1},{j,k}],{n,10}]

(n-1)!/2+(-1)^n+Sum[(-1)^k Binomial[k-1,j-1]Binomial[n-k,j]n/(n-k)*(n-k-1)!/2*2^j,{k,n-1},{j,k}]

Sum[(-1)^k Binomial[k-1,j-1]Binomial[n-k,j]n/(n-k)*(n-k-1)!/2*2^j,{j,k}]

Sum[(((-1))^k) n (-1-k+n)! Hypergeometric2F1[1-k,1+k-n,2,2],{k,n-1}]

Sum[FunctionExpand[(((-1))^k) n (-1-k+n)! Hypergeometric2F1[1-k,1+k-n,2,2]],{k,n-1}]

Infer

l=Table[(n-1)!/2+(-1)^n+Sum[(-1)^k Binomial[k-1,j-1]Binomial[n-k,j]n/(n-k)*(n-k-1)!/2*2^j,{k,n-1},{j,k}],{n,5,20}];

FindSequenceFunction[l]

FindGeneratingFunction[l,x]

FindLinearRecurrence[l]

Count

l=Table[(((-1))^n)+(1/2)(n-1)!+Sum[(((((-1))^k)(2^(j-1))Binomial[k-1,j-1]Binomial[n-k,j]n(n-k-1)!)/((n-k))),{k,n-1},{j,k}],{n,30}]

FindLinearRecurrence[Drop[l,2]]

FindSequenceFunction[Drop[MapIndexed[{#2[[1]],#1}&,l],2],n]

RSolve[{(n^2-7n+9)a[n]==(n^3-8n^2+18n-21)a[n-1]+4n(n-5)a[n-2]-2(n-6)(n^2-5n+3)a[n-3]+(n^2-7n+9)a[n-4]+(n-5)(n^2-5n+3)a[n-5],a[3]==0,a[4]==0,a[5]==1,a[6]==3,a[7]==23},a[n],n]

Table[DifferenceRoot[Function[{\[FormalY],\[FormalN]},{(-3 \[FormalN]-5 (\[FormalN]^2)-(\[FormalN]^3)) \[FormalY][\[FormalN]]+(1-3 \[FormalN]-(\[FormalN]^2)) \[FormalY][1+\[FormalN]]+(-6-4 \[FormalN]+8 (\[FormalN]^2)+2 (\[FormalN]^3)) \[FormalY][2+\[FormalN]]+(-20 \[FormalN]-4 (\[FormalN]^2)) \[FormalY][3+\[FormalN]]+(6-13 \[FormalN]-7 (\[FormalN]^2)-(\[FormalN]^3)) \[FormalY][4+\[FormalN]]+(-1+3 \[FormalN]+(\[FormalN]^2)) \[FormalY][5+\[FormalN]]==0,\[FormalY][3]==0,\[FormalY][4]==0,\[FormalY][5]==1,\[FormalY][6]==3,\[FormalY][7]==23}]][n],{n,3,10}]