[seqfan] Re: Prove formula?

Richard Mathar mathar at strw.leidenuniv.nl
Wed Mar 21 21:23:42 CET 2012


rh> Is it obvious, or easy to prove?  If so "Empirical" can be omitted.
rh> T(n,k)=Number of arrays of n nonnegative integers with value i>0 appearing only 
rh> after i-1 has appeared at least k times
rh> Empirical: T(n,k)=1 if n<=k else sum{i=0..n-k}(binomial(n-k,i)*T(i,k))

I think there is a rather simple combinatorial interpretation of this
recursive formula: Take a "valid" sequence of length n and remove all
zeros. The remaining subsequence is again "valid" in the sense that one
could subtract 1 from all its integers and these would still obey the
constraint on the minimum appearances.

The formula tells this basically in a constructive way:
Reserve the first k places at the start of a
valid sequence of integers of length n for the zeros. Everything later (the
"tail") consists of n-k integers, some of which may or may not be zeros.
All valid tails can be constructed by starting from "valid" sequences of
length i=0,2....,n-k, adding 1 to each entry of such a sequence, and filling
the n-k-i positions not yet held in the tail with zeros. The binomial
factor binomial(n-k,i) says that one needs to choose i places in the pool
of n-k zeros to disperse the "valid" sequence of length i in between the
zeros. After updating the "valid" sequence of the tail by 1, there is a
1-to-1 correspondence of these choices with distinct tails.

Richard Mathar

More information about the SeqFan mailing list