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)

0
votes
2answers
73 views

Subset Counting question

How many subsets of [20] consist of 3 odd integers and any number of even integers? This question was asked in an interview today and I wasn't able to solve it. Please help, thanks in advance
2
votes
0answers
29 views

Inviting People To A Party With Limitations

A person has 8 friends, of whom 5 will be invited to a party. (b) How many choices if 2 of the friends will only attend together? Using inclusion-exclusion there are ${8\choose 5}-{2\choose ...
2
votes
2answers
41 views

Counting Problem - Strings

What is the number of strings of four decimal digits that contain exactly one digit repeated twice? (e.g 1198) My intuition was to first place the digits that aren't repeated and then place the ...
1
vote
0answers
19 views

Total probability distribution of multiple random lotteries

My question: Imagine $d$ identical lotteries. Each individual lottery picks a cost $c_{i}$ between $0$ and $1$. Picking a costs occurs with probability distribution $f(c)$. The total cost of these ...
3
votes
1answer
25 views

Choosing People For A Committee With Limitations

From a group of 8 women and 6 men, a committee consisting of 3 men and 3 women is to be formed. How many different committees are possible if (c) 1 man and 1 woman refuse to serve together? ...
1
vote
0answers
31 views

Derangements question

Let $D_n$ be the number of derangements of $n$ objects and $P_{n,k}$ be the number of permutations of $n$ objects with exactly $k$ fixed points. Give a formula for $P_{n,k}$ in terms of $D_{n−k}$. ...
4
votes
1answer
34 views

How many strings of $\{0,1,2,3\}$ of length $n$ are there such that $0$ appears exactly once and $1$ appears an even number of times?

How many strings of length $n$ of the digits $\{0,1,2,3\}$ are there such that $0$ appears exactly once and $1$ appears an even number of times? My attempt: define $a_n$ to be a sequence of such ...
1
vote
2answers
27 views

In how many ways can a $5 \times 5$ matrix be formed such that sum of row elements and column elements are $4$ and entries are $0$ or $1$?

Let we have a $5 \times 5$ matrix and the elements can be either $0$ or $1$ and the sum of elements of each row and column is $4$ then in how many ways can the matrix be formed ? I tried doing it in ...
2
votes
3answers
128 views

Number of ways to express a number as the sum of different integers

Given a number $n$, then $P_k(n)$ is the number of ways to express $n$ as the sum of $k$ integers. For example $P_2(6)=7$ $0+6=6$ $1+5=6$ $2+4=6$ $3+3=6$ $4+2=6$ $5+1=6$ $6+0=6$ Now I worked ...
2
votes
2answers
28 views

Four Athletes run a race

Four Athletes $A,B,C$ and $D$ run in a race. They have equal abilities so that all place orderings have equal probabilities. There are no ties (i) What is the probability that the first two places ...
0
votes
1answer
52 views

Is my graph a tree?

Let M be a smooth connected manifold. G is a group act on M cocompactly and suppose there is a harmonic function $h$ on M with minimal energy.$h:\rightarrow [0,1]$ such that h is nonconstant and ...
0
votes
1answer
39 views

Game with matches. Very interesting mathematical problem.

Suppose you have a set of matches. You arrange them in 9 rows such that the first row has one match the second two matches the third three and so on until the ninth row which has nine matches. There ...
0
votes
0answers
17 views

Rectangular Grid Walk Question

I learned a trick that for rectangular fields, one can use combinations and define $u$ as up and $r$ as right. I saw that the total steps needed to get to $B$ is $4$ no matter which way you go. So I ...
1
vote
3answers
58 views

How to prove $\sum_{i=1}^{n}\binom{n}{i}p^i(1-p)^{n-i}i = np$?

How to prove, when $p\in[0, 1]$, $$\sum_{i=1}^{n}\binom{n}{i}p^i(1-p)^{n-i}i = np$$ Is there a name for this formula?
1
vote
1answer
29 views

Coloring the 6 vertices of a regular hexagon with a limited use per color

I want to solve to following two-part problem. I solved the first part but I am not sure how to start on part B. A) How many ways are there to color the 6 vertices of a regular hexagon using 4 colors ...
1
vote
0answers
30 views

Generating Series and Recurrence Relation and Closed Form

We have the following recurrence relation: $b_n=2b_{n-1}+b_{n-2}$ and initial conditions $b_0=0, b_1=2$ I use the generating series method to solve as following: Let ...
0
votes
1answer
21 views

How to select four points so that origin is not contained in convex hull of these points?

I have a regular 12-gon $A_1A_2...A_{12}$ with centre $O$. How to select four points so that centre $O$ doesn't lie in and lie on quadrilateral? I tried. With diameter $A_{12}A_6$, consider ...
2
votes
1answer
40 views

Dividing $8$ Children into $4$ teams of $2$ players each

In how many ways can you divide $8$ children into $4$ teams of $2$ players each? My attempt: $$ \binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2}$$ $$ = 4 \times 7 \times 3 ...
7
votes
3answers
70 views

How many $n-$digit number that contain only digits $ 1,2,3,4,5,6$

How many $n- $digit numbers can be formed from the digits $1,2,3,4,5$ and 6, which contains the numbers $1$ and $2$ as neighbours. Let $p_n$ be the number of n-digit numbers which consist only of ...
2
votes
3answers
49 views

Generating function for $a_n= a_{n-1}+2a_{n-2}$+3

How do I find a generating function for $a_n= a_{n-1}+2a_{n-2}$+3 using sigma notation? with initial conditions $a_0$ =2 and $a_1$ = 2. I'm mainly confused by how to deal with the "+3" at the end. ...
1
vote
0answers
37 views

movement of knight in a game of chess

This question arose in my brain while playing a game of chess. We all know how a knight moves in a game of chess. I wanted to calculate the minimum no. of moves required by a knight to cover all the ...
0
votes
0answers
48 views

finding number of subsets such that for given $(a,b)$ $a$ is the minimum element and $b$ is maximum element in that subset

I have a set of size $n$ which is sorted in ascending order. This is the process I followed: The largest element of the set is largest in $2^{n-1}$ subsets and the second largest is largest in ...
1
vote
0answers
16 views

Approximating Number of members in a set after union

I am not sure whether it is possible to this or not, but what I am trying to do is calculate the number of members in a set union (of large size N) without actually forming the set physically. For ...
1
vote
1answer
34 views

All Combinations Of Pairs

A dance class consists of 22 students, of which 10 are women and 12 are men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible? First there are 5 ...
0
votes
0answers
15 views

How to assemble rook polynomials?

I have a problem. I need to assemble a rook polynomial for the chessboard (6x6 boards). Black boards are 1, white boards are 0. ...
1
vote
1answer
40 views

Intuitive explanation for Derangement

The recurrence relation for Derangement is as follows: Let $D_n$ denote the number of derangements of a set $\{1,2,3...n\}$ $D_n=(n-1)D_{n-1}+(n-1)D_{n-2}$ Can someone give and intuitive ...
4
votes
3answers
419 views

How many binary strings of length 2n + 1 have more 1's than 0's? Use bijection to prove.

NOTE: This is a homework question, so I only ask for hints and suggestions to nudge me in the correct direction. Question: Let $n \in \mathbb{N}$. How many binary strings of length 2n + 1 have more ...
1
vote
0answers
26 views

Polya's Enumeration Theorem applied to the 'colourings' of a cycle using integers

I am trying to solve a problem about an application to Polya's Enumeration Theorem. The problem concerns the cycle group on 5 vertices, $C_5$. I found its cycle index to be $x_1^5+4x_5^1$. Thus the ...
0
votes
1answer
36 views

Arrange 52 cards into 4 piles. How many combinations?

I'm doing some statistical physics and there is a conceptual question involved that I have a poor understanding of how to approach conceptually: Any help appreciated :) Thank You! :) EDIT: Answer ...
5
votes
4answers
260 views

Finding out this combination

In how many ways three non-empty strings of length less than or equal to $N$ using $k$ different characters can be selected so that in each case, among the three strings, no string is prefix (not ...
2
votes
1answer
30 views

Permutation At A Railway Track

Engines numbered 1, 2, ..., n are on the line at the left, and it is desired to rearrange(permute) the cars as they leave on the right-hand track. An engine that is on the spur track can be left ...
1
vote
1answer
35 views

Permutations how to eliminate with certain rules

I need to create a list with six elements $x$, $y$, $z$, $w$, $u$, $t$. After this, I should print all of the possible permutations of the elements with length $3$ which follows this rule: The ...
8
votes
2answers
59 views

Minimal collection of subsets to reconstruct singletons

I have come across the following problem in a technical application. For a given integer $n$, what is the minimal collection of subsets of $\{1,\dots,n\}$ such that all "singleton" sets $\{1\}, \{2\}, ...
0
votes
1answer
23 views

How to minimize the maximum Hamming distance of a linear block code.

I suspect it is possible to choose generators of 2^l so that: Each number 1-l is in some generator. The maximum Hamming distance between any two vectors would be at most (l+1)/2. For instance, ...
1
vote
0answers
46 views

Stirling numbers of the second kind vs. binomial coefficient

For $n,k$ positive integers, such that $n\geq k$, denote by $\left\{{n\atop k}\right\} $ the Stirling numbers of the second kind and $\binom{n}{k}$ the binomial coefficient. It is rather ...
3
votes
0answers
29 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
3
votes
1answer
45 views

My answer to this combi problem doesn't match the answer in the book (Problem-Solving Strategies)

[Problems 31 and 32 from Arthur Engel's Problem-Solving Strategies.] Let $n$ children be seated in a line. How many ways can they change their places if they may only move by one place at most? ...
1
vote
2answers
100 views

$2\times 5 \times 8 \ldots \times (3n-1)=?$

Does anybody know if there is a closed form expression using factorials for the above product? I'm not seeing it but I feel like there must be. The recursive relationship corresponding to this ...
4
votes
2answers
104 views

How many ways are there to express a number as the product of groups of three of its factors?

Specifically, I am thinking of a cuboid with a given volume ($28\,000$) that has sides of integer length. For example, $20 \cdot 20 \cdot 70 = 28\,000$, but so do $10 \cdot 40 \cdot 70$ and $1 \cdot 1 ...
1
vote
1answer
61 views

Combinatorics Proof

Let $b_n$ be the number of positive integers whose digits are all $1,$ $3,$ or $4,$ and add up to $n$. For example, $b_5 = 6$, since there are six integers with the desired property: $41,$ $14,$ ...
2
votes
1answer
36 views

In how many ways can we arrange $6$ red, $3$ blue and $4$ green balls in a row such that there is no adjacent green balls?

All ball of one color are identical. My idea is to calculate first the total numbers to arrange the $13$ balls. It equals $\dfrac{13!}{6! 3! 4!}=60060.$ Then I want remove the cases where all $4$ ...
0
votes
1answer
34 views

How can I mathematically model the combinatory problem?

I have the following problem, and I would like to model it using a mathematical formula, for a purpose of optimization problem: let's say that I have two tasks $[T_1, T_2]$, and $3$ resources ...
7
votes
6answers
115 views

Intuitively understanding $\sum_{i=1}^ni={n+1\choose2}$

It's straightforward to show that $$\sum_{i=1}^ni=\frac{n(n+1)}{2}={n+1\choose2}$$ but intuitively, this is hard to grasp. Should I understand this to be coincidence? Why does the sum of the first ...
2
votes
2answers
59 views

Trinomial Theorem for negative exponents

I just learned of binomial theorem for negative integers (or in that case any real $n$). Does such a theorem exist for the trinomial theorem $$(a+b+c)^n$$ and has there been work done? I would think ...
2
votes
1answer
70 views

A game with rice

You have $N$ rices, and K places. You can put or take a rice in place numbered $1$ at any time. You can put a rice or take a rice from a place numbered $i$ iff there is a rice at a place $i-1$. For ...
0
votes
1answer
35 views

Ordering People

How many ways are there to order $3$ boys and $3$ girls when the girls sit together and same for the boys. How many ways are there to order $3$ boys and $3$ girls when $2$ boys can not sit ...
2
votes
2answers
81 views

The value of ${\sum_{k=0}^{20}}(-1)^k\binom{30}{k}\binom{30}{k+10}$

$\newcommand{\b}[1]{\left(#1\right)} \newcommand{\c}[1]{{}^{30}{\mathbb C}_{#1}} \newcommand{\r}[1]{\frac1{x^{#1}}}$ The value of $$\sum_{k=0}^{20}(-1)^k\binom{30}{k}\binom{30}{k+10}$$ It is also the ...
1
vote
0answers
22 views

Combinatorics while drawing cards

He have a deck with $52$ cards and $4$ suits, $H$,$D$,$C$,$S$, from which you take $26$ cards. There are some combinations that, when taken with the same suit, give a prize. Let's those combinations ...
1
vote
3answers
39 views

Proving some identities in Derangements.

Let $D_n$ denote the number of derangements of {1,2,3,...,n}. We know that for $n\geq1$, we have: \begin{equation*} D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}+...+(-1)^n\frac{1}{n!}). \end{equation*} Given ...
1
vote
1answer
25 views

How does the Borda count work?

I was watching this video. about ranking a bunch of proposals by dividing the full list in to sub lists and each person that submitted the proposals gets one of these sub-lists and ranks it. The lists ...