Explanation For an n × n chessboard define a set F of “forbidden" locations, consisting of ( 1 , 2 ) , ( 2 , 3 ) , ... ( n − 1 , n ) ( n , 1 ) . For 0 ≤ k ≤ n let a ( n , k ) denote the number of ways to place k nonattacking rooks on the chessboard, such that each rook is contained in F . Order the elements of the F in a circular fashion n 1 2 3 4 . . . 2 n − 2 2 n − 1 2 n n t h location ( 1 , 1 ) ( 1 , 2 ) ( 2 , 2 ) ( 2 , 3 ) . . . ( n − 1 , n ) ( n , n ) ( n , 1 ) with the first location following the last one. Given two locations in F , they are adjacent in the circular ordering if and only if they are in the same row or column of the chessboard. Thus a ( n , k ) represents the number of k -subsets of the set F , such that no two elements of the subset are adjacent in the circular ordering. Denote such a k -subset by { a i } i = 1 k with 1 ≤ a 1 < a 2 < ... < a k ≤ 2 n . Define; x 1 = a 1 − 1 , x 2 = a 2 − 2 , ... x k = a k − a k − 1 − 2 , x k + 1 = 2 n − a k Then x i ≥ 0 ( 1 ≤ i ≤ k + 1 ) , ∑ i = 1 k + 1 x i = 2 n − 2 k + 1 ( 1 ) Initially ignoring the constraint on the pair ( x 1 , x k + 1 ) , the number of integral solutions to ( 1 ) is ( 2 n − k + 1 k )

5th Edition

ISBN: 9780136020400

Author: Richard A. Brualdi

Publisher: Prentice Hall

See similar textbooks

Question

Chapter 6, Problem 33E

To determine

To prove: The identity a(n,k)=(2nn−k)(2n−kk).

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 6, Problem 32E

Chapter 6, Problem 34E

Students have asked these similar questions

Please answer this question for me, make it in clear steps.

The diagram below models the layout at a carnival where G, R, P, C, B, and E are various locations on the grounds. GRPC is a parallelogram. Part A: Identify a pair of similar triangles. Part B: Explain how you know the triangles from Part A are similar. Part C: Find the distance from B to E and from P to E. Show your work. Make sure to explain and show your work for each part.

What is the value of the last row

Chapter 6 Solutions

Introductory Combinatorics

Ch. 6 - Prob. 1E Ch. 6 - Find the number of integers between 1 and 10,000...Ch. 6 - Find the number of integers between 1 and 10,000...Ch. 6 - Prob. 4E Ch. 6 - Determine the number of 10-combinations of the...Ch. 6 - A bakery sells chocolate, cinnamon, and plain...Ch. 6 - Determine the number of solutions of the equation...Ch. 6 - Determine the number of solutions of the equation...Ch. 6 - Determine the number of integral solutions of the...Ch. 6 - Let S be a multiset with k distinct objects with...

Ch. 6 - Determine the number of permutations of {1, 2, …,...Ch. 6 - Determine the number of permutations of {1, 2, ⋯,...Ch. 6 - Determine the number of permutations of {1, 2, …,...Ch. 6 - Determine a general formula for the number of...Ch. 6 - At a party, seven gentlemen check their hats. In...Ch. 6 - Use combinatorial reasoning to derive the...Ch. 6 - Determine the number of permutations of the...Ch. 6 - Verify the factorial formula Ch. 6 - Using the evaluation of the derangement numbers as...Ch. 6 - Prob. 20E Ch. 6 - Prove that Dn is an even number if and only if n...Ch. 6 - Show that the numbers Qn of Section 6.5 can be...Ch. 6 - (Continuation of Exercise 22.) Use the...Ch. 6 - What is the number of ways to place six...Ch. 6 - Prob. 25E Ch. 6 - Count the permutations i1i2i3i4i5i6 of {1, 2, 3,...Ch. 6 - Prob. 27E Ch. 6 - Prob. 28E Ch. 6 - Prob. 29E Ch. 6 - Prob. 30E Ch. 6 - Prob. 31E Ch. 6 - Prob. 32E Ch. 6 - Prob. 33E Ch. 6 - Prob. 34E Ch. 6 - Consider the board with forbidden positions as...Ch. 6 - Prob. 38E Ch. 6 - Prob. 39E Ch. 6 - Consider the multiset X = {n1 · a1, n2 · a2, …, nk...

Knowledge Booster

Similar questions

SEE MORE QUESTIONS

Recommended textbooks for you

Discrete Mathematics and Its Applications ( 8th I...
Math
ISBN:9781259676512
Author:Kenneth H Rosen
Publisher:McGraw-Hill Education
Mathematics for Elementary Teachers with Activiti...
Math
ISBN:9780134392790
Author:Beckmann, Sybilla
Publisher:PEARSON
Calculus Volume 1
Math
ISBN:9781938168024
Author:Strang, Gilbert
Publisher:OpenStax College
Thinking Mathematically (7th Edition)
Math
ISBN:9780134683713
Author:Robert F. Blitzer
Publisher:PEARSON
Discrete Mathematics With Applications
Math
ISBN:9781337694193
Author:EPP, Susanna S.
Publisher:Cengage Learning,
Pathways To Math Literacy (looseleaf)
Math
ISBN:9781259985607
Author:David Sobecki Professor, Brian A. Mercer
Publisher:McGraw-Hill Education