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.

38,396 questions
37 views

Combinations and Permutations. [on hold]

A college has $750$ students and $400$ of them are girls. In how many ways can a delegation of $10$ be selected such that $4$ of them are boys? Using combinations and permutations.
38 views

In how many ways can the first, second and third prizes be drawn in a raffle? [on hold]

$3,500$ raffle tickets are issued in a charity function. In how many ways can the first, second and third prizes be drawn? Using combinations and permutations
44 views

${}_nP_r$ versus $n^r$ [on hold]

If I had $n=2$ different symbols, how many $2$-symbol ($r=2$) "words" could I create? If I had $n=5$ different symbols, how many $2$-symbol ($r=2$) "words" could I create? Would I use the ...
46 views

Prove the determinant identity (2)

For any natural $n$ prove that \begin{gather*} {\frac { q \left|\begin {array}{ccc} {q}^{n+2}& \left( {\frac {p}{q}} \right) ^{n+2}& \left( {p}^{-1} \right) ^{n +2}\\ {q}& {\frac {p}{...
104 views

$10$ numbers from $1,2,\dots,37$

$10$ numbers are chosen from $\{1,2, \ldots, 37 \}$. Show that we can choose $4$ of them such that the sum of two of these four is equal to the sum of the other two. My attempt : Almost nothing I ...
48 views

Number of ways to divide dotted square grid in half

Consider a $4\times4$ dotted grid that looks like this: By drawing a series of connected straight lines going from dot to dot, there are many ways to divide the square into two halves (of equal area)...
32 views

Determine the number of ways n distinct marbles can be placed inside five jars.

Determine the number of ways n marbles can be placed inside five distint jars, if the 1st jar must contain 1 marble, 2nd jar must contain 4 marbles, 3rd jar must contain 5 marbles, 4th and 5th marble ...
35 views

Combinatorics proof involving finite series

I am trying to prove the following identity with little success!: $\sum_{k=0}^{p-1} (p-k) = p(p+1)/2$. Any suggestions? Thanks.
24 views

28 views

Express a set of number with binomial coefficients in terms of $n$ [duplicate]

Hi I'm working on my scholarship exam practice but I got stuck at my last question, could you please have a look? I'll write every part of question so you know the big picture. I have marked the ...
30 views

Kenneth Rosen-Combinatorics-Exercise for section 5.5

For this question: There are $5$ balls and $3$ boxes. Find the number of ways to distribute the balls in the boxes for the given $4$ cases. 1>box and the balls are labelled: Then we get $3^5$ ...
19 views

$\binom{n+1}{r+1}=\sum_{k=r+1}^{n+1}\binom{k-1}{r}$ whenever $n\geq r\geq 0$ [duplicate]

$\binom{n+1}{r+1}=\sum_{k=r+1}^{n+1}\binom{k-1}{r}\ \text{ whenever }n\geq r\geq 0.$ Anyone can help me with this proof?
84 views

Show that $a_{n-1}$ divides $a_{kn-1}$ for recurrence relation $a_n = a_{n-1} + a_{n-2}$

Question is posted above will be super thankful for all your help $a_n = a_{n-1} + a_{n-2}$ Show that $a_{n-1}$ divides $a_{kn-1}$for recurrence relation above $a_1 = 1$ $a_2 = 2$ $a_3 = 3$
30 views

Number of five letter words possible using the english alphabet, not including anagrams

I'm studying for an intro to combinatorics midterm by completing past midterms. One of the questions is "How many ways are there to choose $5$-letter 'words' from the $26$-letter English alphabet ...
40 views

Permutations preserving a filtration property

Suppose $\mathcal{A}$ is a non-empty family of sets of natural numbers size $n$ with the property that if $\{k_1<k_2< \dots <k_n\}\in \mathcal{A}$ and $j_i\leq k_i$ for all $1\leq i\leq n$, ...
74 views

How to find the growth rates of $n$ bacteria, knowing the sizes of bacteria from $m$ observations?

Each bacterium grows at a some constant rate, i.e. every minute the size of the bacteria increases by some constant value. Different bacteria can grow at different rate (they can also grow at same ...
47 views

A restaurant has a choice of $12$ main courses and $4$ desserts. How many $2$-course dinner selections are from the menu?

I got this question on combinatorics, but I am very confused about it. Q: A restaurant has a choice of $12$ main courses and $4$ desserts. How many $2$-course dinner selections are from the menu? I ...
33 views

How many circular necklaces can be made with the length of p (a prime number), that can be created by connecting n different types of beads together

Given an unlimited number of beads of n different types, how many circular necklaces are there, with the length of p (a prime number), that can be created by connecting the beads together? Note that ...
32 views

Combinations: summation of combinations equalities

Suppose we have two quantities $$A = \sum^n_{i=0}C^n_i (X_{n-i}X_{i+1} + X_iX_{n-i+1})\\ B = \sum^{n+1}_{i=0}C^{n+1}_i (X_iX_{n-i+1}),$$ where $C^n_i$ is the combination notation, and $X$ are just ...
39 views

Infinite modular lattices

A finite lattice $L$ is called modular if and only if its elements satisfy the following modular identity: For all $x,y,z\in L$ such that $x\leq z$, we have $x\vee(y\wedge z)=(x\vee y)\wedge z$. How ...
34 views

The sum of the second numbers in the first 100 rows of Pascal's Triangle

What is the sum of the second numbers in the first $100$ rows of Pascal's triangle (excluding the first row, the row containing a single $1$)? The sum should be over the second through the hundredth ...
34 views

32 views

What's the sum of all 6 digit numbers that can be made with numbers 1, 2, 3, 5, 7, 8?

It's not necessary for the 6 digit numbers to have unique numbers. E.g. 111111 is an acceptable number.
15 views

Specific position / Restricted permutation [I don't exactly know the name of this topic]

In the word ARTICLE find the number of permutation by keeping A in the first place or not keeping E in the last place. How do I solve this. What's the exact category for this type of permutation? ...
38 views

Linear programming over integers mod 2, expressing function as sum of two

Let $h=a+\ell+1$ and define $$f(a,\ell;u_2,u_1,\tau) = \frac{h^2}2 u_2 +h(a+\frac12)u_1+\frac{a(a+1)}2 \tau+1$$ where all the variables are integers, and such that $u_1=u_2 \pmod{2}$. Such $f$ is an ...
34 views

Generating Function functional relation

Suppose I have a generating function which I know satisfies the relation $$x = T(x) (1 - x - T(x^2)).$$ Can I say anything about the coefficients? Ideally I would be able to get some kind of closed ...
52 views

Is there any way to simplify $\binom{n}{k}+\binom{n+1}{k}$?

I was wondering if there is any way to express the sum $\binom{n}{k}+\binom{n+1}{k}$ as only one binomial coefficient?
20 views

Combinatorics/Permutations [duplicate]

A village has about 1 million residents. Suppose each resident has a jar with 100 coins in it.Two jars are considered to be “equivalent” if they have the same number of 10c, 20c, 50c, \$1 and \$2 ...
20 views

Assignment of subsets with overlap rule

I want to create $M$ lists of size-$k$ subsets of $\mathbb{Z}_n$, labeled $A_1, \ldots, A_M$ with the following properties: $|A_1| = |A_2| = \ldots = |A_M|$, i.e. every list contains the same number ...
Lets consider all matrices with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$) containing only integers between $0$ and $K−1$ (inclusive). For each such matrix $A$, let'...