For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
1answer
94 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
0
votes
1answer
127 views

Solve the following recurrences using generating functions.

Solve the following recurrence using generating functions to find a formula for $A_n$ in terms of $n$. $A_0 = 1$, $A_1 = 1$, and for $n\geq 2$, $A_n = A_{n-1} + 2A_{n-2} + 4$
1
vote
0answers
60 views

Simple counting question related to equivalence classes

Let $S = \{1,2,3,...,10\}.$ Define the relation $\mathscr R$ on the power set $\mathscr P(S)$ of all subsets of $S$ by: for all $A,B \in \mathscr P(S),A\mathscr RB$ if and only if $N(A) = N(B)$. ...
0
votes
1answer
207 views

in how many ways can vertices of square be 3 colored if the square can moved in 3 dimension.

can any one explain to me how to answer this question Q a)in how many ways can vertices of square be 3 colored if the square can moved in 3 dimension. b) answer the same question but ...
4
votes
3answers
336 views

Constructing A Combinatorial Proof of a Binomial Identity

Consider: $$\sum_{k=0}^m \binom{n+k}k = \binom{m+n+1}m.$$ The LHS counts the number of subsets whose size is equal to its maximal element plus some fixed value. Alternatively, we can choose how ...
3
votes
1answer
177 views

Combinatorial Proof of a Binomial Coefficient Identity

I am looking to prove the following identity combinatorially: $\sum_k$ $n \choose 2k$ $2k \choose k$ $2^{n-2k}$ = $2n \choose n$ Clearly the RHS counts the number of ways to choose n elements ...
1
vote
1answer
36 views

Lowest bounds of Lucas Numbers

I'm currently working with bounding terms of a recurrence relation and just filled out the table for $L_n < (1.7)^n$ and am asked to figure out why the number $1.7$ is so special and how I can ...
3
votes
1answer
52 views

Smallest subset of $\{1,2,…,4n\}$ with a certain property

Fact 1: Let $A\subseteq\{1,2,...,2n\}$. If $n+1\leq |A|$, then there exists 2 elements $a,b\in A$ such that $a+b=2n+1$. Proof: This can be shown by writing $\{1,2,...,2n\}$ as the union of $n$ ...
1
vote
1answer
64 views

Trying to extend Vandermonde's formula to the case where m and n are not integers

I am currently trying to extend Vandermonde's formula of $\sum_j\binom{m}{j}\binom{n}{k-j} = \binom{m+n}{k}$ for $m,n,k$ to the point where $m$ and $n$ are not integers and I'm not sure how to tackle ...
0
votes
0answers
22 views

Trying to work towards a combinatorial proof. [duplicate]

What does (n-1 choose k-1) + (n-2 choose k-1) + ... + (k-1 choose k-1) equal? As of now I see it as something + 1 since anything choose itself will be 1 at the end but I have no idea how to begin to ...
2
votes
1answer
3k views

Counting The Number Of Ways To Seat People At A Table

How many ways are there to seat six people around a circular table where two seatings are considered the same when everyone has the same two neighbors without regard to whether they are right or ...
0
votes
1answer
73 views

Combinatorics pigeonhole probems

Let there be $R$ red and $B$ blue balls, with each ball distinct from the other (even of the same colour). $M$ balls ($(1)$ assume $M<R,B$) are to be chosen. What is the probability that the number ...
2
votes
5answers
331 views

Deriving Closed Form for a Recursion via Generating Functions

Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$. Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain $$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
1
vote
0answers
69 views

planar walks and catalan numbers

prove that following numbers are equal: (unordered) pairs of lattice paths with n+1 steps each, starting at (0,0), using steps (0,1) or (1,0), ending at the same point and only intersecting at the ...
1
vote
1answer
247 views

How to deduce the psition mapping of entries of a matrix?

I would be thankful if any peer shed light on me. Assume that the mapping of a set is unknown. By knowing n number of E element sets and the transformed sets with positioned elements, How can I ...
1
vote
1answer
46 views

Game problem related to combinatorics

Suppose I locked my ''very expensive'' mobile by a security code and now I forget the code. ;-( The things I remember about the code are: 1) It consists a sequence of FOUR numbers, each from 1 to 60. ...
0
votes
1answer
260 views

Combinatorial Proofs for Simple Binomial Identities

Consider $\sum k(k-1)(k-2)$ $n\choose k$ = $n(n-1)(n-2)$ $n-3 \choose 3$ for k >= 0 n >=3 I had initially thought the right side counted the ways to select three distinct objects from n and then ...
8
votes
2answers
443 views

How many injective functions $f:[1,…,m]\to{[1,…,n]}$ has no fixed point? $(m\le n)$

How many injective functions $f:[1,...,m]\to{[1,...,n]}$ has no fixed point? $(m\le n)$ I thought about the next thing: $f(x_1)\neq x_1$, Means i can choose for $x_1$ - (n-1) options, But then, ...
1
vote
3answers
519 views

Proof on distinct odd parts, partitions

Let $p$ ($n|$distinct odd parts) be the number of partitions of $n$ into distinct odd parts. PRove that $p(n)$ is odd if and only if $p$($n|$distinct odd parts) is odd. I know we're suppose to use ...
1
vote
1answer
76 views

Proof of the number of partitions.

Prove that the number of partitions of $n$ for which no part occur more than $9$ times is equal to the nujmber of partitions of $n$ with no parts divisible by $10$.
1
vote
2answers
510 views

combinations of Rubik cube

A Rubick's Cube has owl heads on it, which can be misoriented. How many (times) MORE combinations are there of this cube vs. one that has blank stickers? Can someone give me some hints? Thanks
0
votes
1answer
161 views

Proof Involving Difference Operators

Let E be the forward shift operator on $x$ defined by $Ef(x) = f(x+1)$. Similarly, let $\delta$ be the forward difference operator such that $\delta f(x) = f(x+1) - f(x)$ and the inverse operator ...
2
votes
1answer
178 views

Proof of asymptotic expansion of binomial coefficient

here's the problem I'm currently stuck on: Prove that (for $k$ fixed): $$\binom{N}{k}=\frac{N^{k}}{k!}+O(N^{k-1})$$ I know that: $$\binom{N}{k}\le\frac{N^{k}}{k!}$$ But I'm not sure how to ...
1
vote
2answers
278 views

Inclusion & Exclusion: In how many permutations of the digits $0,…,9$ there's no continuity of 7 digits or more?

In how many permutations of the digits $0,...,9$ there's no continuity of 7 digits or more? (Ex. the number 203456789 1 should not be counted) I believe that the basic case, for the inclusion ...
2
votes
2answers
69 views

Using Generating Functions (again) to Solve Recurrences

Consider the recursion $a_n = 2a_{n-1} + (-1)^n$ where $a_0 = 2$ Then $A(x) = \sum a_n x^n$ = $2 + \sum a_n x^n$ shifting the index of summation. The only next move I can think of is to now ...
1
vote
2answers
447 views

A counting problem involving ternary sequences

A ternary sequence is a sequence all of whose elements are the digits 0, 1 or 2. Find the number of ternary sequences of length 8 in which the digits 0 and 1 each occur an even number of times. ...
2
votes
1answer
136 views

Combinatorics riddle: Sorting people in a cinema line.

Say i want to go to the cinema. There are two types of movies. Action movie. Drama movie. Because action is more interesting it costs 50$. And the cost for drama is 10€. There are 200 people ...
1
vote
1answer
153 views

Computing the probability of rolling a sum of 18 on 4 six-sided dice

The following PDF gives an explanation on page 11. Unfortunately I do not know how to reproduce it here. http://web.mit.edu/~qchu/Public/TopicsInGF.pdf In short, I am not sure how the symmetry ...
2
votes
2answers
248 views

Combinatorics Example Problem

Ten weight lifters are competing in a team weightlifting contest. Of the lifters, 3 are from the United States, 4 are from Russia, 2 are from China, and 1 is from Canada. Part 1 If the scoring ...
2
votes
2answers
52 views

Work-at-home days such that the office is always staffed

I am quite rusty on combinatorial formulas, but I think the following practical question has a combinatorial answer. This is not homework. A company gives it's technicians two work days per week to ...
4
votes
3answers
297 views

Combinatorial Proof for a Recursive Sequence

For $n>3$ let $g_n = g_{n-1} + g_{n-3}$ where the recursion takes the value 1 for n = 0,1,2. Prove that $g_{2n} = (g_n)^2 + 2g_{n-2}g_{n-1}$ combinatorially, $n > 1$. For the time being I am ...
4
votes
2answers
929 views

How many ways are there to add the numbers in set $k$ to equal $n$?

How many ways are there to add the numbers in set $k$ to equal $n$? For a specific example, consider the following: I have infinite pennies, nickels, dimes, quarters, and loonies (equivalent to 0.01, ...
2
votes
2answers
665 views

If 8 new teachers are to be divided among 4 schools, how many divisions are possible?

If 8 new teachers are to be divided among 4 schools, how many divisions are possible? I understand that in this question you are just solving for the multinomial coefficients of the multinomial ...
4
votes
4answers
159 views

Evaluating Sums Algebraically or Combinatorially

Consider (1) $$\sum_{k=0}^{n}\binom{n}{k}2^{k-n}$$ (2) $$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$ These sums appear too difficult (in my mind) to evaluate combinatorially. What are some ...
0
votes
1answer
211 views

How many 9 letter strings are there that contain at least 3 distinct vowels?

Question: How many 9 letter strings are there that contain at least 3 distinct vowels? I am studying and I was wondering if this answer could be an alternative answer to the question above: ...
1
vote
1answer
49 views

8 friends, 7 nights, invite 4 every night, all of the friends must be invited, how many options?

Assume I have 8 friends, I want to invite 4 friends each night for 7 night so everyone will be invited at least once. How many combinations are there to do it? I think I'm supposed to use the ...
0
votes
0answers
512 views

Probability of Obtaining A Particular Sum from Successive Dice Rolls

Suppose you have a regular die with 6 faces numbered 1 through 6, respectively, and roll the die 4 times. What is the probability that the sum of the 4 rolls is 14? This problem is equivalent to ...
0
votes
1answer
165 views

How many ways are there to sit $n$ couples on a bench when every couple sits together?

How many ways are there to sit $n$ couples on a bench with $2n$ sits, when every couple sits together? How many ways are there to sit the couples so that none of the couples will sit together?
0
votes
2answers
154 views

Construct set family whose members intersect at even number of points

F $\subseteq 2^{[n]}$ is a set family. Every member of F has odd size. Every two distinct members of F intersect at even number of points. 1) Show that |F| $\leq$ n 2) Suppose now every member has ...
7
votes
0answers
175 views

The right way to motivate lattice theory in a combinatorics class

I am attending a course on combinatorics. I was asked to present Möbius functions on lattices for this course. I was trying to look for a simple non-trivial problem that illustrates the need for ...
3
votes
1answer
84 views

Evaluating Sums Combinatorially

Consider the following finite sums: (1) $\sum k(k!)$ for k from 1 to n (2) $\sum (k-1)(n-k)$ from 1 to n I am trying to determine how to evaluate these sums combinatorially. It seems the first is ...
2
votes
2answers
134 views

Tricks to Solve Arbitrary Recursions

Consider two recursions: (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$ (2) $na_n = (n-2)a_{n-1} + n/2$ with $a_0 = 0$ When I look at the first recursion it suggests to me that I ...
5
votes
1answer
349 views

Combinatorial puzzle

Let $\pi$ be a set of ordered pairs of natural numbers, $\pi = \lbrace (n_1,n_2) \dots (n_k ,n_{k+1})\rbrace$ (a "set of pairs"). Let $\cup \pi$ be the set $\lbrace n_1 n_2 \dots n_k ...
0
votes
0answers
30 views

sphere packing bound and codewords [duplicate]

show that a binary code of length 6 and minimum distance 3 can have at most 9 codewords.I think this can be shown by sphere packing bound but how can i show that it can not have 9 codewords?and ...
-1
votes
1answer
58 views

What is the algorithm to permute a set of elements in to a fixed length? [closed]

for example {abc, d, e, f, xy} and fixed length 5 the output should be abced, abcef, abcdf, abcxy, xydef further is for multiple length 5 and 6 append the output list is abcedf, abcxyd, abcxye, ...
0
votes
0answers
89 views

Inclusion-Exclusion Principle

I'm having a bit of trouble with this, and can't get my numbers to come out correctly. Here's an example: Get a maximum of n items, composed of the following: x burgers y hot dogs z fruit w napkins ...
1
vote
2answers
101 views

to get a MDS code from a hyperoval in a projective plane

explain how we can get a MDS code of length q+2 and dimension q-1 from a hyperoval in a projective plane PG2(q) with q a power of 2? HINT:a hyperoval Q is a set of q+2 points such that no three ...
3
votes
1answer
2k views

Multinomial Theorem Example Questions

I'm learning about the multinomial theorem and working 2 examples in a book. I thought I understood the examples until I did example 5c. I don't understand why these two examples are different. In ...
0
votes
1answer
70 views

bijective mapping homework question

I have to answer a question which i don't really understand. The question is: Find an appropriate bijective mapping between a set of sequences and the set in question: 1. In how many ways can $k$ ...
2
votes
2answers
52 views

New to generating functions - how do I get the function from the sequence defined by $a_n= n$ for $n\geqslant 0$?

I'm given: $a_n= n$ for $n \geqslant 0$. I'm quite good at recursive generating functions, but I haven't came across a simpler one like this, so I'm sure I'm just overlooking something really basic.