Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially 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.
6,901
questions
-1
votes
3
answers
109
views
How to prove by induction(do not use differential) $(1-x)^{-n}=\sum^{\infty}_{k=0}\binom{n-1+k}{k}x^k$
I would appreciate if somebody could help me with the following problem.
Q: How to prove by induction(do not use differential)
$$(1-x)^{-n}=\sum^{\infty}_{k=0}\binom{n-1+k}{k}x^k$$
I tried to solve ...
- 5,506
-1
votes
1
answer
1k
views
Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with
Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with
(a) An even number of 0s (b) An even total number of 0s and 1s (c) An even number of 0s and an even ...
- 471
-1
votes
3
answers
90
views
How to prove the summation $\sum\limits_{i=0}^b {b \choose i}(-1)^i\frac{1}{a+i+1}=\frac{a!b!}{(a+b+1)!}$ [closed]
I am working on the Beta function integration. After the integral, I want to prove the summation:
$$\sum_{i=0}^b {b \choose i}(-1)^i\frac{1}{a+i+1}=\frac{a!b!}{(a+b+1)!}$$
Can anyone give an idea?
- 2,893
-1
votes
1
answer
2k
views
Choosing non-adjacent chairs
There are $n$ chairs in a row. Find the number of ways of
choosing $k$ of these chairs, so that no two chosen chairs are
adjacent.
There are 10 chairs in a circle, labelled from 1 to 10. Find the
...
-1
votes
1
answer
105
views
Alexander takes the train [closed]
In the Central station there is a long train composed of two sorts of cars, green cars and blue cars.
Thus, the adjacent cars of the trains form blocks of the same color. As always, Alexander ...
- 732
-1
votes
1
answer
110
views
Anna stands at $A(0,0)$ and Eve at $B(5, 3)$. What is the maximum probability they will meet if...
Anna stands at $A(0,0)$ and Eve at $B(5, 3)$. Every minut Anna move $1$ right (with probability $p$) or $1$ up and Eve move $1$ left (also with probabilty $p$) or $1$ down. What is the maximum ...
- 90.7k
-1
votes
2
answers
64
views
John and Jane are taking the cards from the well mixed pack of $16$ cards. What is the probability that John in the hands has card of boy? [closed]
John and Jane are taking the cards from the well mixed pack of $16$ cards. In pack of cards are $4$ aces $(A)$, $4$ kings $(K)$, $4$ queens $(Q)$ and $4$ boys $(J)$. First John take one card from the ...
- 39
-1
votes
2
answers
396
views
How many numbers in $\{2,3,...,360\}$ share at least one prime factor with $360$?
What is the best way to go about solving this question?
- 409
-1
votes
1
answer
486
views
No of ways of allotting 4 dishes to n days [duplicate]
Possible Duplicate:
In how many ways can we colour $n$ baskets with $r$ colours?
There are n days and 4 types of dishes.Any 1 of 4 dishes is alloted to each day. And dishes of the consecutive ...
- 169
-1
votes
4
answers
5k
views
How many 4 digit numbers can be made with exactly 2 different digits
I need to find how many four digit numbers can be made using exactly 2 different digits.
ALL DIGITS FROM 1 TO 9 CAN BE USED. NOT JUST 1 AND 0
- 2,863
-1
votes
3
answers
2k
views
In a room there are eight lights. Each light can be switched on and off independently of the others. In how many ways can the room be lit with-?
In a room there are eight lights. Each light can be switched on and off independently of the others. In how many ways can the room be lit with-
five lights on?
at least five lights on?
-1
votes
1
answer
475
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
votes
1
answer
420
views
Permutation without fixed points. [closed]
We have a deck of 52 playing cards. We can assume an initial order of them; when i mix it, I ask if is more likely that P: "none card remains in the original position" or Q:"not(P)". And if we ...
user348628
-1
votes
1
answer
49
views
Two ways to calculate the same sum where the harmonic number pops up.
Can someone help me with this equality?
Prove that
$$\sum_{i=1}^n \frac{x^i}{i} = \sum_{i=1}^n {n \choose i}\frac{(x-1)^i}{i} + H_n$$
where $H_n$ is the harmonic number.
- 43
-1
votes
1
answer
115
views
Pigeon Hole Principle Cases [duplicate]
Given seven real numbers. Show that we can always choose two of them, say $a, b$ such that
$0 < \dfrac{a-b} {ab+1}< \sqrt{3}$
I think this is one of pigeon hole principle problem. I have tried ...
- 1,305
-1
votes
1
answer
58
views
Choose $n$ elements from a set where their summand equals $S$
Given a set size $n$ consisting of elements from $1 \rightarrow n$, choose $k$ elements from the set such that their summand equals $S$, if possible
For ex: $n = 5$ (i.e the choices $\{1,2,3,4,5\}$), ...
- 21
-1
votes
2
answers
68
views
The number of possible $4$ digit numbers with ordered digits
So I was taking a math test and I was stuck on a question asking,
How many possible $4$ digit numbers are there where each digit is lower than the one before it?
I wasn't sure how to account for ...
- 148
-1
votes
1
answer
2k
views
Closed form expression for $\sum_{k=0}^{n}(k^2 + 3k + 2)$
How can I find the closed form expression for the sum below using generating functions?
$$\sum_{k=0}^{n}(k^2 + 3k + 2)$$
EDIT:
We transform $k^2+3k+2$ into $(k+2)(k+1)$. Let $a_k=(k+2)(k+1)$ and $...
- 35
-2
votes
2
answers
91
views
Binomial and combinatorics [closed]
Please help me solve this problem.
Show that:
$$\sum_{k=1}^n k{n \choose 2k+1} = (n-2)2^{n-3}$$
- 1
-2
votes
4
answers
104
views
I tried this question by using pi denoting method and got a big equation what to do
Find coefficient of $x^6$ in
$(1+x)(1+x^2)^2.....(1+x^n)^n$
-2
votes
3
answers
101
views
Solve algebraically $n \binom{m+n}{m} = (m+1)\binom {m+n}{m+1}$ [closed]
I can't get very far with this one :/
- 17
-2
votes
1
answer
82
views
Find cofficient of $x^p$ in the expansion of $(ax^2+bx+c)^n$?
Here p can be $0, 1, 2...$ and $n$ can be $0,1,2,...$ I just want to get the generalized relation for finding the coefficient of $x^2$ or $x^3$ and so on in expansion of multinomials like $(1+x+x^2)^5$...
- 199
-2
votes
3
answers
83
views
help me in solving [closed]
evaluate :
$$
\sum_{k=0}^\infty\binom{n}{2+4k}
$$
I tried using pre formulated series of multinomial expansions but it doesnt help. Please give a solution to the problem, without using complex ...
- 372
-2
votes
1
answer
58
views
From the mountain top to the coast.
From a mountain top lead to ways to the (sea)coast. Neither way goes below of the sea level or over of the mountain top. Show that Adam and Barbara can go on the roads from the mountain top to the sea ...
- 2,022
-2
votes
1
answer
159
views
No two children may sit in adjacent seats [closed]
There are twelve people which includes 3 couples, 3 single adults and 3 children. In how many ways they can be arranged :-
a) if no two children can sit in adjacent seats?
b) if each couple must sit ...
- 143
-2
votes
1
answer
543
views
How many bit strings of length 20 have exactly five $1$’s and do not contain $11111$ as a substring? [closed]
Recall that a bit string is a string composed of characters $0$ and $1$.
Can someone explain how the answer is:
${20\choose5} - 16$?
- 1,149
-2
votes
1
answer
73
views
game theory+probability problem [duplicate]
In one city, $N$ Petya, Vasya and Tolya hide from zombies in an underground bunker. But they have no connection with the outside world and they don’t know if the zombies remained in the city or left. ...
- 161
-2
votes
1
answer
325
views
Existence of 1-factor in a connected graph and its connctivity
Let $G$ be a connected graph of even order( greater than or equal to 2k) such that every set of $k-1$ independent edges belong to a $1-factor$ of the graph. Then the graph is $k$-connected.
If the ...
- 389
-3
votes
1
answer
2k
views
partition of a multiset
Let $X=\{\underbrace{a_1,\cdots ,a_1}_{\nu_1},\cdots,\underbrace{a_k,\cdots ,a_k}_{\nu_k}\}$
be a multiset of cardinality $\sum{\nu_i}=n$ where each $a_i$ repeats $\nu_i$ times. We suppose that when $\...
- 11.1k
-3
votes
2
answers
1k
views
What is the number of permutations for given N numbers, such that the first part is non-decreasing?
Let $A$ be a list of $n$ numbers in range $[1,100]$ (numbers can repeat).
I'm looking for the number of permutations of $A$ which start with a non-decreasing part, where this part ends with the first ...