a r X i v :0712.3946v 1 [m a t h .C O ] 23 D e c 2007
A Combinatorial Interpretation for the Identity
n k =0
n k
k j =0
k j
3=
n k =0
n k 2 2k k
DAVID CALLAN
Department of Statistics University of Wisconsin-Madison
1300University Ave Madison,WI 53706-1532callan@stat.wisc.edu
December 21,2007
Abstract
The title identity appeared as Problem 75-4,propod by P.Barrucand,in Siam Review in 1975.The published solution equated constant terms in a suitable poly-nomial identity.Here we give a combinatorial interpretation in terms of card deals.
The title identity was propod by Pierre Barrucand in the Problems and Solutions ction of Siam Review in 1975[1]and was considered sufficiently interesting to be included in the problem compilation [2].The published solution [3]equated constant terms in the identity
1+(1+x )(1+y/x )(1+1/y ) n =
1+1+x x n .
The problem was also solved by G.E.Andrews,M.E.H.Ismail,and O.G.Ruehr using hypergeometric functions,by C.L.Mallows using probability,and by the pro-por using differential equations.The q
uence generated by each side of the identity,(1,3,15,93,639,...)n ≥0,is A002893in The On-Line Encyclopedia of Integer Seque蓝色用英语怎么说
nces .Here we show that the identity counts certain derangement-type card deals in two different ways.To construct the deals start with a deck of 3n cards,n each colored red,green and blue,in denominations 1through n .Next choo a subt S of the denominations and partition all the cards of the de悲剧爱情故事
nominations into a list of three equal size ts such that the first t contains no red cards,the cond no green cards,and the
third no blue cards.Or,more picturesquely,deal all cards of the chon denominations into three equa笑字的成语
l-size hands to players designated red,green an动漫黑白头像
d blue in such a way that no player receives a card of her own color.Let T n denote the t of all triples(deals) obtained in this way.For example,T2is shown below with deals classified by the t S of denominations.
denomination avoid
red blue
11212
21112
31122
41211
51212
61212
71222
82211
92212
101212
1111
1211
1322
1422
15∅∅
The15deals in T2
The left side of the title identity counts the deals by size of the denomination t S:the number of deals in T n with|S|=k is n k k j=0 k j 3.The right side counts them by number of distinct denominations occurring in the red player’s hand:the number of deals in T n with k distinct denominations in red’s hand is n k 2 2k k .
We now proceed to verify the asrtion九年级优秀作文
s.Since there are n k ways to choo a subt S of size k from the denominations,thefirst asrtion will obviously follow from Proposition1.The number of ways to deal all3n cards so that no player receives a card of her own color is n j=0 n j 3[A000172].
Proof Let us count the deals by number j of green cards in red’s hand.If there are j green cards in red’s hand,then the balance of red’s hand must consist of n−j blue cards,red cards not being allowed.The remaining n−j green cards must be in blue’s hand and the remaining j blue cards in green’s hand.This forces j red cards in blue’s hand and n−j red cards in green’s hand.Thus the deal i
s determined by a choice of j green cards and a choice of n−j blue 走马简谱
cards for red’s hand,and a choice of j red cards for blue’s hand— n j 3choices in all.
As for the cond asrtion,let D denote the t of denominations appearing in the red player’s hand.Since the number of deals depends on D only through its size and since there are n k ways to choo a t D of size k劳动合同文本
,it suffices to show
Proposition2.The number of deals in T n for which the denominations appearing in the red player’s hand are1,2,...,k is n k 2k k [A026375].
Proof Partition the t of denominations D={1,2,...,k}occurring in red’s hand into three blocks:A,tho appearing on both blue and green cards(in red’s hand); B,tho appearing on blue cards only;C,tho appearing on green cards only.Set |A|=a,|B|=b,|C|=c.Thus a+b+c=k and2a+b+c is the size of each hand. This implies that the number of denominations not in{1,2,...,k}but involved in the deal is a;call this t E.The green cards with denominations in B⊔E must occur in blue’s hand.This accounts for|B⊔E|=a+b cards in blue’s hand and so the balance of blue’s hand must consist of a+c red cards.
Thus the deal is determined by a choice of the ts A and B(C is then determined), the t E,and a c
hoice of a+c red cards(from the k+a available)for blue’s hand.The choices are counted by the sum over nonnegati谓语动词
ve a and b of the product k a [choo A] k−a b [choo B] n−k a [choo E] k+a a+c [choo red cards for blue’s hand].This sum can be written
a≥0 k a n−k n−k−a b≥0 k−a b k+a k−b .
An application of the ever-uful Vandermonde convolution to the inner sum yields 2k k , independent of a,and then another application evaluates the entire sum as n n−k 2k k =
n k 2k k .
Acknowledgement I thank Zerinvary Lajos for pointing out that the counting quence of Proposition1is a special ca of the Dinner-Diner matching numbers A059066.
References
[1]P.Barrucand,A combinatorial identity,Problem75-4,SIAM Review,17(1975),168.
[2]Murray S.Klamkin(editor),Problems in Applied Mathematics:Selections from
SIAM Review,SIAM,1990,148–149.
[3]D.R.Breach,D.McCarthy,D.Monk,and P.E.O’Neil,Solution for Problem75-4,
SIAM Review,18(1976),303.
