All Questions
Tagged with binomial-coefficients combinatorics
3,233
questions
3
votes
0
answers
468
views
Determine the general term of the sequence $(a_n)_{n\ge1}$, strictly decreasing
Determine the general term of the sequence $(a_n)_{n\ge1}$, strictly decreasing, of strictly positive numbers, which satisfies the properties:
a) $na_n \in \mathbb{N} \setminus \{0\}$ for every $n \in ...
2
votes
0
answers
92
views
Problem involving determinants and binomial coefficients
Let $\lambda = (\lambda_1, ..., \lambda_{n})$ be a partition, $\lambda^{'}$ be the conjugate of $\lambda$, and $$A_{\lambda} := \det[\tilde{h}_{\lambda_i - i + j}^{(i)}]_{1 \leq i, j \leq n},$$ where $...
1
vote
0
answers
41
views
Cardinality Relations in Set Theory: Pairs and Binomial Identity
Let $A$ be a non-empty set with $n$ elements.
a) Determine the number of pairs $(X, Y)$ where $X$ is included in $Y$, both included in $A$, and $\text{card}(X) = k$, $\text{card}(Y) = m$; $1 \leq k \...
6
votes
1
answer
147
views
How to find all positive integers $n,k$ such that ${n\choose k}=m$ for a given $m$?
This question is motivated by a simple exercise in Peter Cameron's Combinatorics: Topics, Techniques, Algorithms:
A restaurant near Vancouver offered Dutch pancakes with ‘a thousand and
one ...
1
vote
1
answer
43
views
Summing a binomial series that arose while counting functions
Define $f:A \to A$ where $A$ contains $n$ distinct elements. How many functions exist such that $ \forall x \in A, f^m(x)=x$, $(m<n)$ (and $m$ is prime to avoid the mistake pointed out in the ...
0
votes
1
answer
66
views
Seeking help to Prove The Recursive Binomial Coefficient Formula
A rich body of research exists on Binomial Coefficients, with the concept finding its roots in Pascal's Triangle. My current investigation focuses on a Recursive Approach for generating these ...
2
votes
2
answers
72
views
compute $\sum_{k=0}^{n} \frac{{(-1)^k}}{k+1}{n \choose k}$.
Find $\sum_{k=0}^{n} \frac{{(-1)^k}}{k+1}{n \choose k}$ as a function of n.
I have done it in the following way:
Notice first that $\sum_{k=0}^{n} \frac{{(-1)^k}}{k+1}{n \choose k} = \sum_{k=0}^{\...
0
votes
0
answers
22
views
How many bit strings of length n contain more 0’s than 1’s? [duplicate]
To solve this, I think we need to use combinatorial reasoning.=
Consider a bit string of length ( n ). There are ( 2^n ) possible bit strings of this length because each bit can independently be ...
0
votes
1
answer
30
views
A probability question over multiple questions test.
I was wondering about this problem: say I have to take a test made of $31$ questions chosen among a database of $140$ questions total.
Those questions are open questions (that is, not multiple choice ...
2
votes
1
answer
43
views
Number of ways to select a subset of the set $ \{1, 2, . . . , 200 \}$ in such a way that it contains the same number of even and odd elements.
Select a subset of the set $ \{1, 2, . . . , 200 \}$ in such a way that it contains the same number of even and odd elements. In how many ways can this be done?
My solution:
To ensure that a subset ...
3
votes
0
answers
60
views
Prove combinatoric equation: $\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$
Prove the equation:
$$\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$$
My solution:
We have $n+1$ players numbered from $1$ to $n+1$. We want to play a team game that ...
7
votes
1
answer
161
views
Reference for a combinatorial identity involving the number of derangements
Let $$c_n=n!\sum\limits_{k=0}^n (-1)^k \frac{1}{k!}$$ be the number of derangements of $n$ elements. The following combinatorial identity is coming up in my research:
$$\sum\limits_{j=1}^{n-2}c_{n-j}{...
0
votes
0
answers
38
views
find number of disjoint subsets
For my discrete maths course i did the following exercise:
Let M be a finite set with n elements, find
$|\{(U,V)|U,V\subseteq M , U \not = V,U\cap V= \emptyset \}|$
I did it the following way:
choose ...
8
votes
1
answer
186
views
Simplifying a binomial sum for bridge deals with specific voids
While trying to get an expression for the number of deals from a generalised bridge deck with nobody being void in any suit I encountered the following subproblem.
From a generalised bridge deck with $...
3
votes
0
answers
88
views
Motzkin numbers generating function, binomial, recurrence relation
We will find the formula for Motzkin numbers and show that they enumerate chord diagrams. Let $\mathcal{M}$ be the following class of combinatorial configurations. A configuration of weight $n$ is a ...