Skip to main content
Bounty Ended with 25 reputation awarded by CommunityBot
Minor edits.
Source Link
Somos
  • 36k
  • 3
  • 31
  • 81

The question asked is a special case of a general combinatorial enumeration enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

Replace $\,j\,$ with $\,n-j\,$ in the product of the two binomial coefficients to get

$$ {\binom n {n-j}}{\binom {n-j}{k+j-n}} = \frac{n!}{j!(j+k-n)!(2n-2j-k)!}. \tag8 $$

Replace $n\to T\!-\!1,j\to N_+,k\to n_2\!-\!n_1$ toMake the replacements

$$n\mapsto T\!-\!1,\;\;j\mapsto N_+,\;\;k\mapsto n_2\!-\!n_1 \tag9 $$

to get the last expression in the question.

The question asked is a special case of a general combinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

Replace $\,j\,$ with $\,n-j\,$ in the product of the two binomial coefficients to get

$$ {\binom n {n-j}}{\binom {n-j}{k+j-n}} = \frac{n!}{j!(j+k-n)!(2n-2j-k)!}. \tag8 $$

Replace $n\to T\!-\!1,j\to N_+,k\to n_2\!-\!n_1$ to get the last expression in the question.

The question asked is a special case of a general combinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

Replace $\,j\,$ with $\,n-j\,$ in the product of the two binomial coefficients to get

$$ {\binom n {n-j}}{\binom {n-j}{k+j-n}} = \frac{n!}{j!(j+k-n)!(2n-2j-k)!}. \tag8 $$

Make the replacements

$$n\mapsto T\!-\!1,\;\;j\mapsto N_+,\;\;k\mapsto n_2\!-\!n_1 \tag9 $$

to get the last expression in the question.

Rewording.
Source Link
Somos
  • 36k
  • 3
  • 31
  • 81

The question asked is a special case of a general combinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

Replace $\,j\,$ with $\,n-j\,$ in the product of the two binomial coefficients to get

$$ {\binom n {n-j}}{\binom {n-j}{k+j-n}} = \frac{n!}{j!(j+k-n)!(2n-2j-k)!}. \tag8 $$

Replace $n\to T\!-\!1,j\to N_+,k\to n_2\!-\!n_1$ to get the last expression in the question.

The question asked is a special case of a general combinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

The question asked is a special case of a general combinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

Replace $\,j\,$ with $\,n-j\,$ in the product of the two binomial coefficients to get

$$ {\binom n {n-j}}{\binom {n-j}{k+j-n}} = \frac{n!}{j!(j+k-n)!(2n-2j-k)!}. \tag8 $$

Replace $n\to T\!-\!1,j\to N_+,k\to n_2\!-\!n_1$ to get the last expression in the question.

Fixed obvious typo. Rewording.
Source Link
Somos
  • 36k
  • 3
  • 31
  • 81

The question asked is a special case of a general combinatoricialcombinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial isare given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

Oneand one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

The question asked is a special case of a general combinatoricial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial is given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

One of several formulas for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

The question asked is a special case of a general combinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$

Rewording and adjust spacing.
Source Link
Somos
  • 36k
  • 3
  • 31
  • 81
Loading
Source Link
Somos
  • 36k
  • 3
  • 31
  • 81
Loading